# Approximating submodular $k$-partition via principal partition
sequence111University of Illinois, Urbana-Champaign. Email: {karthe,
<EMAIL_ADDRESS>Supported in part by NSF grants CCF-1814613 and
CCF-1907937.

Karthekeyan Chandrasekaran  Weihang Wang

###### Abstract

In submodular $k$-partition, the input is a submodular function
$f:2^{V}\rightarrow\mathbb{R}_{\geq 0}$ (given by an evaluation oracle) along
with a positive integer $k$ and the goal is to find a partition of the ground
set $V$ into $k$ non-empty parts $V_{1},V_{2},\ldots,V_{k}$ in order to
minimize $\sum_{i=1}^{k}f(V_{i})$. Narayanan, Roy, and Patkar [17] designed an
algorithm for submodular $k$-partition based on the principal partition
sequence and showed that the approximation factor of their algorithm is $2$
for the special case of graph cut functions (which was subsequently
rediscovered by Ravi and Sinha [21]). In this work, we study the approximation
factor of their algorithm for three subfamilies of submodular functions—namely
monotone, symmetric, and posimodular and show the following results:

  1. 1.

The approximation factor of their algorithm for monotone submodular
$k$-partition is $4/3$. This result improves on the $2$-factor that was known
to be achievable for monotone submodular $k$-partition via other algorithms.
Moreover, our upper bound of $4/3$ matches the recently shown lower bound
under polynomial number of function evaluation queries [22]. Our upper bound
of $4/3$ is also the first improvement beyond $2$ for a certain graph
partitioning problem that is a special case of monotone submodular
$k$-partition.

  2. 2.

The approximation factor of their algorithm for symmetric submodular
$k$-partition is $2$. This result generalizes their approximation factor
analysis beyond graph cut functions.

  3. 3.

The approximation factor of their algorithm for posimodular submodular
$k$-partition is $2$.

We also construct an example to show that the approximation factor of their
algorithm for arbitrary submodular functions is $\Omega(n/k)$.

##  1 Introduction

A set function $f:2^{V}\rightarrow\mathbb{R}$ is submodular if $f(A)+f(B)\geq
f(A\cap B)+f(A\cup B)$ for every $A,B\subseteq V$. An evaluation oracle for a
function $f:2^{V}\to\mathbb{R}$ takes a subset $A\subseteq V$ as input and
returns $f(A)$. We consider the _submodular $k$-partition_ problem defined as
follows: The input consists of a non-negative submodular function
$f:2^{V}\to\mathbb{R}_{\geq 0}$ on a finite ground set $V$ via an evaluation
oracle and an integer $k\geq 2$. The goal is to find a partition
$V_{1},V_{2},\ldots,V_{k}$ of $V$ into $k$ non-empty parts in order to
minimize $\sum_{i=1}^{k}f(V_{i})$. Namely, the goal is to compute

$\min\left\\{\sum_{i\in[k]}f(V_{i}):\ V_{1},V_{2},\ldots,V_{k}\text{ is a
partition of }V,\ V_{i}\neq\emptyset\;\forall i\in[k]\right\\}.$

Throughout, we will assume that the input submodular function is non-negative
and denote the size of the ground set $V$ by $n$. If $k=2$, then the problem
reduces to the classic submodular minimization problem. We emphasize that our
focus is on submodular $k$-partitioning when $k$ is part of input (see [4] for
a discussion of the problem for fixed constant $k$). Submodular $k$-partition
formulates several interesting partitioning problems and we will discuss some
of the special cases below. For arbitrary submodular functions, the problem is
NP-hard [9], does not admit a $(2-\epsilon)$-approximation assuming polynomial
number of function evaluation queries [22], does not admit a $n^{1/(\log\log
n)^{c}}$-approximation for every constant $c$ assuming the Exponential Time
Hypothesis [5], and the best approximation factor that is known is $O(k)$ [25,
18].

In this work, we will be interested in the submodular $k$-partition problem
for subfamilies of submodular functions—namely monotone, symmetric, and
posimodular submodular functions. A set function
$f:2^{V}\rightarrow\mathbb{R}$ is

  1. 1.

monotone if $f(B)\geq f(A)$ for every $A\subseteq B\subseteq V$,

  2. 2.

symmetric if $f(A)=f(V-A)$ for every $A\subseteq V$, and

  3. 3.

posimodular if $f(A)+f(B)\geq f(A-B)+f(B-A)$ for every $A,B\subseteq V$.

If the input submodular function is monotone/symmetric/posimodular, then we
call the associated submodular $k$-partition problem as
monotone/symmetric/posimodular submodular $k$-partition. We note that monotone
submodular functions and symmetric submodular functions are also
posimodular222In fact, monotone functions are posimodular since $f(A)\geq
f(A-B)$ and $f(B)\geq f(B-A)$ for every $A,B\subseteq V$. Symmetric submodular
functions are posimodular: for every $A,B\subseteq V$, we have that
$f(A)+f(B)=f(V-A)+f(B)\geq f((V-A)\cup B)+f((V-A)\cap
B)=f(V-(A-B))+f(B-A)=f(A-B)+f(B-A)$.. Hence, posimodular submodular
$k$-partition problem generalizes both monotone submodular $k$-partition and
symmetric submodular $k$-partition problems. We now discuss the approximation
status of symmetric/monotone/posimodular submodular $k$-partition and some of
their well-known special cases (see Table 1 for a summary of approximation
factors of symmetric/monotone/posimodular submodular $k$-partition achieved by
different approaches).

Monotone submodular $k$-partition. Special cases of monotone submodular
$k$-partition problem include matroid $k$-partition and coverage
$k$-partition—the submodular functions of interest here are matroid rank
functions and coverage functions respectively. Matroid $k$-partition captures
several interesting problems: e.g., (1) partition the columns of a given
matrix into $k$ non-empty parts to minimize the sum of the dimension of the
subspace spanned by the parts and (2) partition the edges of a given graph
into $k$ non-empty parts to _maximize_ the sum of the number of connected
components formed by the parts. Coverage $k$-partition also captures several
interesting problems: e.g., (3) partition the vertices of a given graph into
$k$ non-empty parts $V_{1},V_{2},\ldots,V_{k}$ in order to minimize
$\sum_{i=1}^{k}f(V_{i})$, where $f(P)$ is the number of edges incident to the
vertex subset $P\subseteq V$. To gain a better understanding of the difficulty
in solving/approximating monotone submodular $k$-partition, we encourage the
reader to briefly think about the concrete special case of matrix column
partitioning problem (i.e., problem (1) described above which is seemingly a
linear algebra problem) before reading further.

Monotone submodular $k$-partition is NP-hard [22]. Moreover, it admits a
simple (and fast) $(2-1/k)$-approximation algorithm that will be denoted
henceforth as the _cheapest singleton partitioning algorithm_ : return the
partition
$V_{1}:=\\{v_{1}\\},V_{2}:=\\{v_{2}\\},\ldots,V_{k-1}:=\\{v_{k-1}\\},V_{k}:=V-\\{v_{1},\ldots,v_{k-1}\\})$,
where the $n$ elements of the ground set are ordered as $v_{1},\ldots,v_{n}$
such that $f(\\{v_{1}\\})\leq f(\\{v_{2}\\})\leq\ldots\leq f(\\{v_{n}\\})$.
Santiago [22] showed that this is a $2$-approximation. His analysis can be
extended to show that it is in fact a $(2-1/k)$-approximation333The cheapest
singleton partitioning algorithm returns a solution whose cost is
$f(V-V_{k})+\sum_{i=1}^{k-1}f(\\{v_{i}\\})\leq
f(V)+\sum_{i=1}^{k-1}f(\\{v_{i}\\})\leq
f(V)+(1-1/k)\sum_{i=1}^{k}f(\\{v_{i}\\})\leq(2-1/k)\max\\{f(V),\sum_{i=1}^{k}f(\\{v_{i}\\})\\}$
while the cost of an optimum $k$-partition is at least
$\max\\{f(V),\sum_{i=1}^{k}f(\\{v_{i}\\})\\}$. The lower bound on the cost of
the optimum $k$-partition $V_{1}^{*},\ldots,V_{k}^{*}$ is because
$\sum_{i=1}^{k}f(V_{i}^{*})\geq f(V)$ by non-negativity and submodularity and
moreover, if the optimum partition is indexed such that
$\min\\{j\in[n]:v_{j}\in V_{i}^{*}\\}\leq\min\\{j\in[n]:v_{j}\in
V_{i+1}^{*}\\}$ for all $i\in[k-1]$, then $f(V_{i}^{*})\geq f(\\{v_{i}\\})$ by
monotonicity and hence,
$\sum_{i=1}^{k}f(V_{i}^{*})\geq\sum_{i=1}^{k}f(\\{v_{i}\\})$. and this is the
best possible approximation factor for this algorithm444The best possible
approximation factor for the cheapest singleton partitioning algorithm is
$2-1/k$ as seen from this example: Let $f$ be the rank function of a partition
matroid on a $k$-partition $\\{S_{1},\ldots,S_{k}\\}$ of the ground set $S$
where $|S_{i}|\geq 2$ for all $i\in[k]$. Then, the algorithm may return
$\\{\\{s_{1}\\},\\{s_{2}\\},\ldots,\\{s_{k-1}\\},S-\\{s_{1},\ldots,s_{k-1}\\}\\}$,
where $s_{i}\in S_{i}$ for all $i\in[k-1]$ and this $k$-partition has
objective value $2k-1$, whereas the partition $\\{S_{1},\ldots,S_{k}\\}$ has
objective value $k$.. Alternatively, the greedy splitting algorithm presented
in [25] achieves a $(2-2/k)$-approximation. On the inapproximability front,
Santiago [22] showed that there does not exist an algorithm that makes
polynomial number of function evaluation queries to obtain a
$(4/3-\epsilon)$-approximation for every constant $\epsilon>0$.

Symmetric submodular $k$-partition. Well-known special cases of symmetric
submodular $k$-partition problem are graph $k$-cut and hypergraph
$k$-partition—the submodular functions of interest here are the cut functions
of an explicitly given graph and hypergraph respectively. Graph $k$-cut is NP-
complete [9] and does not have a polynomial-time $(2-\epsilon)$-approximation
for every constant $\epsilon>0$ under the Small Set Expansion Hypothesis [11].
There are several known approaches to achieve a $2$-approximation for graph
$k$-cut—(i) greedy splitting approach [23], (ii) Gomory-Hu tree based approach
[24], (iii) extreme sets based approach [12], (iv) principal partition
sequence based approach [17, 2, 21], and (v) covering-LP based approach [14,
6, 20]. Greedy splitting, Gomory-Hu tree, and extreme sets based approaches
lead to a $(2-2/k)$-approximation while the principal partition sequence and
the covering-LP based approaches lead to a $(2-2/n)$-approximation for graph
$k$-cut. The principal partition sequence and the covering-LP based approaches
for graph $k$-cut have also been shown to be related to each other [6]. The
principal partition sequence based approach is the main algorithm of interest
to our work and we will discuss it in detail in Section 2.

For the more general problem of symmetric submodular $k$-partition, two of the
approaches discussed in the previous paragraph for graph $k$-cut have been
generalized to obtain $2$-approximations—the greedy splitting approach [25]
and the Gomory-Hu tree approach lead to a $(2-2/k)$-approximation. Analyzing
the approximation factor of the principal partition sequence based approach
for symmetric submodular $k$-partition was one of the driving motivations of
our work. On the inapproximability front, Santiago [22] showed that there does
not exist an algorithm that makes polynomial number of function evaluation
queries to obtain a $(2-\epsilon)$-approximation for every constant
$\epsilon>0$.

Posimodular submodular $k$-partition. The only natural family of posimodular
submodular functions that we are familiar with are symmetric submodular
functions and monotone submodular functions as well as their positive linear
combinations. As mentioned before, posimodular submodular $k$-partition is a
unified generalization of symmetric submodular $k$-partition and monotone
submodular $k$-partition. To the best of authors’ knowledge, posimodular
submodular $k$-partition has not been studied in the literature before and
there are no specialized algorithms or approximation factor analysis of
existing algorithms for posimodular submodular $k$-partition. A slight
modification to the analysis of the greedy splitting algorithm presented in
[25] shows that their algorithm achieves a $(3-2/k)$-approximation for
posimodular submodular $k$-partition—we refrain from presenting this analysis
in the interests of brevity. On the inapproximability front, since symmetric
submodular functions are also posimodular submodular, the lower bound for
symmetric submodular $k$-partition also holds for posimodular submodular
$k$-partition, i.e., there does not exist an algorithm for posimodular
submodular $k$-partition that makes polynomial number of function evaluation
queries to obtain a $(2-\epsilon)$-approximation for every constant
$\epsilon>0$.

###  1.1 Our Results

In this work, we investigate Narayanan, Roy, and Patkar’s [17] principal
partition sequence based algorithm for submodular $k$-partition. They showed
that their algorithm achieves a $2$-approximation for graph $k$-cut (which was
subsequently rediscovered by Ravi and Sinha [21]). We show the following
results:

  1. 1.

Their algorithm achieves a $4/3$-approximation for monotone submodular
$k$-partition. This result improves on the $2$-factor that is known to be
achievable via two different algorithms: the cheapest singleton partitioning
algorithm and the greedy splitting algorithm. Moreover, our upper bound of
$4/3$ matches the lower bound shown by Santiago [22]. We will discuss the
significance of our upper bound result shortly.

  2. 2.

Their algorithm achieves a $2$-approximation for symmetric submodular
$k$-partition. This factor matches the $2$-factor that is known to be
achievable via two other algorithms: the greedy splitting algorithm and the
Gomory-Hu tree based algorithm, and also matches the lower bound [11, 22]. Our
contribution here is generalizing the analysis of [17, 21] to beyond graph cut
functions.

  3. 3.

Their algorithm achieves a $2$-approximation for posimodular submodular
$k$-partition. This result improves on the $3$-factor that is known to be
achievable via the greedy splitting algorithm and matches the lower bound of
$2$ shown by Santiago [22].

See Table 1 for a comparison. Graph $k$-cut is the well-studied special case
of symmetric submodular $k$-partition/posimodular submodular $k$-partition, so
we include that as the last column in the table for comparison. Approximation
factors in the row corresponding to principal partition sequence are the main
results of our work. In the last row of the table, we include the known lower
bounds on the approximation factor for comparison. The lower bound for graph
cut function is assuming the Small Set Expansion Hypothesis [11] while the
rest of the lower bounds are assuming polynomial number of function evaluation
queries. Dashes in the table indicate that either the approach does not extend
or there has been no analysis of the approximation factor of the approach for
the subfamily.

We complement our upper bounds on the approximation factor of their algorithm
with matching lower bound constructions for each subfamily of submodular
functions. Our results show that the principal partition sequence based
algorithm achieves the best possible approximation factor for broad
subfamilies of submodular functions, thus illustrating the power and
applicability of this algorithm. On the other hand, we show that the
approximation factor of their algorithm for arbitrary submodular functions is
$\Omega(n/k)$ via a lower bound construction. This construction shows that
their principal partition sequence based algorithm cannot directly improve the
approximation factor for submodular $k$-partition beyond the current best
$O(k)$.

We briefly discuss the significance of our $4/3$-approximation result for
monotone submodular $k$-partition. Firstly, prior to our results, there were
no known families of submodular functions for which the submodular
$k$-partition problem could be approximated to a factor better than $2$. Our
result for monotone submodular functions breaks this $2$-factor barrier for a
broad family of submodular functions. Secondly, our result for monotone
submodular $k$-partition leads to a new approximation result even for a graph
partitioning problem that we describe now. For a graph $G=(V,E)$ with edge
weights $w:E\rightarrow\mathbb{R}_{+}$, consider functions
$d,f:2^{V}\rightarrow\mathbb{R}_{+}$ defined by $d(S):=w(\delta(S))$ and
$f(S):=w(E[S])+w(\delta(S))$ for every $S\subseteq V$, where $\delta(S)$
denotes the set of edges with exactly one end-vertex in $S$, $E[S]$ denotes
the set of edges with both end-vertices in $S$, and $w(F):=\sum_{e\in F}w(e)$
for every $F\subseteq E$. The function $d$ is the cut function of the graph
and is symmetric submodular. The function $f$ is the coverage function of the
graph and is monotone submodular. Submodular $k$-partition for the function
$d$ is known as graph $k$-cut and it is known that graph $k$-cut does not
admit a $(2-\epsilon)$-approximation under the Small Set Expansion Hypothesis
[11]. In contrast, our results show that coverage $k$-partition in
graphs—i.e., submodular $k$-partition for the function $f$—admits a
$4/3$-approximation. We note that coverage $k$-partition in graphs is NP-hard
[22] and its approximability is an intriguing open question.

| Monotone | Symmetric | Posimodular | Graph
---|---|---|---|---
| Submodular | Submodular | Submodular | Cut Function
| Function | Function | Function |
Greedy splitting |  $2-2/k$ [25] |  $2-2/k$ [25] |  $3-2/k$ [25]* |  $2-2/k$ [23]
Extreme Sets | — | — | — |  $2-2/k$ [12]
Gomory-Hu tree | — |  $2-2/k$ [Folklore] | — |  $2-2/k$ [24]
Covering-LP | — | — | — |  $2-2/k$ [14, 6]
Cheapest Singleton |  $2-1/k$ [22] | — | — | —
Partitioning |  |  |  |
Principal Partition | $4/3-4/(9n+3)$ | $2-2/n$ | $2-2/(n+1)$ |  $2-2/n$ [17, 21]
Sequence | (Theorem 3.1) | (Theorem 3.2) | (Theorem 3.3) |
Lower Bound |  $4/3-\epsilon$ [22] |  $2-\epsilon$ [22] |  $2-\epsilon$ [22] |  $2-\epsilon$ [11]
Table 1: Approximation factors of symmetric/monotone/posimodular submodular
$k$-partition using different approaches. Result in the first row marked with
an asterisk follows by slight modifications to the known analysis of the
approximation factor for symmetric submodular functions given in [25].

Organization. We discuss the principal partition sequence based algorithm in
Section 2. We analyze the approximation factor of the algorithm with matching
lower bound constructions for each of the three subfamilies of submodular
functions in Section 3. We exhibit an instance of submodular $k$-partition
where the algorithm achieves an approximation factor of $\Omega(n/k)$ in
Section 4.

###  1.2 Related work

The principal partition sequence based algorithm for submodular $k$-partition
was introduced by Narayanan, Roy, and Patkar [17]. We will formally define the
principal partition sequence of a submodular function and describe their
algorithm in Section 2. They analyzed the approximation factor of their
algorithm for two variants of $k$-partitioning problems in hypergraphs. These
two variants are not special cases of symmetric/monotone/posimodular
submodular $k$-partition and are not of direct interest to our work. However,
we describe these variants to highlight the versatility of the principal
partition sequence based approach and also to shed light on the results of
Narayanan, Roy, and Patkar’s work which do not seem to be well-known in the
literature. Given a hypergraph $H=(V,E)$, a hyperedge cost function
$c:E\to\mathbb{R}_{+}$, and an integer $k$, the goal is to find a partition
$\mathcal{P}:=\\{V_{1},V_{2},\ldots,V_{k}\\}$ of $V$ into $k$ non-empty parts
that minimizes an objective of interest:

  1. 1.

If the objective is the sum of cost of hyperedges that intersect at least two
parts of $\mathcal{P}$, then the problem is known as _hypergraph $k$-cut_.

  2. 2.

If the objective is the sum of _cost of hyperedges relative to the partition
$\mathcal{P}$_, where the cost of a hyperedge $e$ relative to $\mathcal{P}$ is
$c(e)(\ell-1)$ with $\ell$ being the number of parts of $\mathcal{P}$
intersected by $e$, then the problem is known as _normalized coverage
$k$-partition_555We introduce this nomenclature because the problem is
equivalent to finding a partition $V_{1},V_{2},\ldots,V_{k}$ of the ground set
$V$ in order to minimize $\sum_{i=1}^{k}f(V_{i})-f(V)$, where
$f:2^{V}\rightarrow\mathbb{R}_{+}$ is an explicitly given coverage function
(every coverage function can be uniquely represented using a hypergraph [3]).
We consider the subtraction of $f(V)$ as normalizing the objective since it is
a trivial lower bound on the sum of the function values of the parts:
$\sum_{i=1}^{k}f(V_{i})\geq f(V)$ holds for every $k$-partition
$V_{1},V_{2},\ldots,V_{k}$ since $f$ is a coverage function..

Narayanan, Roy, and Patkar [17] showed that their principal partition sequence
based algorithm achieves a $r(1-1/n)$-approximation for hypergraph $k$-cut,
where $r$ is the size of the largest hyperedge and $n$ is the number of
vertices in the input hypergraph, and achieves a $(2-2/n)$-approximation for
normalized coverage $k$-partition. A consequence (of both of their results) is
that the principal partition sequence based algorithm achieves a
$(2-2/n)$-approximation for graph $k$-cut. Their principal partition sequence
based algorithm for graph $k$-cut is equivalent to the Lagrangean relaxation
approach suggested by Barahona [2]. The approximation factor of the principal
partition sequence based algorithm for graph $k$-cut being at most $2$ was
rediscovered by Ravi and Sinha [21] and for hypergraph $k$-cut being at most
$r$ was rediscovered by Baïou and Barahona [1].

We mention that a slight modification to the analysis of the greedy splitting
algorithm presented in [25] shows that the greedy splitting algorithm achieves
a $(2-2/k)$-approximation for normalized coverage $k$-partition and hypergraph
$k$-partition. We note that hypergraph $k$-partition is a special case of
symmetric submodular $k$-partition and is different from hypergraph $k$-cut
(for definition of hypergraph $k$-partition, see discussion of symmetric
submodular $k$-partition at the beginning of the introduction). On the
inapproximability front, it is known that hypergraph $k$-cut does not admit an
approximation factor of $n^{1/(\log\log n)^{c}}$, where $c$ is a constant,
assuming the Exponential Time Hypothesis [5]. The best inapproximability
result for the more general submodular $k$-partition problem (mentioned in the
introduction) follows from this inapproximability for hypergraph $k$-cut.

##  2 Principal partition sequence based algorithm

In this section, we recall the principal partition sequence based algorithm
for submodular $k$-partition designed by Narayanan, Roy, and Patkar [17]. We
begin with some notation. Throughout this work, a _partition_ of a set $S$ is
defined to be a collection of _nonempty_ pairwise disjoint subsets of $S$
whose union is $S$, and a _$k$ -partition_ of a set $S$ is defined to be a
partition of $S$ with exactly $k$ parts. For two distinct partitions
$\mathcal{P}$ and $\mathcal{Q}$ of a set $S$, if every part of $\mathcal{Q}$
is completely contained in some part of $\mathcal{P}$ then we say that
$\mathcal{Q}$ _refines_ $\mathcal{P}$ (equivalently, $\mathcal{P}$ is a
coarsening of $\mathcal{Q}$). For two distinct partitions $\mathcal{P}$ and
$\mathcal{Q}$ of a set $S$, we will say that $\mathcal{Q}$ is obtained from
$\mathcal{P}$ by refining only one part of $\mathcal{P}$ if there exists a
part $P\in\mathcal{P}$ such that $P\notin\mathcal{Q}$ and every part
$Q\in\mathcal{Q}$ satisfies either $Q\subsetneq P$ or $Q\in\mathcal{P}$ (i.e.,
either $Q$ is a proper subset of the part $P$ or $Q$ is a part of the
partition $\mathcal{P}$); we will denote such a part $P\in\mathcal{P}$ as the
part refined by $\mathcal{Q}$.

Let $f:2^{V}\to\mathbb{R}$ be a set function on ground set $V$. For a
collection $\mathcal{P}$ of subsets of $V$, we write
$f(\mathcal{P}):=\sum_{P\in\mathcal{P}}f(P)$. We will say that a partition
$\mathcal{P}=\\{P_{1},\ldots,P_{k}\\}$ is an optimal $k$-partition if
$f(\mathcal{P})\leq f(\mathcal{Q})$ for every $k$-partition $\mathcal{Q}$ of
$V$. We define the function $g_{f,\mathcal{P}}:\mathbb{R}_{\geq
0}\to\mathbb{R}$ for a partition $\mathcal{P}$ of the ground set $V$ and the
function $g_{f}:\mathbb{R}_{\geq 0}\to\mathbb{R}$ as follows:

$\displaystyle g_{f,\mathcal{P}}(b)$
$\displaystyle:=f(\mathcal{P})-b|\mathcal{P}|\text{ and}$ $\displaystyle
g_{f}(b)$ $\displaystyle:=\min\\{g_{f,\mathcal{P}}(b):\mathcal{P}\text{ is a
partition of }V\\}.$

We drop the subscript $f$ and instead write $g_{\mathcal{P}}$ and $g$
respectively, if the function $f$ is clear from context. By definition, the
function $g_{f}$ is piece-wise linear. It can be shown that $g_{f}$ has at
most $|V|-1$ breakpoints. The next theorem shows that if the function
$f:2^{V}\rightarrow\mathbb{R}$ is submodular, then there exists a sequence of
partitions achieving the $g_{f}$ function values at the breakpoints that have
a nice structure; moreover, the breakpoints and such a sequence of partitions
can be computed in polynomial time given access to the evaluation oracle of
the submodular function $f$. We emphasize that the theorem holds for arbitrary
submodular functions (which may not be non-negative valued).

######  Theorem 2.1 ([15, 17]).

Let $f:2^{V}\to\mathbb{R}$ be a submodular function on a ground set $V$. Then,
there exists a sequence
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ of partitions of $V$
and values $b_{1},b_{2},\ldots,b_{r-1}$ such that

  1. 1.

$\mathcal{P}_{1}=\\{V\\}$ and $\mathcal{P}_{r}=\\{\\{v\\}:v\in V\\}$,

  2. 2.

For each $j\in[r-1]$, the partition $\mathcal{P}_{j+1}$ is obtained from
$\mathcal{P}_{j}$ by refining only one part of $\mathcal{P}_{j}$,

  3. 3.

$b_{1}<b_{2}<\ldots<b_{r-1}$,

  4. 4.

$g(b_{j})=g_{\mathcal{P}_{j}}(b_{j})=g_{\mathcal{P}_{j+1}}(b_{j})$ for each
$j\in[r-1]$ and

  5. 5.

$g(b)=g_{\mathcal{P}_{1}}(b)$ for all $b\in(-\infty,b_{1}]$,
$g(b)=g_{\mathcal{P}_{j+1}}(b)$ for all $b\in[b_{j},b_{j+1}]$ for each
$j\in[r-2]$, and
$g(b)=g_{\mathcal{P}_{r}}(b)$ for all $b\in[b_{r-1},\infty)$.

Moreover, such a sequence
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ of partitions of $V$
and values $b_{1},b_{2},\ldots,b_{r-1}$ can be computed in polynomial time
given access to the evaluation oracle of the submodular function $f$.

For a submodular function $f:2^{V}\rightarrow\mathbb{R}$, we will denote a
sequence of partitions
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ and the sequence of
values $b_{1},b_{2},\ldots,b_{r-1}$ satisfying the conditions given in Theorem
2.1 as a _principal partition sequence_ and the _critical value sequence_ of
$f$, respectively. We note that this definition differs from those in [15, 17]
owing to the reversed indexing order and the imposition of condition 2—we note
that the proofs given in those papers also show that condition 2 holds (also
see [21]). The principal partition sequence of submodular functions is known
in the literature as _principal lattice of partitions_ of submodular functions
since there exists a lattice structure associated with the sequence of
partitions. We choose to call it as principal partition sequence in this work
since the sequence suffices for our purpose. For more on principal lattice of
partitions of submodular functions and their computation, we refer the reader
to [7, 15, 17, 16, 8, 19, 2, 10, 13].

We now discuss the principal partition sequence based algorithm for submodular
$k$-partition that was proposed by Narayanan, Roy, and Patkar [17]. This
algorithm computes a principal partition sequence satisfying all conditions in
Theorem 2.1. If the sequence contains a partition that has exactly $k$ parts,
then the algorithm returns this $k$-partition. Otherwise, the algorithm
returns a $k$-partition obtained by refining the partition in the sequence
that has the largest number of parts that is less than $k$. The refinement is
based on the partition in the sequence that has the fewest number of parts
that is more than $k$. The formal description of the refinement is given in
Algorithm 1. Since the sequence
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ satisfying the
conditions of Theorem 2.1 can be computed in polynomial time, Algorithm 1 can
indeed be implemented to run in polynomial time. By design, the algorithm
returns a $k$-partition. The remainder of this work will focus on analyzing
the approximation factor of the algorithm.

Input: A submodular function $f:2^{V}\to\mathbb{R}$ given by evaluation
oracles and an integer $k\geq 2$.

Output: A $k$-partition $\mathcal{P}$ of $V$.

Use Theorem 2.1 to compute a principal partition sequence
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ of the submodular
function $f$ satisfying all conditions stated in that theorem.

if $|\mathcal{P}_{j}|=k$ for some $j\in[r]$ then

Return $\mathcal{P}:=\mathcal{P}_{j}$.

end if

Let $i\in\\{2,3,\ldots,r\\}$ so that
$|\mathcal{P}_{i-1}|<k<|\mathcal{P}_{i}|$.

Let $S\in\mathcal{P}_{i-1}$ be the part refined by $\mathcal{P}_{i}$ and
$\mathcal{P}^{\prime}$ be the parts of $\mathcal{P}_{i}$ contained in $S$.

Let $\mathcal{P}^{\prime}=\\{B_{1},\ldots,B_{|\mathcal{P}^{\prime}|}\\}$ such
that $f(B_{1})\leq f(B_{2})\leq\ldots\leq f(B_{|\mathcal{P}^{\prime}|})$.

Return
$\mathcal{P}:=(\mathcal{P}_{i-1}\backslash\\{S\\})\cup\left\\{B_{1},B_{2},\ldots,B_{k-|\mathcal{P}_{i-1}|}\right\\}\cup\left\\{\bigcup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\right\\}$.

Algorithm 1 Principal partition sequence based algorithm for submodular
$k$-partition

To construct examples that exhibit tight lower bound on the approximation
factor of Algorithm 1, we will need the following proposition that identifies
a special case under which the principal partition is unique and consists only
of two partitions—namely, the partition into singletons and the partition that
consists of only one part.

######  Proposition 2.1.

Let $f:2^{V}\rightarrow\mathbb{R}_{\geq 0}$ be a non-negative submodular
function. Suppose that for every partition
$\mathcal{P}\neq\mathcal{Q},\\{V\\}$ where $\mathcal{Q}:=\\{\\{v\\}:v\in
V\\}$, the function $f$ satisfies

$\frac{f(\mathcal{P})-f(V)}{|\mathcal{P}|-1}>\frac{f(\mathcal{Q})-f(V)}{|V|-1}.$

Then, the principal partition sequence of $f$ is $\\{V\\},\mathcal{Q}$.

###### Proof.

Let $n:=|V|$. It suffices to show that for every partition $\mathcal{P}$ of
$V$ such that $\mathcal{P}\neq\\{V\\},\mathcal{Q}$, we have that

$\displaystyle
f(\mathcal{P})-b|\mathcal{P}|>\min\\{f(V)-b,f(\mathcal{Q})-b\cdot
n\\}\quad\forall b\in\mathbb{R}$ (1)

This suffices since it ensures that no partitions other than $\\{V\\}$ and
$\mathcal{Q}$ satisfy conditions 4 and 5 in Theorem 2.1. By the hypothesis, we
have

$\frac{f(\mathcal{P})-f(V)}{|\mathcal{P}|-1}>\frac{f(\mathcal{Q})-f(V)}{n-1},$

which is equivalent to

$\displaystyle f(\mathcal{P})-b^{\prime}|\mathcal{P}|>f(V)-b^{\prime},$ (2)

where $b^{\prime}=(f(\mathcal{Q})-f(V))/(n-1)$ for every partition
$\mathcal{P}\neq\\{V\\},\mathcal{Q}$. Now, suppose inequality (1) fails for
some partition $\mathcal{P}$ and some $b\in\mathbb{R}$, then

$\displaystyle f(\mathcal{P})-b|\mathcal{P}|\leq f(V)-b\text{ and }$ (3)
$\displaystyle f(\mathcal{P})-b|\mathcal{P}|\leq f(\mathcal{Q})-bn.$ (4)

Consequently, we have that

$\displaystyle(b-b^{\prime})|\mathcal{P}|$
$\displaystyle=(f(\mathcal{P})-b^{\prime}|\mathcal{P}|)-(f(\mathcal{P})-b|\mathcal{P}|)$
$\displaystyle>(f(V)-b^{\prime})-(f(\mathcal{P})-b|\mathcal{P}|)\quad\quad\text{(using
inequality \eqref{eqn: 4/3 tight example - 2})}$
$\displaystyle\geq(f(V)-b^{\prime})-(f(V)-b)\quad\quad\text{(using inequality
\eqref{eqn: 4/3 tight example - 3})}$ $\displaystyle=b-b^{\prime}.$

This implies $b-b^{\prime}>0$. Moreover, we also have that

$\displaystyle(b-b^{\prime})|\mathcal{P}|$
$\displaystyle=(f(\mathcal{P})-b^{\prime}|\mathcal{P}|)-(f(\mathcal{P})-b|\mathcal{P}|)$
$\displaystyle>(f(V)-b^{\prime})-(f(\mathcal{P})-b|\mathcal{P}|)\quad\quad\text{(using
inequality \eqref{eqn: 4/3 tight example - 2})}$
$\displaystyle\geq(f(V)-b^{\prime})-(f(\mathcal{Q})-bn)\quad\quad\text{(using
inequality \eqref{eqn: 4/3 tight example - 4})}$
$\displaystyle=(f(\mathcal{Q})-b^{\prime}n)-(f(\mathcal{Q})-bn)\quad\quad(\text{by
definition of }b^{\prime})$ $\displaystyle=(b-b^{\prime})n.$

Since $b-b^{\prime}>0$, it follows that $|\mathcal{P}|>n$, which is a
contradiction to the fact that $\mathcal{P}$ is a partition of $V$. Therefore,
inequality (1) holds by contradiction. ∎

##  3 Approximation factor analysis

In this section, we analyze the approximation factor of Algorithm 1 for
various subfamilies of submodular functions. We state and prove certain lemmas
that will be useful for all submodular functions (Lemmas 3.1 and 3.2). We
analyze the approximation factor of Algorithm 1 for monotone submodular
functions in Section 3.1, for symmetric submodular functions in Section 3.2,
and for posimodular submodular functions in Section 3.3. We conclude each
subsection with a remark on the tightness of the approximation factor for the
algorithm.

Our first lemma identifies a special case in which Algorithm 1 returns an
optimum $k$-partition. This special case was also identified by Narayanan,
Roy, and Patkar. We note that the following lemma holds for arbitrary
submodular functions (which may not be non-negative).

######  Lemma 3.1 ([17]).

Let $k\geq 2$ be an integer, $f:2^{V}\to\mathbb{R}$ be a submodular function
on a ground set $V$, and
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ be a principal
partition sequence of the submodular function $f$ satisfying the conditions of
Theorem 2.1. If there exists $j\in[r]$ such that $|\mathcal{P}_{j}|=k$, then
$\mathcal{P}_{j}$ is an optimal $k$-partition.

###### Proof.

Let $\mathcal{P}^{\ast}$ be a $k$-partition of $V$ that minimizes
$f(\mathcal{P}^{\ast})$ and let $b_{j}$ be the value where
$g(b_{j})=g_{\mathcal{P}_{j}}(b_{j})$. Then,

$f(\mathcal{P}^{\ast})-b_{j}\cdot k=g_{\mathcal{P}^{\ast}}(b_{j})\geq
g(b_{j})=g_{\mathcal{P}_{j}}(b_{j})=f(\mathcal{P}_{j})-b_{j}|\mathcal{P}_{j}|=f(\mathcal{P}_{j})-b_{j}\cdot
k,$

and hence, $f(\mathcal{P}^{\ast})\geq f(\mathcal{P}_{j})$. Therefore,
$\mathcal{P}_{j}$ is indeed an optimal $k$-partition. ∎

In order to address the case where there is no $j\in[r]$ such that
$|\mathcal{P}_{j}|=k$, we need the following lemma that shows two lower bounds
on the optimum value. The first lower bound in the lemma holds for arbitrary
submodular functions (which may not be non-negative) while the second lower
bound holds for non-negative submodular functions.

######  Lemma 3.2.

Let $k\geq 2$ be an integer, $f:2^{V}\to\mathbb{R}$ be a submodular function
on a ground set $V$, $\mathcal{P}^{\ast}$ be a $k$-partition of $V$ that
minimizes $f(\mathcal{P}^{\ast})$, and
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ be a principal
partition sequence of the submodular function $f$ satisfying the conditions of
Theorem 2.1. Suppose $|\mathcal{P}_{j}|\neq k$ for all $j\in[r]$. Let
$\mathcal{P}_{i-1},\mathcal{P}_{i}$ be the partitions such that
$|\mathcal{P}_{i-1}|<k<|\mathcal{P}_{i}|$. Then,

  1. (i)

$f(\mathcal{P}^{\ast})\geq\frac{|\mathcal{P}_{i}|-k}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}f(\mathcal{P}_{i-1})+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}f(\mathcal{P}_{i})$
and

  2. (ii)

$f(\mathcal{P}^{\ast})\geq f(\mathcal{P}_{i-1})$ if $f$ is non-negative.

###### Proof.

We prove the two lower bounds below.

  1. (i)

Let $b_{i-1}$ be the value such that
$g_{\mathcal{P}_{i-1}}(b_{i-1})=g_{\mathcal{P}_{i}}(b_{i-1})$. Then, we have

$\displaystyle
f(\mathcal{P}_{i-1})-b_{i-1}|\mathcal{P}_{i-1}|=f(\mathcal{P}_{i})-b_{i-1}|\mathcal{P}_{i}|\implies
b_{i-1}=\frac{f(\mathcal{P}_{i})-f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}.$
(5)

By condition 4 of Theorem 2.1, we also have

$\displaystyle f(\mathcal{P}^{\ast})-b_{i-1}\cdot k$
$\displaystyle=g_{\mathcal{P}^{\ast}}(b_{i-1})\geq
g(b_{i-1})=g_{\mathcal{P}_{i}}(b_{i-1})=f(\mathcal{P}_{i})-b_{i-1}|\mathcal{P}_{i}|$
$\displaystyle\implies f(\mathcal{P}^{\ast})\geq
f(\mathcal{P}_{i})+b_{i-1}(k-|\mathcal{P}_{i}|).$ (6)

Combining (5) and (6), we get

$\displaystyle f(\mathcal{P}^{\ast})$ $\displaystyle\geq
f(\mathcal{P}_{i})+\frac{f(\mathcal{P}_{i})-f(\mathcal{P}_{i-1})}{|P_{i}|-|P_{i-1}|}(k-|\mathcal{P}_{i}|)$
$\displaystyle=\frac{|\mathcal{P}_{i}|-k}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}f(\mathcal{P}_{i-1})+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}f(\mathcal{P}_{i}).$

  2. (ii)

Let $P_{1}^{*},\ldots,P_{k}^{*}$ be the parts of $\mathcal{P}^{\ast}$ (in
arbitrary order). Let $k^{\prime}:=|\mathcal{P}_{i-1}|$. We know that
$k^{\prime}<k$. Consider the $k^{\prime}$-partition $\mathcal{Q}$ obtained as
$Q_{1}:=P_{1}^{*},Q_{2}:=P_{2}^{*},\ldots,Q_{k^{\prime}-1}:=P_{k^{\prime}-1}^{*},Q_{k^{\prime}}:=\cup_{j=k^{\prime}}^{k}P_{j}^{*}$.
Then,

$f(\mathcal{P}^{\ast})=\sum_{i=1}^{k}f(P_{i}^{*})\geq\left(\sum_{i=1}^{k^{\prime}-1}f(P_{i}^{*})\right)+f(\cup_{j=k^{\prime}}^{k}P_{j}^{*})=\sum_{i=1}^{k^{\prime}}f(Q_{i})=f(\mathcal{Q}).$

The inequality above is due to submodularity and non-negativity. The partition
$\mathcal{Q}$ is a $k^{\prime}$-partition. By Lemma 3.1, the partition
$\mathcal{P}_{i-1}$ is an optimal $k^{\prime}$-partition. Hence,

$f(\mathcal{Q})\geq f(\mathcal{P}_{i-1}).$

The above two inequalities together imply that $f(\mathcal{P}^{\ast})\geq
f(\mathcal{P}_{i-1})$.

∎

###  3.1 Monotone submodular functions

In this section, we bound the approximation factor of Algorithm 1 for monotone
submodular $k$-partitioning. The following is the main theorem of this
section.

######  Theorem 3.1.

The approximation factor of Algorithm 1 for non-negative monotone submodular
$k$-partitioning is $\frac{4}{3}-\frac{4}{9n+3}$, where $n$ is the size of the
ground set.

The asymptotic approximation factor of $4/3$ achieved by Algorithm 1 is the
best possible for non-negative monotone submodular $k$-partition: for every
constant $\epsilon>0$, there does not exist an algorithm that achieves a
$(4/3-\epsilon)$-approximation using polynomial number of function evaluation
queries [22]. We will also exhibit examples to show the tightness of the
approximation factor for Algorithm 1 after proving the theorem. The proof of
Theorem 3.1 follows from Lemma 3.1 and Lemma 3.3 shown below.

######  Lemma 3.3.

Let $k\geq 2$ be an integer, $f:2^{V}\to\mathbb{R}_{\geq 0}$ be a non-negative
monotone submodular function on a ground set $V$ of size $n$,
$\mathcal{P}^{\ast}$ be a $k$-partition of $V$ that minimizes
$f(\mathcal{P}^{\ast})$, and
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ be a principal
partition sequence of the submodular function $f$ satisfying the conditions of
Theorem 2.1. Suppose $|\mathcal{P}_{j}|\neq k$ for all $j\in[r]$. Then, the
partition $\mathcal{P}$ returned by Algorithm 1 satisfies

$f(\mathcal{P})\leq\left(\frac{4}{3}-\frac{4}{9n+3}\right)f(\mathcal{P}^{\ast}).$

###### Proof.

Let $\mathcal{P}_{i-1},\mathcal{P}_{i}$ be the partitions such that
$|\mathcal{P}_{i-1}|<k<|\mathcal{P}_{i}|$. Let $S$ and
$\mathcal{P}^{\prime}=\\{B_{1},B_{2},\ldots,B_{|\mathcal{P}^{\prime}|}\\}$ be
as in Algorithm 1.

Firstly, since
$\cup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\subseteq S$
and $f$ is monotone, we have that

$f\left(\cup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\right)\leq
f(S).$

Secondly, by our choice of $B_{1},B_{2},\ldots,B_{k-|\mathcal{P}_{i-1}|}$, we
know that

$\displaystyle\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})\leq\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime}).$

Hence,

$\displaystyle f(\mathcal{P})$
$\displaystyle=f(\mathcal{P}_{i-1})-f(S)+\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})+f\left(\bigcup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\right)$
$\displaystyle\leq
f(\mathcal{P}_{i-1})+\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})$
$\displaystyle\leq
f(\mathcal{P}_{i-1})+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime})$
$\displaystyle=f(\mathcal{P}_{i-1})+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(f(\mathcal{P}_{i})+f(S)-f(\mathcal{P}_{i-1})),$

where the last equality follows from the fact that
$f(\mathcal{P}_{i-1})-f(S)+f(\mathcal{P}^{\prime})=f(\mathcal{P}_{i})$ and
$|\mathcal{P}^{\prime}|=|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1$. Rearranging,
we have that

$\displaystyle f(\mathcal{P})$
$\displaystyle\leq\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(|\mathcal{P}_{i}|-k+1)+\frac{f(\mathcal{P}_{i})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(k-|\mathcal{P}_{i-1}|)$
$\displaystyle\quad\quad\quad\quad+\frac{f(S)}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(k-|\mathcal{P}_{i-1}|)$
$\displaystyle=\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(|\mathcal{P}_{i}|-k+1)+\frac{f(\mathcal{P}_{i})+f(S)}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(k-|\mathcal{P}_{i-1}|)\right)$
$\displaystyle\leq\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(f(\mathcal{P}^{\ast})+\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}+\frac{f(S)}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(k-|\mathcal{P}_{i-1}|)\right)$
$\displaystyle\leq\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(f(\mathcal{P}^{\ast})+\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(1+k-|\mathcal{P}_{i-1}|)\right).$
(7)

where the second inequality above is by by Lemma 3.2(i) and the third
inequality above is because $f(S)\leq f(\mathcal{P}_{i-1})$. Inequality (7)
implies that

$\displaystyle f(\mathcal{P})$
$\displaystyle\leq\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(f(\mathcal{P}^{\ast})+f(\mathcal{P}_{i-1})+\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(1+k-|\mathcal{P}_{i}|)\right)$
$\displaystyle\leq\left(1-\frac{1}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(f(\mathcal{P}^{\ast})+f(\mathcal{P}_{i-1})\right)\quad(\text{since
}k<|\mathcal{P}_{i}|)$ $\displaystyle\leq 2f(\mathcal{P}^{\ast}),$

where the last inequality is because $f(\mathcal{P}_{i-1})\leq
f(\mathcal{P}^{\ast})$ by Lemma 3.2(ii). The above analysis shows that the
approximation factor is at most $2$. We tighten the analysis now. As a
consequence of the above inequality, we may assume that
$f(\mathcal{P}^{\ast})\neq 0$ because if $f(\mathcal{P}^{\ast})=0$, then the
returned $k$-partition $\mathcal{P}$ also satisfies $f(\mathcal{P})=0$ and
thus, is optimal. Let $c:=f(\mathcal{P}_{i-1})/f(\mathcal{P}^{\ast})$. By
Lemma 3.2(ii), we have that $f(\mathcal{P}_{i-1})\leq f(\mathcal{P}^{\ast})$
and hence, $c\in[0,1]$. For convenience, we define $A:=k-|\mathcal{P}_{i-1}|$
and $B:=|\mathcal{P}_{i}|-k$ and note that $A,B\geq 1$. Using this notation,
we may rewrite inequality (7) as

$\displaystyle f(\mathcal{P})$
$\displaystyle\leq\left(\frac{A+B}{A+B+1}\right)\left(f(\mathcal{P}^{\ast})+\frac{1+A}{A+B}f(\mathcal{P}_{i-1})\right)$
$\displaystyle=\left(\frac{A+B}{A+B+1}\right)\left(1+\frac{1+A}{A+B}\cdot
c\right)f(\mathcal{P}^{\ast}).$ (8)

By Lemma 3.2(i), we have

$f(\mathcal{P}^{\ast})\geq\left(\frac{B}{A+B}\right)f(\mathcal{P}_{i-1})+\left(\frac{A}{A+B}\right)f(\mathcal{P}_{i})=\left(\frac{B}{A+B}\right)cf(\mathcal{P}^{\ast})+\left(\frac{A}{A+B}\right)f(\mathcal{P}_{i}).$

Rearranging, we have

$f(\mathcal{P}_{i})\leq\left(1-\frac{B}{A+B}\cdot
c\right)\left(\frac{A+B}{A}\right)f(\mathcal{P}^{\ast})=\left(\frac{A+B}{A}-\frac{B}{A}\cdot
c\right)f(\mathcal{P}^{\ast}).$

Since $\mathcal{P}$ is obtained by coarsening $\mathcal{P}_{i}$, we have
$f(\mathcal{P})\leq f(\mathcal{P}_{i})$ by submodularity and non-negativity of
$f$. This implies

$\displaystyle f(\mathcal{P})\leq\left(\frac{A+B}{A}-\frac{B}{A}\cdot
c\right)f(\mathcal{P}^{\ast}).$ (9)

Combining inequalities (8) and (9), we have

$\displaystyle\frac{f(\mathcal{P})}{f(\mathcal{P}^{\ast})}\leq\max_{c\in[0,1]}\min\left\\{\left(\frac{A+B}{A+B+1}\right)\left(1+\frac{1+A}{A+B}\cdot
c\right),\;\frac{A+B}{A}-\frac{B}{A}\cdot c\right\\}.$ (10)

Thus, in order to upper bound the approximation factor, it suffices to upper
bound the right hand side of inequality (10). Since
$\left(\frac{A+B}{A+B+1}\right)\left(1+\frac{1+A}{A+B}\cdot c\right)$ and
$\frac{A+B}{A}-\frac{B}{A}\cdot c$ are both linear in $c$, with the former
increasing and the latter decreasing as a function of $c$, the value

$\max_{c\in\mathbb{R}}\min\left\\{\left(\frac{A+B}{A+B+1}\right)\left(1+\frac{1+A}{A+B}\cdot
c\right),\;\frac{A+B}{A}-\frac{B}{A}\cdot c\right\\}$

is achieved when the two terms are equal. Setting
$\left(\frac{A+B}{A+B+1}\right)\left(1+\frac{1+A}{A+B}\cdot
c^{\ast}\right)=\frac{A+B}{A}-\frac{B}{A}\cdot c^{\ast}$ and solving for
$c^{\ast}$, we get

$c^{\ast}=\frac{\frac{A+B}{A}-\frac{A+B}{A+B+1}}{\frac{1+A}{A+B+1}+\frac{B}{A}}=\frac{\frac{B}{A}+\frac{1}{A+B+1}}{\frac{1+A}{A+B+1}+\frac{B}{A}}.$

Plugging $c=c^{\ast}$ into $\frac{A+B}{A}-\frac{B}{A}\cdot c$ yields

$\displaystyle\frac{f(\mathcal{P})}{f(\mathcal{P}^{\ast})}$
$\displaystyle\leq\max_{c\in[0,1]}\min\left\\{\frac{A+B}{A+B+1}\left(1+\frac{1+A}{A+B}\cdot
c\right),\;\frac{A+B}{A}-\frac{B}{A}\cdot c\right\\}$
$\displaystyle\leq\frac{A+B}{A}-\frac{B}{A}\cdot c^{\ast}$
$\displaystyle=1+\frac{B}{A}(1-c^{\ast})$
$\displaystyle=1+\frac{B}{A}\left(1-\frac{\frac{B}{A}+\frac{1}{A+B+1}}{\frac{1+A}{A+B+1}+\frac{B}{A}}\right)$
$\displaystyle=1+\frac{\frac{B}{A+B+1}}{\frac{1+A}{A+B+1}+\frac{B}{A}}$
$\displaystyle=1+\frac{AB}{A+A^{2}+AB+B^{2}+B}$ $\displaystyle\leq
1+\frac{AB}{3AB+A+B}\quad(\text{since }A^{2}+B^{2}\geq 2AB)$
$\displaystyle=\frac{4}{3}-\frac{1}{3}\cdot\frac{A+B}{3AB+A+B}$
$\displaystyle=\frac{4}{3}-\frac{1}{3}\cdot\frac{A+B}{3AB/2+3AB/2+A+B}$
$\displaystyle\leq\frac{4}{3}-\frac{1}{3}\cdot\frac{A+B}{3AB/2+3(A^{2}+B^{2})/4+A+B}\quad(\text{since
}AB\leq\frac{A^{2}+B^{2}}{2})$
$\displaystyle=\frac{4}{3}-\frac{1}{3}\cdot\frac{A+B}{3(A+B)^{2}/4+A+B}$
$\displaystyle=\frac{4}{3}-\frac{1}{3}\cdot\frac{1}{3(A+B)/4+1}$
$\displaystyle\leq\frac{4}{3}-\frac{4}{9n+3}.$

The last inequality above is because
$A+B=|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|\leq n-1$. ∎

######  Remark 3.1.

The approximation factor of Algorithm 1 for non-negative monotone submodular
functions is at least $4/3-4/(9n+3)$. We show this for $n=3$ using the
following example: Let $V=\\{a,b,c\\}$, $k=2$, and $f:2^{V}\to\mathbb{R}_{\geq
0}$ be defined by

$\displaystyle
f(\emptyset)=0,\;f(\\{a\\})=1,\;f(\\{b\\})=f(\\{c\\})=1+\epsilon,$
$\displaystyle
f(\\{a,b\\})=f(\\{a,c\\})=\frac{3}{2}+\epsilon,\;f(\\{b,c\\})=f(V)=2+2\epsilon.$

Submodularity and monotonicity of $f$ can be verified by considering all
possible subsets. Moreover, the principal partition sequence of this instance
is $\\{V\\},\\{\\{a\\},\\{b\\},\\{c\\}\\}$. Thus, Algorithm 1 returns the
$2$-partition $\\{\\{a\\},\\{b,c\\}\\}$, whose objective value is
$3+2\epsilon$. An optimum $2$-partition is $\\{\\{c\\},\\{a,b\\}\\}$, whose
objective value is $5/2+\epsilon$. Thus, the approximation factor is
$\frac{3+2\epsilon}{5/2+\epsilon}\to\frac{6}{5}$ as $\epsilon\to 0$. We note
that for $n=3$, the approximation factor guaranteed by Theorem 3.1 is
$\frac{4}{3}-\frac{4}{9n+3}=\frac{6}{5}$.

We conclude the section by showing that there exist monotone submodular
functions for which the approximation factor of Algorithm 1 is at least $4/3$
asymptotically (i.e., as $n\to\infty$).

######  Lemma 3.4.

For every odd positive integer $n\geq 5$, there exists a function $k=k(n)$
(i.e., $k$ is a function of $n$) and an instance of non-negative monotone
submodular $k$-partition over an $n$-element ground set such that the
approximation factor of Algorithm 1 on that instance is arbitrarily close to
$4/3-4/(3n+3)$.

###### Proof.

Let $n\geq 5$ be an arbitrary odd number, $k=\frac{n+1}{2}$, and let
$V=\\{v_{1},\ldots,v_{n}\\}$ be the ground set. Moreover, let
$U:=\\{v_{1},\ldots,v_{\frac{n-1}{2}}\\}$ and
$D:=\\{v_{\frac{n+1}{2}},\ldots,v_{n}\\}$ so that $V=U\uplus D$. Let
$g:2^{U}\to\mathbb{R}_{\geq 0}$ be a function over the ground set $U$ defined
by

$g(S)=\begin{cases}\frac{1}{2}+\frac{1}{2}\cdot|S|&\ \text{ if }\
\emptyset\neq S\subseteq U,\\\ 0&\ \text{ if }S=\emptyset.\end{cases}$

and $f:2^{V}\to\mathbb{R}_{\geq 0}$ be defined by

$f(S):=\min\left\\{g(S\cap U)+(1+\epsilon)|S\cap D|,\;\frac{n+1}{2}\right\\}\
\forall\ S\subseteq V,$

where $\epsilon>0$ is infinitesimally small. The function $f$ satisfies
$f(\emptyset)=0$, $f(V)=\frac{n+1}{2}$, $f(U)=\frac{n+1}{4}$,
$f(D)=\frac{n+1}{2}$, $f(\\{v\\})=1$ for each $v\in U$, and
$f(\\{v\\})=1+\epsilon$ for each $u\in D$. We will use $\mathcal{Q}$ to denote
the partition of $V$ into $n$ singleton sets, and it follows that
$f(\mathcal{Q})=n+\frac{(n+1)\epsilon}{2}$. For convenience, we will write
$h(S):=g(S\cap U)+|S\cap D|$ for all $S\subseteq V$ so that
$f(S)=\min\\{h(S),\frac{n+1}{2}\\}$ for all $S\subseteq V$ throughout the
proof.

######  Claim 3.1.

The function $f$ is submodular and monotone.

###### Proof.

Let $A,B\subseteq V$ be arbitrary. We notice that the function $h$ is
monotone, and

$h(A)+h(B)\geq h(A\cap B)+h(A\cup B).$

Without loss of generality, we may assume $h(A)\geq h(B)$, and thus $h(A\cup
B)\geq h(A)\geq h(B)\geq h(A\cap B)$. We consider the following five cases:

  1. 1.

$h(A\cup B)\leq\frac{n+1}{2}$.

$\implies f(A)+f(B)=h(A)+h(B)\geq h(A\cap B)+h(A\cup B)=f(A\cap B)+f(A\cup
B).$

  2. 2.

$h(A)\leq\frac{n+1}{2}<h(A\cup B)$.

$\implies f(A)+f(B)=h(A)+h(B)\geq h(A\cap B)+h(A\cup B)>h(A\cap
B)+\frac{n+1}{2}=f(A\cap B)+f(A\cup B).$

  3. 3.

$h(B)\leq\frac{n+1}{2}<h(A)$.

$\implies f(A)+f(B)=\frac{n+1}{2}+h(B)\geq\frac{n+1}{2}+h(A\cap B)=f(A\cup
B)+f(A\cap B).$

  4. 4.

$h(A\cap B)\leq\frac{n+1}{2}<h(B)$.

$\implies f(A)+f(B)=\frac{n+1}{2}+\frac{n+1}{2}\geq\frac{n+1}{2}+h(A\cap
B)=f(A\cup B)+f(A\cap B).$

  5. 5.

$\frac{n+1}{2}<h(A\cap B)$.

$\implies f(A)+f(B)=\frac{n+1}{2}+\frac{n+1}{2}=f(A\cup B)+f(A\cap B).$

Since exactly one of these five cases holds, we have proved the submodularity
of $f$. The monotonicity of $f$ is implied by the monotonicity of $h$. ∎

######  Claim 3.2.

For every partition $\mathcal{P}\neq\mathcal{Q},\\{V\\}$, the function $f$
satisfies

$\frac{f(\mathcal{P})-f(V)}{|\mathcal{P}|-1}>\frac{f(\mathcal{Q})-f(V)}{n-1}.$

###### Proof.

First, we note that $f(V)=\frac{n+1}{2}$ and
$\frac{f(\mathcal{Q})-f(V)}{n-1}=\frac{n+(n+1)\epsilon/2-(n+1)/2}{n-1}=\frac{1}{2}+\frac{(n+1)\epsilon}{2n-2}$,
and thus the desired inequality is equivalent to

$f(\mathcal{P})\geq\frac{n}{2}+\frac{1}{2}|\mathcal{P}|+\epsilon(|\mathcal{P}|-1)\frac{n+1}{2n-2}.$

We note that there exists at most one part $P\in\mathcal{P}$ such that
$h(P)\geq\frac{n+1}{2}$. To see this, assume that two distinct parts
$P,P^{\prime}\in\mathcal{P}$ satisfy $h(P)\geq\frac{n+1}{2}$ and
$h(P^{\prime})\geq\frac{n+1}{2}$. This implies

$\displaystyle n+1$ $\displaystyle\leq h(P)+h(P^{\prime})\leq
2\cdot\frac{1}{2}+\frac{1}{2}|(P\cup P^{\prime})\cap U|+(1+\epsilon)|(P\cup
P^{\prime})\cap D|$ $\displaystyle\leq
1+\frac{1}{2}\cdot\frac{n-1}{2}+(1+\epsilon)\frac{n+1}{2}=\frac{3n+1}{4}+1+\frac{(n+1)\epsilon}{2}<n+1,$

because $\epsilon$ is infinitesimal and $n\geq 5$, yielding a contradiction.
Therefore, we may consider two cases: $\mathcal{P}$ containing no part $P$
such that $h(P)\geq\frac{n+1}{2}$, and $\mathcal{P}$ containing exactly one
part $P$ such that $h(P)\geq\frac{n+1}{2}$.

Suppose $\mathcal{P}$ contains no part $P$ such that $h(P)\geq\frac{n+1}{2}$.
We will use $t$ to denote the number of parts of $\mathcal{P}$ that each
intersects $U$ non-trivially. Then, $|\mathcal{P}|-t$ represents the number of
parts of $\mathcal{P}$ that are each contained in $D$, and we have
$|\mathcal{P}|-t\leq|D|=\frac{n+1}{2}$. It follows that

$\displaystyle
f(\mathcal{P})-\frac{n}{2}-\frac{|\mathcal{P}|}{2}-\epsilon(|\mathcal{P}|-1)\frac{n+1}{2n-2}$
$\displaystyle=\frac{1}{2}\cdot
t+\frac{1}{2}\cdot\frac{n-1}{2}+(1+\epsilon)\frac{n+1}{2}$
$\displaystyle\quad\quad\quad\quad\quad\quad-\frac{n}{2}-\frac{|\mathcal{P}|}{2}-\epsilon(|\mathcal{P}|-1)\frac{n+1}{2n-2}$
$\displaystyle=\frac{n+1}{4}-\frac{|\mathcal{P}|-t}{2}+\epsilon\left(\frac{n+1}{2}-\frac{(|\mathcal{P}|-1)(n+1)}{2n-2}\right)$
$\displaystyle\geq\frac{n+1}{4}-\frac{n+1}{4}+\epsilon\left(\frac{n+1}{2}-\frac{(|\mathcal{P}|-1)(n+1)}{2n-2}\right)$
$\displaystyle\geq\epsilon\left(\frac{n+1}{2}-\frac{(n-2)(n+1)}{2n-2}\right)\
\ (\text{since }|\mathcal{P}|\leq n-1)$
$\displaystyle=\epsilon\cdot\frac{n+1}{2n-2}$ $\displaystyle>0.$

Now, suppose $\mathcal{P}$ contains exactly one part $P\in\mathcal{P}$ such
that $h(P)\geq\frac{n+1}{2}$. Each other part $P^{\prime}\neq P$ of
$\mathcal{P}$ satisfies $f(P^{\prime})\geq 1$. It follows that

$\displaystyle
f(\mathcal{P})\geq\frac{n+1}{2}+1\cdot(|\mathcal{P}|-1)=\frac{n}{2}+|\mathcal{P}|-\frac{1}{2}>\frac{n}{2}+\frac{1}{2}\cdot|\mathcal{P}|+\epsilon(|\mathcal{P}|-1)\frac{n+1}{2n-2}$

since $|\mathcal{P}|\geq 2$ and $\epsilon$ is arbitrarily small. ∎

By Proposition 2.1, Algorithm 1 returns the partition
$\\{\\{v_{1}\\},\ldots,\\{v_{\frac{n-1}{2}}\\},D\\}$ (because
$\\{v_{1}\\},\ldots,\\{v_{\frac{n-1}{2}}\\}$ are the $k-1$ singleton sets that
minimize the $f$ values), whose objective is $\frac{n-1}{2}+\frac{n+1}{2}=n$.
The partition
$\\{\\{v_{1},\ldots,v_{\frac{n+1}{2}}\\},\\{v_{\frac{n+3}{2}}\\},\ldots,\\{v_{n}\\}\\}$
has objective
$\frac{n+1}{4}+(1+\epsilon)+(1+\epsilon)\frac{n-1}{2}=\frac{3n+3}{4}+\frac{(n+1)\epsilon}{2}$.
The approximation factor is at least

$\frac{n}{\frac{3n+3}{4}+\frac{(n+1)\epsilon}{2}}\to\frac{4}{3}-\frac{4}{3n+3}\;(\text{as
}\epsilon\to 0).$

This completes the proof of Lemma 3.4. ∎

###  3.2 Symmetric submodular functions

In this section, we bound the approximation factor of Algorithm 1 for
symmetric submodular $k$-partitioning. The following is the main theorem of
this section.

######  Theorem 3.2.

The approximation factor of Algorithm 1 for non-negative symmetric submodular
$k$-partitioning is $2(1-1/n)$, where $n$ is the size of the ground set.

The asymptotic approximation factor of $2$ achieved by Algorithm 1 is the best
possible for non-negative symmetric submodular $k$-partition: for every
constant $\epsilon>0$, there does not exist an algorithm that achieves a
$(2-\epsilon)$-approximation using polynomial number of function evaluation
queries [22]. We will remark on the tightness of the approximation factor for
Algorithm 1 after proving the theorem. The proof of Theorem 3.2 follows from
Lemma 3.1 and Lemma 3.5 shown below.

######  Lemma 3.5.

Let $k\geq 2$ be an integer, $f:2^{V}\to\mathbb{R}$ be a non-negative
symmetric submodular function on a ground set $V$ of size $n$,
$\mathcal{P}^{\ast}$ be a $k$-partition of $V$ that minimizes
$f(\mathcal{P}^{\ast})$, and
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ be a principal
partition sequence of the submodular function $f$ satisfying the conditions of
Theorem 2.1. Suppose $|\mathcal{P}_{j}|\neq k$ for all $j\in[r]$. Then the
partition $\mathcal{P}$ returned by Algorithm 1 satisfies

$f(\mathcal{P})\leq 2\left(1-\frac{1}{n}\right)f(\mathcal{P}^{\ast}).$

###### Proof.

Let $\mathcal{P}_{i-1},\mathcal{P}_{i}$ be the partitions such that
$|\mathcal{P}_{i-1}|<k<|\mathcal{P}_{i}|$. Let $S$ and
$\mathcal{P}^{\prime}=\\{B_{1},B_{2},\ldots,B_{|\mathcal{P}^{\prime}|}\\}$ be
as in Algorithm 1.

Firstly, we note that for every $T\subseteq S$, symmetry, submodularity, and
non-negativity of $f$ together imply that

$\displaystyle f(T)$ $\displaystyle=f(V-T)=f((V-S)\cup(S-T))\leq
f(V-S)+f(S-T)=f(S)+f(S-T).$ (11)

Secondly, by our choice of $B_{1},B_{2},\ldots,B_{k-|\mathcal{P}_{i-1}|}$, we
know that

$\displaystyle\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})\leq\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime}).$
(12)

Since $\cup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\subseteq
S$, we have that

$\displaystyle
f\left(\bigcup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\right)$
$\displaystyle\leq
f(S)+f\left(\bigcup_{j=1}^{k-|\mathcal{P}_{i-1}|}B_{j}\right)\quad\text{(by
inequality \eqref{Eqn: sym sm})}$ $\displaystyle\leq
f(S)+\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})\quad\text{(by submodularity
and non-negativity)}$ $\displaystyle\leq
f(S)+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime}).\quad\text{(by
inequality }\eqref{Eqn: sum of f(Bj)})$

Therefore, we have

$\displaystyle f(\mathcal{P})$
$\displaystyle=f(\mathcal{P}_{i-1})-f(S)+\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})+f\left(\bigcup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\right)$
$\displaystyle\leq
f(\mathcal{P}_{i-1})-f(S)+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime})+\left(f(S)+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime})\right)$
$\displaystyle=f(\mathcal{P}_{i-1})+2\cdot\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime})$
$\displaystyle=f(\mathcal{P}_{i-1})+2\cdot\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(f(\mathcal{P}_{i})+f(S)-f(\mathcal{P}_{i-1})),$

where the last equality follows from the fact that
$f(\mathcal{P}_{i-1})-f(S)+f(\mathcal{P}^{\prime})=f(\mathcal{P}_{i})$ and
$|\mathcal{P}^{\prime}|=|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1$. Rearranging,
we get

$\displaystyle
f(\mathcal{P})\leq\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(|\mathcal{P}_{i}|+|\mathcal{P}_{i-1}|-2k+1)$
$\displaystyle+\frac{f(\mathcal{P}_{i})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(2k-2|\mathcal{P}_{i-1}|)$
$\displaystyle\quad\quad\quad\quad+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\cdot
2f(S).$

Now, we observe that $2f(S)=f(S)+f(V-S)\leq f(\mathcal{P}_{i-1})$ by symmetry,
submodularity, and non-negativity. Consequently, we have that

$\displaystyle f(\mathcal{P})$
$\displaystyle\leq\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(|\mathcal{P}_{i}|+|\mathcal{P}_{i-1}|-2k+1)+\frac{f(\mathcal{P}_{i})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(2k-2|\mathcal{P}_{i-1}|)$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\cdot
f(\mathcal{P}_{i-1})$
$\displaystyle=\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(|\mathcal{P}_{i}|-k+1)+\frac{f(\mathcal{P}_{i})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(2k-2|\mathcal{P}_{i-1}|)\right)$
$\displaystyle\leq\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(2|\mathcal{P}_{i}|-2k)+\frac{f(\mathcal{P}_{i})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(2k-2|\mathcal{P}_{i-1}|)\right)$
$\displaystyle\leq\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\cdot
2f(\mathcal{P}^{\ast})\quad(\text{by Lemma \ref{lemma: f long ineq}(i)})$
$\displaystyle=\left(1-\frac{1}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\cdot
2f(\mathcal{P}^{\ast})$ $\displaystyle\leq
2\left(1-\frac{1}{n}\right)f(\mathcal{P}^{\ast}),$

where the second inequality is because $1\leq|\mathcal{P}_{i}|-k$ and the last
inequality is because $|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|\leq n-1$. ∎

######  Remark 3.2.

In contrast to the greedy splitting and the Gomory-Hu tree based approaches,
the principal partition sequence approach given in Algorithm 1 does not
achieve an approximation factor of $2-2/k$ for non-negative symmetric
submodular functions: For the special case of graph $k$-cut, Proposition 5.2
of [21] provides a family of graph cut functions on which Algorithm 1 returns
solutions whose approximation factor is arbitrarily close to $2$.

###  3.3 Posimodular submodular functions

In this section, we bound the approximation factor of Algorithm 1 for
posimodular submodular $k$-partitioning. The following is the main theorem of
this section.

######  Theorem 3.3.

The approximation factor of Algorithm 1 for non-negative posimodular
submodular $k$-partitioning is $2(1-\frac{1}{n+1})$, where $n$ is the size of
the ground set.

The asymptotic approximation factor of $2$ achieved by Algorithm 1 is the best
possible for non-negative posimodular submodular $k$-partition: for every
constant $\epsilon>0$, there does not exist an algorithm that achieves a
$(2-\epsilon)$-approximation using polynomial number of function evaluation
queries [22]. Lemmas 3.1 and 3.6 complete the proof of Theorem 3.3. The proof
of Theorem 3.3 follows from Lemma 3.1 and Lemma 3.6 shown below.

######  Lemma 3.6.

Let $k\geq 2$ be an integer, $f:2^{V}\to\mathbb{R}_{\geq 0}$ be a non-negative
posimodular submodular function on a ground set $V$ of size $n$,
$\mathcal{P}^{\ast}$ be a $k$-partition of $V$ that minimizes
$f(\mathcal{P}^{\ast})$, and
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots,\mathcal{P}_{r}$ be a principal
partition sequence of the submodular function $f$ satisfying the conditions of
Theorem 2.1. Suppose $|\mathcal{P}_{j}|\neq k$ for all $j\in[r]$. Then, the
partition $\mathcal{P}$ returned by Algorithm 1 satisfies

$f(\mathcal{P})\leq 2\left(1-\frac{1}{n+1}\right)f(\mathcal{P}^{\ast}).$

###### Proof.

Let $\mathcal{P}_{i-1},\mathcal{P}_{i}$ be the partitions such that
$|\mathcal{P}_{i-1}|<k<|\mathcal{P}_{i}|$. Let $S$ and
$\mathcal{P}^{\prime}=\\{B_{1},B_{2},\ldots,B_{|\mathcal{P}^{\prime}|}\\}$ be
as in Algorithm 1.

Firstly, we note that for every $T\subseteq S$, non-negativity and
posimodularity implies that

$\displaystyle f(T)\leq f(T)+f(\emptyset)\leq f(S)+f(S-T).$ (13)

Secondly, by our choice of $B_{1},B_{2},\ldots,B_{k-|\mathcal{P}_{i-1}|}$, we
know that

$\displaystyle\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})\leq\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime}).$
(14)

Since $\cup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\subseteq
S$, we have that

$\displaystyle
f\left(\bigcup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\right)$
$\displaystyle\leq
f(S)+f\left(\bigcup_{j=1}^{k-|\mathcal{P}_{i-1}|}B_{j}\right)\quad\text{(by
inequality \eqref{Eqn: posi sm})}$ $\displaystyle\leq
f(S)+\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})\quad\text{(by submodularity
and non-negativity)}$ $\displaystyle\leq
f(S)+\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime}).\quad\text{(by
inequality }\eqref{Eqn: sum of f(Bj)-posi})$

Therefore, we have

$\displaystyle f(\mathcal{P})$
$\displaystyle=f(\mathcal{P}_{i-1})-f(S)+\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})+f\left(\bigcup_{j=k-|\mathcal{P}_{i-1}|+1}^{|\mathcal{P}^{\prime}|}B_{j}\right)$
$\displaystyle\leq
f(\mathcal{P}_{i-1})-f(S)+2\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})+f(S)$
$\displaystyle=f(\mathcal{P}_{i-1})+2\cdot\sum_{j=1}^{k-|\mathcal{P}_{i-1}|}f(B_{j})$
$\displaystyle\leq
f(\mathcal{P}_{i-1})+2\cdot\frac{k-|\mathcal{P}_{i-1}|}{|\mathcal{P}^{\prime}|}f(\mathcal{P}^{\prime})$
$\displaystyle=f(\mathcal{P}_{i-1})+\frac{2k-2|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}(f(\mathcal{P}_{i})+f(S)-f(\mathcal{P}_{i-1})),$

where the last equality follows from the fact that
$f(\mathcal{P}_{i-1})-f(S)+f(\mathcal{P}^{\prime})=f(\mathcal{P}_{i})$ and
$|\mathcal{P}^{\prime}|=|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1$. Applying the
fact that $f(S)\leq f(\mathcal{P}_{i-1})$, we have

$\displaystyle f(\mathcal{P})$
$\displaystyle\leq\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1)\right)$
$\displaystyle\quad\quad\quad\quad\quad\quad+\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(\frac{f(\mathcal{P}_{i})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(2k-2|\mathcal{P}_{i-1}|)\right)$
$\displaystyle=\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}((2|\mathcal{P}_{i}|-2k)+(2k-|\mathcal{P}_{i-1}|-|\mathcal{P}_{i}|+1))\right)$
$\displaystyle\quad\quad\quad\quad\quad\quad+\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(\frac{2f(\mathcal{P}_{i})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(k-|\mathcal{P}_{i-1}|)\right)$
$\displaystyle\leq\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(2f(\mathcal{P}^{\ast})+\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(2k-|\mathcal{P}_{i-1}|-|\mathcal{P}_{i}|+1)\right),$
(15)

where the last inequality is by Lemma 3.2(i). Inequality (15) implies that

$\displaystyle f(\mathcal{P})$
$\displaystyle\leq\left(\frac{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(2f(\mathcal{P}^{\ast})+f(\mathcal{P}_{i-1})+\frac{f(\mathcal{P}_{i-1})}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|}(2k-2|\mathcal{P}_{i}|+1)\right)$
$\displaystyle\leq\left(1-\frac{1}{|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|+1}\right)\left(2f(\mathcal{P}^{\ast})+f(\mathcal{P}_{i-1})\right)\quad(\text{since
}k<|\mathcal{P}_{i}|)$ $\displaystyle\leq 3f(\mathcal{P}^{\ast}),$

where the last inequality is because $f(\mathcal{P}_{i-1})\leq
f(\mathcal{P}^{\ast})$ by Lemma 3.2(ii). The above analysis already shows that
the approximation factor is at most $3$. We tighten the factor now. As a
consequence of the above inequality, we may assume that
$f(\mathcal{P}^{\ast})\neq 0$ because if $f(\mathcal{P}^{\ast})=0$, then the
returned $k$-partition $\mathcal{P}$ also satisfies $f(\mathcal{P})=0$ and
thus, is optimal. Let $c:=f(\mathcal{P}_{i-1})/f(\mathcal{P}^{\ast})$. By
Lemma 3.2(ii), we have that $f(\mathcal{P}_{i-1})\leq f(\mathcal{P}^{\ast})$
and hence, $c\in[0,1]$. For convenience, we define $A:=k-|\mathcal{P}_{i-1}|$
and $B:=|\mathcal{P}_{i}|-k$ and note that $A,B\geq 1$. Using these notations,
we may rewrite inequality (15) as

$\displaystyle f(\mathcal{P})$
$\displaystyle\leq\left(\frac{A+B}{A+B+1}\right)\left(2f(\mathcal{P}^{\ast})+\frac{A-B+1}{A+B}f(\mathcal{P}_{i-1})\right)$
$\displaystyle=\left(\frac{A+B}{A+B+1}\right)\left(2+\frac{A-B+1}{A+B}\cdot
c\right)f(\mathcal{P}^{\ast}).$ (16)

By Lemma 3.2(i), we have

$f(\mathcal{P}^{\ast})\geq\left(\frac{B}{A+B}\right)f(\mathcal{P}_{i-1})+\left(\frac{A}{A+B}\right)f(\mathcal{P}_{i})=\left(\frac{B}{A+B}\right)cf(\mathcal{P}^{\ast})+\left(\frac{A}{A+B}\right)f(\mathcal{P}_{i}).$

Rearranging, we have

$f(\mathcal{P}_{i})\leq\left(1-\frac{B}{A+B}\cdot
c\right)\left(\frac{A+B}{A}\right)f(\mathcal{P}^{\ast})=\left(\frac{A+B}{A}-\frac{B}{A}\cdot
c\right)f(\mathcal{P}^{\ast}).$

Since $\mathcal{P}$ is obtained by coarsening $\mathcal{P}_{i}$, we have
$f(\mathcal{P})\leq f(\mathcal{P}_{i})$ by submodularity and non-negativity of
$f$. Hence,

$\displaystyle f(\mathcal{P})\leq\left(\frac{A+B}{A}-\frac{B}{A}\cdot
c\right)f(\mathcal{P}^{\ast}).$ (17)

Combining inequalities (16) and (17), we have

$\displaystyle\frac{f(\mathcal{P})}{f(\mathcal{P}^{\ast})}\leq\max_{c\in[0,1]}\min\left\\{\left(\frac{A+B}{A+B+1}\right)\left(2+\frac{A-B+1}{A+B}\cdot
c\right),\;\frac{A+B}{A}-\frac{B}{A}\cdot c\right\\}.$ (18)

Thus, in order to upper bound the approximation factor, it suffices to upper
bound the right hand side of inequality (18). Both terms
$\left(\frac{A+B}{A+B+1}\right)\left(2+\frac{A-B+1}{A+B}\cdot c\right)$ and
$\frac{A+B}{A}-\frac{B}{A}\cdot c$ are linear in $c$, and the latter is
decreasing as a function of $c$. Next, we consider two cases: $A-B+1\leq 0$
and $A-B+1>0$.

Suppose $A-B+1\leq 0$, then the term
$\left(\frac{A+B}{A+B+1}\right)\left(2+\frac{A-B+1}{A+B}\cdot c\right)$ is
linear and non-increasing as a function of $c$. The maximum

$\max_{c\in[0,1]}\min\left\\{\left(\frac{A+B}{A+B+1}\right)\left(2+\frac{A-B+1}{A+B}\cdot
c\right),\;\frac{A+B}{A}-\frac{B}{A}\cdot c\right\\}$

is achieved at $c=0$. Thus, we have

$\displaystyle\frac{f(\mathcal{P})}{f(\mathcal{P}^{\ast})}$
$\displaystyle\leq\min\left\\{\frac{A+B}{A+B+1}\cdot
2,\;\frac{A+B}{A}\right\\}$ $\displaystyle\leq\frac{A+B}{A+B+1}\cdot 2$
$\displaystyle=2\left(1-\frac{1}{A+B+1}\right)$ $\displaystyle\leq
2\left(1-\frac{1}{n}\right),$ (19)

where the last inequality follows from the fact that
$A+B=|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|\leq n-1$.

Now, we consider the case $A-B+1>0$. The term
$\left(\frac{A+B}{A+B+1}\right)\left(2+\frac{A-B+1}{A+B}\cdot c\right)$ is
linear and increasing as a function of $c$, and thus the maximum

$\max_{c\in\mathbb{R}}\min\left\\{\left(\frac{A+B}{A+B+1}\right)\left(2+\frac{A-B+1}{A+B}\cdot
c\right),\;\frac{A+B}{A}-\frac{B}{A}\cdot c\right\\}$

is achieved when the two terms are equal. Setting
$\left(\frac{A+B}{A+B+1}\right)\left(2+\frac{A-B+1}{A+B}\cdot
c^{\ast}\right)=\frac{A+B}{A}-\frac{B}{A}\cdot c^{\ast}$ and solving for
$c^{\ast}$, we get

$\displaystyle
c^{\ast}=\frac{\frac{A+B}{A}-2\cdot\frac{A+B}{A+B+1}}{\frac{A-B+1}{A+B+1}+\frac{B}{A}}.$

Plugging $c=c^{\ast}$ into $\frac{A+B}{A}-\frac{B}{A}\cdot c$, we have

$\displaystyle\frac{f(\mathcal{P})}{f(\mathcal{P}^{\ast})}$
$\displaystyle\leq\max_{c\in[0,1]}\min\left\\{\left(\frac{A+B}{A+B+1}\right)\left(2+\frac{A-B+1}{A+B}\cdot
c\right),\;\frac{A+B}{A}-\frac{B}{A}\cdot c\right\\}$
$\displaystyle\leq\frac{A+B}{A}-\frac{B}{A}\cdot c^{\ast}$
$\displaystyle=1+\frac{B}{A}(1-c^{\ast})$
$\displaystyle=1+\frac{B}{A}\left(1-\frac{\frac{A+B}{A}-2\cdot\frac{A+B}{A+B+1}}{\frac{A-B+1}{A+B+1}+\frac{B}{A}}\right)$
$\displaystyle=1+\frac{\frac{2B}{A+B+1}}{\frac{A-B+1}{A+B+1}+\frac{B}{A}}$
$\displaystyle=1+\frac{2AB}{A^{2}+A+B^{2}+B}$ $\displaystyle\leq
1+\frac{2AB}{2AB+A+B}\quad(\text{since }A^{2}+B^{2}\geq 2AB)$
$\displaystyle=2-\frac{A+B}{2AB+A+B}$ $\displaystyle=2-\frac{A+B}{AB+AB+A+B}$
$\displaystyle\leq 2-\frac{A+B}{AB+(A^{2}+B^{2})/2+A+B}\quad(\text{since
}AB\leq\frac{A^{2}+B^{2}}{2})$ $\displaystyle=2-\frac{A+B}{(A+B)^{2}/2+A+B}$
$\displaystyle=2-\frac{1}{(A+B)/2+1}$ $\displaystyle\leq 2-\frac{2}{n+1}.$

The last inequality above is because
$A+B=|\mathcal{P}_{i}|-|\mathcal{P}_{i-1}|\leq n-1$. ∎

######  Remark 3.3.

The approximation factor of Algorithm 1 for non-negative posimodular
submodular functions is at least $2-2/(n+1)$. We show this for $n=3,k=2$ using
the following example: Let $V=\\{a,b,c\\}$, $k=2$, and
$f:2^{V}\rightarrow\mathbb{R}_{\geq 0}$ be defined by

$\displaystyle f(\emptyset)=0,\;f(a)=f(b)=1,\;f(c)=1+\epsilon,$ $\displaystyle
f(\\{a,b\\})=1+\epsilon,\;f(\\{b,c\\})=f(\\{a,c\\})=2,\;f(\\{a,b,c\\})=1+\epsilon.$

Submodularity and posimodularity of $f$ can be verified by considering all
possible subsets. Moreover, the principal partition sequence of this instance
is $\\{V\\},\\{\\{a\\},\\{b\\},\\{c\\}\\}$. Thus, the algorithm returns the
$2$-partition $\\{\\{a\\},\\{b,c\\}\\}$, while the optimum $2$-partition is
$\\{\\{c\\},\\{a,b\\}\\}$. Thus, the approximation factor approaches $3/2$ as
$\epsilon\to 0$. We note that for $n=3$, the approximation factor guaranteed
by Theorem 3.3 is $2-2/(n+1)=3/2$.

##  4 Lower bound for arbitrary submodular functions

In this section, we present an instance of submodular $k$-partition where
Algorithm 1 achieves an approximation factor of $\Omega(n/k)$. We emphasize
that the submodular function in our instance is not
symmetric/monotone/posimodular.

Let $V=\\{v_{0},v_{1},\ldots,v_{n-1}\\}$ be the ground set. We define a
digraph $D=(V,E(D))$ and a hypergraph $H=(V,E(H))$ on the same vertex set $V$
as follows (see Fig.1):

$\displaystyle E(D)$ $\displaystyle=\\{v_{0}v_{i}:i\in[n-1]\\}\text{ and }$
$\displaystyle E(H)$ $\displaystyle=\\{\\{v_{1},v_{2},\ldots,v_{n-1}\\}\\}.$

Figure 1: Example in Section 4. The arcs belong to the digraph $D$ and the
hyperedge $\\{v_{1},\ldots,v_{n-1}\\}$ belongs to the hypergraph $H$.

For every subset $S\subseteq V$, we will use $d_{D}^{in}(S)$ to denote the
number of arcs in $D$ whose tails are in $\bar{S}$ and heads are in $S$. We
will use $d_{H}(S)$ to denote the number of hyperedges in $H$ that have at
least one vertex in $S$ and one vertex in $\bar{S}$. Next, we define a set
function $f:2^{V}\to\mathbb{R}_{\geq 0}$ by

$f(S):=a\cdot d^{in}_{D}(S)+d_{H}(S)\quad\forall S\subseteq V,$

where $a\gg 1$ is a large constant. We note that $f$ is submodular because it
is a positive linear combination of two submodular functions (and it is not
monotone/symmetric/posimodular).

######  Claim 4.1.

The principal partition sequence of $f$ is
$\\{V\\},\\{\\{v_{i}\\}:i\in\\{0,1,\ldots,n-1\\}\\}$.

###### Proof.

For convenience, we will use $\mathcal{Q}$ to denote the partition of $V$ into
singletons. By Proposition 2.1 and the fact that $f(V)=0$, it suffices to
prove that for every partition $\mathcal{P}$ of $V$ such that $\mathcal{P}$ is
not $\mathcal{Q}$ or $\\{V\\}$, we have that

$\displaystyle\frac{f(\mathcal{P})}{|\mathcal{P}|-1}>\frac{f(\mathcal{Q})}{n-1}.$
(20)

Let $P_{0}\in\mathcal{P}$ be the part that contains $v_{0}$. Then, we have
that $f(P_{0})\geq 1$ if $P_{0}\neq\\{v_{0}\\}$ and $f(P_{0})=0$ otherwise.
For each part $P\in\mathcal{P}$ that does not contain $v_{0}$, we have that
$f(P)\geq 1+a$ if $|P|=1$ and $f(P)\geq 2+a$ if $|P|\geq 2$. Since
$\mathcal{P}\neq\mathcal{Q}$, we have that either $P_{0}\neq\\{v_{0}\\}$ or at
least one of the parts $P\in\mathcal{P}\setminus\\{P_{0}\\}$ has size $|P|\geq
2$. Thus,
$f(\mathcal{P})=\sum_{P\in\mathcal{P}}f(P)\geq(1+a)(|\mathcal{P}|-1)+1$.
Moreover, we have $f(\mathcal{Q})=(1+a)(n-1)$ and hence

$\displaystyle\frac{f(\mathcal{P})}{|\mathcal{P}|-1}$
$\displaystyle\geq\frac{(1+a)(|\mathcal{P}|-1)+1}{|\mathcal{P}|-1}=1+a+\frac{1}{|\mathcal{P}|-1}>1+a=\frac{(1+a)(n-1)}{n-1}=\frac{f(\mathcal{Q})}{n-1}.$

This proves inequality (20). ∎

######  Claim 4.2.

The approximation factor of Algorithm 1 on input $(f,k)$ is $\Omega(n/k)$.

###### Proof.

We note that $f(\\{v_{0}\\})=0$ and $f(\\{v_{i}\\})=1+a$ for all $i\in[n-1]$.
By Claim 4.1, on input $(f,k)$, Algorithm 1 returns a partition $\mathcal{P}$
consisting of the $k-1$ singleton parts that minimizes $f$ among all singleton
sets and the complement of the union of these $k-1$ singleton parts.
Therefore, the returned partition $\mathcal{P}$ contains $\\{v_{0}\\}$ as a
part and thus

$f(\mathcal{P})=\sum_{P\in\mathcal{P}:P\neq\\{v_{0}\\}}f(P)\geq
f(V-\\{v_{0}\\})=a(n-1).$

The second inequality follows from submodularity of the function $f$. Consider
the $k$-partition
$\\{\\{v_{1}\\},\\{v_{2}\\},\ldots,\\{v_{k-1}\\},V-\\{v_{1},\ldots,v_{k-1}\\}\\}$,
which has objective $(1+a)(k-1)+1$. This implies that the optimum
$k$-partition $\mathcal{P}^{\ast}$ satisfies
$f(\mathcal{P}^{\ast})\leq(1+a)(k-1)+1$. Thus, the approximation factor of the
solution returned by Algorithm 1 is

$\displaystyle\frac{f(\mathcal{P})}{f(\mathcal{P}^{\ast})}\geq\frac{a(n-1)}{(1+a)(k-1)+1}\to\frac{n-1}{k-1}\text{
as }a\to\infty.$

∎

##  5 Conclusion

The principal partition sequence of submodular functions was shown to exist by
Narayanan [15]. The principal partition sequence of submodular functions is
known in the literature as _principal lattice of partitions_ of submodular
functions since there exists a lattice structure associated with the sequence
of partitions [7, 16, 8, 19, 2, 10, 13]. We chose to call it as principal
partition sequence in this work since the sequence suffices for our purpose.
Narayanan, Roy, and Patkar [17] used the principal partition sequence to
design an algorithm for submodular $k$-partition. They analyzed the
approximation factor of their algorithm for certain subfamilies of submodular
functions that arise from hypergraphs. In this work, we investigated the
approximation factor of their algorithm for three broad subfamilies of
submodular functions—namely monotone, symmetric, and posimodular submodular
functions. Our results show that the principal partition sequence based
algorithm achieves the best possible asymptotic approximation factor for all
these three subfamilies. A novelty of our contributions is the improvement in
the approximability of monotone submodular $k$-partition from $2$ to $4/3$,
thus matching the inapproximability threshold. It would be interesting to pin
down the approximability of special cases of monotone submodular
$k$-partition—e.g., matroid $k$-partition and coverage $k$-partition which are
interesting by themselves since they capture several interesting partitioning
problems.

#### Acknowledgements.

Karthekeyan Chandrasekaran would like to thank Chandra Chekuri for asking
about the approximation factor of the principal partition sequence based
approach for symmetric submodular $k$-partition.

## References

  * [1] M. Baïou and F. Barahona, _Packing Hypertrees and the k-cut problem in Hypergraphs_ , International Conference on Learning and Intelligent Optimization, LION, 2023, pp. 521–534.
  * [2] F. Barahona, _On the k-cut problem_ , Operations Research Letters 26 (2000), no. 3, 99–105.
  * [3] D. Chakrabarty and Z. Huang, _Testing coverage functions_ , Automata, Languages, and Programming, ICALP, 2012, pp. 170–181.
  * [4] K. Chandrasekaran and C. Chekuri, _Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time_, Mathematics of Operations Research (2022), Prelim. version in FOCS 2020: pages 810–821.
  * [5] C. Chekuri and S. Li, _On the hardness of approximating the k-way hypergraph cut problem_ , Theory Comput. 16 (2020), 1–8.
  * [6] C. Chekuri, K. Quanrud, and C. Xu, _LP Relaxation and Tree Packing for Minimum $k$-Cut_, SIAM Journal on Discrete Mathematics 34 (2020), no. 2, 1334–1353.
  * [7] W. Cunningham, _Optimal attack and reinforcement of a network_ , J. ACM 32 (1985), no. 3, 549––561.
  * [8] M. P. Desai, H. Narayanan, and S. B. Patkar, _The realization of finite state machines by decomposition and the principal lattice of partitions of a submodular function_ , Discrete Appl. Math. 131 (2003), 299–310.
  * [9] O. Goldschmidt and D. Hochbaum, _A Polynomial Algorithm for the $k$-cut Problem for Fixed $k$_, Mathematics of Operations Research 19 (1994), no. 1, 24–37.
  * [10] V. Kolmogorov, _A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph_ , Algorithmica (2010), 394–412.
  * [11] P. Manurangsi, _Inapproximability of Maximum Biclique Problems, Minimum $k$-Cut and Densest At-Least-$k$-Subgraph from the Small Set Expansion Hypothesis_, Algorithms 11(1) (2018), 10.
  * [12] H. Nagamochi and Y. Kamidoi, _Minimum cost subpartitions in graphs_ , Information Processing Letters 102 (2007), no. 2, 79–84.
  * [13] K. Nagano, Y. Kawahara, and S. Iwata, _Minimum average cost clustering_ , Advances in Neural Information Processing Systems, NIPS, vol. 23, 2010.
  * [14] J. Naor and Y. Rabani, _Tree packing and approximating k-cuts_ , Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2001, pp. 26––27.
  * [15] H. Narayanan, _The principal lattice of partitions of a submodular function_ , Linear Algebra and its Applications 144 (1991), 179–216.
  * [16] H. Narayanan, _Submodular functions and electrical networks (2nd edition)_ , 1997.
  * [17] H. Narayanan, S. Roy, and S. Patkar, _Approximation algorithms for min-k-overlap problems using the principal lattice of partitions approach_ , Journal of Algorithms 21 (1996), no. 2, 306–330.
  * [18] K. Okumoto, T. Fukunaga, and H. Nagamochi, _Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems_ , Algorithmica 62 (2012), no. 3, 787–806.
  * [19] S. B. Patkar and H. Narayanan, _Improving graph partitions using submodular functions_ , Discrete Appl. Math. 131 (2003), 535–553.
  * [20] K. Quanrud, _Fast and Deterministic Approximations for k-Cut_ , Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX, 2019, pp. 23:1–23:20.
  * [21] R. Ravi and A. Sinha, _Approximating k-cuts using network strength as a lagrangean relaxation_ , European Journal of Operational Research 186 (2008), no. 1, 77–90.
  * [22] R. Santiago, _New approximations and hardness results for submodular partitioning problems_ , Proceedings of International Workshop on Combinatorial Algorithms, IWOCA, 2021, pp. 516–530.
  * [23] H. Saran and V. Vazirani, _Finding k Cuts within Twice the Optimal_ , SIAM Journal on Computing 24 (1995), no. 1, 101–108.
  * [24] V. Vazirani, _Approximation algorithms_ , Springer, Berlin, Germany, 2003 - 2003 (ger;eng).
  * [25] L. Zhao, H. Nagamochi, and T. Ibaraki, _Greedy splitting algorithms for approximating multiway partition problems_ , Mathematical Programming 102 (2005), no. 1, 167–183.