Min-Max Graph Partitioning and Small Set Expansion

Introduction

Min-max partitions arise naturally in many settings. Consider the following application in the context of cloud computing, which is a special case of the general graph-mapping problem considered in [BLNZ11] (and also implicit in other previous works [YYRC08, ZA06, CRB09]). There are $n$ processes communicating with each other, and there are $k$ machines, each having a bandwidth capacity $C$. The goal is to allocate the processes to machines in a way that balances the load (roughly $n/k$ processes per machine), and meets the outgoing bandwidth requirement. Viewing the processes as vertices and the traffic between them as edge-weights, we get the Min–Max $k$–Partitioning problem. In general, balanced partitioning (either min-sum or min-max) is at the heart of many heuristics that are used in a wide range of applications, including VLSI layout, circuit testing and simulation, parallel scientific processing, and sparse linear systems.

Balanced partitioning, particularly in its min-sum version, has been studied extensively during the last two decades, with impressive results and connections to several fields of mathematics, see e.g. [LR99, ENRS99, LLR95, AR98, ARV08, KNS09, LN06, CKN09]. The min-max variants, in contrast, have received much less attention. Previously, no approximation algorithm for the Min–Max $k$–Partitioning problem was given explicitly, and the approximation that follows from known results is not smaller than $O(k\sqrt{\log n})$.One could reduce the problem to the min-sum version of $k$-partitioning. The latter admits bicriteria approximation $O(\sqrt{\log n\log k})$ [KNS09], but the reduction loses another factor of $k/2$. Another possibility is to repeatedly remove $n/k$ vertices from the graph, paying again a factor of $k/2$ on top of the approximation in a single iteration, which is, say, $O(\log n)$ by [Räc08]. We improve this dependence on $k$ significantly.

An important tool in our result above is an approximation algorithm for the Small-Set Expansion (SSE) problem. This problem was suggested recently by Raghavendra and Steurer [RS10] (see also [RST10a, RST10b]) in the context of the unique games conjecture. Recall that the edge-expansion of a subset $S\subseteq V$ with $0<|S|\leq\tfrac{1}{2}|V|$ is

The input to the SSE problem is an edge-weighted graph and $\rho\in(0,\tfrac{1}{2}]$, and the goal is to compute

Raghavendra, Steurer and Tetali [RST10a] designed for SSE an algorithm that approximates the expansion within $O(\sqrt{(1/\Phi_{\rho})\log(1/\rho)})$ factor of the optimum, while violating the bound on $|S|$ by no more than a constant factor (namely, a bicriteria approximation). Notice that the approximation factor depends on $\Phi_{\rho}$; this is not an issue if every small set expands well, but in general $\Phi_{\rho}$ can be as small as $1/\textrm{poly}(n)$, in which case this guarantee is quite weak.

One can achieve a true approximation of $O(\log{n})$ for SSE using [Räc08], for any value of $\rho$.For very small values of $\rho$, roughly $\rho n\leq O(\log^{2}n)$, a better approximation ratio is known [FKN03]. If one desires a better approximation, then an approximation of $O(\sqrt{\log{n}})$ using [ARV08] can be achieved at the price of slightly violating the size constraint, namely a bicriteria approximation algorithm. However, unlike the former which works for any value of $\rho$, the latter works only for $\rho=\Omega(1)$. In our context of min-max problems we need the case $\rho=1/k$, where $k=k(n)$ is part of the input. Therefore, it is desirable to extend the $O(\sqrt{\log{n}})$ bound of [ARV08] to a large range of values for $\rho$.

Our two main results are bicriteria approximation algorithms for the Min–Max $k$–Partitioning and SSE problems, presented below. The notation $O_{\varepsilon}(t)$ hides multiplicative factors depending on $\varepsilon$, i.e., stands for $O(f(\varepsilon)\cdot t)$.

For every positive constant $\varepsilon>0$, Min–Max $k$–Partitioning admits a bicriteria approximation of \big{(}O_{\varepsilon}(\sqrt{\log{n}\log k}),\ 2+\varepsilon\big{)}.

This theorem provides a polynomial-time algorithm that with high probability outputs a partition $S_{1},\ldots,S_{k}$ such that $\max_{i}|S_{i}|\leq(2+\varepsilon)\tfrac{n}{k}$ and $\max_{i}\delta(S_{i})\leq O(\sqrt{\log{n}\log k})\mathsf{OPT}$, where $\mathsf{OPT}$ is the optimal min-max value of partitioning into $k$ equal-size parts. (The guarantee on part size can be improved slightly to $2-\frac{1}{k}+\varepsilon$). This result is most interesting in the regime $1\ll k\ll n$.

For every positive constant $\varepsilon>0$, Small-Set Expansion admits a bicriteria approximation of \big{(}O_{\varepsilon}(\sqrt{\log{n}\log{(1/\rho)}}),1+\varepsilon\big{)}.

This theorem provides a polynomial-time algorithm that with high probability outputs a set $S$ of size $0<|S|\leq(1+\varepsilon)\rho n$ whose edge-expansion is $\delta(S)/|S|=O(\sqrt{\log{n}\log{(1/\rho)}})\mathsf{OPT}$, where $\mathsf{OPT}$ is the minimum edge-expansion over all sets of size at most $\rho n$. Our algorithm actually handles a more general version, called Weighted Small-Set Expansion, which is required in Theorem 1.1. We defer the precise details to Section 2.

2 Additional Results and Extensions

Closely related to the SSE problem is the following $\rho$–Unbalanced Cut problem: The input is again a graph $G=(V,E)$ with nonnegative edge-weights and a parameter $\rho\in(0,\tfrac{1}{2}]$, and the goal is to find a subset $S\subseteq V$ of size $|S|=\rho n$ that minimizes $\delta(S)$. The relationship between this problem and SSE is similar to the one between Balanced Cut and Sparsest Cut, and thus Theorem 1.2 yields the following result.

For every constant $0<\varepsilon<1$, the $\rho$–Unbalanced Cut problem admits a bicriteria approximation of \big{(}O_{\varepsilon}(\sqrt{\log n\log(1/\rho)}),\Omega(1),1+\varepsilon\big{)}.

This theorem says that there is a polynomial-time algorithm that with high probability finds $S\subseteq V$ of size $\Omega(\rho n)\leq|S|\leq(1+\varepsilon)\rho n$ and value $\delta(S)\leq O_{\varepsilon}(\sqrt{\log{n}\log{(1/\rho)}})\mathsf{OPT}$, where $\mathsf{OPT}$ is the value of an optimal solution to $\rho$–Unbalanced Cut. This result generalizes the bound of [ARV08] from $\rho=\Omega(1)$ to any value of $\rho\in(0,\tfrac{1}{2}]$. Our factor is better than the $O(\log n)$ true approximation ratio that follows from [Räc08], at the price of slightly violating the size constraint. Our algorithm actually handles a more general version, called Weighted $\rho$-Unbalanced Cut, which is required in Theorem 1.1. We defer the precise details to Section 2.4.

Min-Max-Multiway-Cut.

We also consider the following Min-Max-Multiway-Cut problem, suggested by Svitkina and Tardos [ST04]: the input is an undirected graph with nonnegative edge-weights and $k$ terminal vertices $t_{1},\ldots,t_{k}$, the goal is to partition the vertices into $k$ parts $S_{1},\ldots,S_{k}$ (not necessarily balanced), under the constraint that each part contains exactly one terminal, so as to minimize $\max_{i}\delta(S_{i})$. They designed an $O(\alpha\log n)$–approximation algorithm for this problem, where $\alpha$ is the approximation factor known for Minimum Bisection. Plugging $\alpha=O(\log n)$, due to Räcke [Räc08], the algorithm of Svitkina and Tardos achieves $O(\log^{2}n)$-approximation. Using a similar algorithm to the one in Theorem 1.1, we obtain a better approximation factor.

Min-Max-Multiway-Cut admits an $O(\sqrt{\log{n}\log k})$–approximation algorithm.

Somewhat surprisingly, we show that removing the dependence on $n$ for Min-Max-Multiway-Cut (even though no balance is required) appears hard, which stands in contrast to its min-sum version, known as Multiway Cut, which admits $O(1)$–approximation [CKR00, KKS+04]. The idea is to show that it would imply a similar independence of $n$ for the min-sum version of $k$-partitioning, thus for large but constant $k$, we would get an $(O(1),O(1))$-bicriteria approximation for Min–Sum $k$–Partitioning, which seems unlikely based on the current state of art [ARV08, AR06, KNS09].

If there is a $k^{1-\varepsilon}$–approximation algorithm for Min-Max-Multiway-Cut for some constant $\varepsilon>0$, then there is a $(k^{2},\gamma)$ bicriteria approximation algorithm for Min–Sum $k$–Partitioning with $\gamma\leq 3^{2/\varepsilon}$.

Additionally, we also consider a common generalization of Min–Max $k$–Partitioning and Min-Max-Multiway-Cut, which we call Min–Max Cut. In fact we obtain Theorem 1.4 as a special case of our result for Min–Max Cut.

Excluded-minor graphs.

Finally, we obtain an improved approximation – constant factor – for SSE in graphs excluding a fixed minor.

For every constant $\varepsilon>0$, Small-Set Expansion admits:

bicriteria approximation of \big{(}O_{\varepsilon}(r^{2}),\ 1+\varepsilon\big{)} on graphs excluding a $K_{r,r}$-minor.

bicriteria approximation of \big{(}O_{\varepsilon}(\log g),\ 1+\varepsilon\big{)} on graphs of genus $g\geq 1$.

These bounds extend to the $\rho$–Unbalanced Cut problem, and by plugging them into the proof of Theorems 1.1 and 1.4, we achieve an improved approximation ratio of $O(r^{2})$ for Min–Max $k$–Partitioning and Min-Max-Multiway-Cut in graphs excluding a $K_{r,r}$-minor.

3 Techniques

For clarity, we restrict the discussion here mostly to our main application, Min–Max $k$–Partitioning. Our approach has two main ingredients. First, we reduce the problem to a weighted version of SSE, showing that an $\alpha$ (bicriteria) approximation for the latter can be used to achieve $O(\alpha)$ (bicriteria) approximation for Min–Max $k$–Partitioning. Second, we design an $O_{\varepsilon}(\sqrt{\log n\log(1/\rho)})$ (bicriteria) approximation for weighted SSE (recall that in our applications $\rho=1/k$).

For SSE on excluded-minor and bounded-genus graphs, we give a better approximation guarantees, of a constant factor, by extending the notion of orthogonal separators to linear programs (LPs) and designing such low-distortion “LP separators” for these special graph families. The proof uses the probabilistic decompositions of Klein, Plotkin, and Rao [KPR93] and Lee and Sidiropoulos [LS10]. We believe that this result may be of independent interest. Let us note that the LP formulation for SSE is not trivial and requires novel spreading constraints. We remark that even on planar graphs, the decomposition of Räcke [Räc08] suffers an $\Omega(\log n)$ loss in the approximation guarantee, and thus does not yield $o(\log n)$ ratio for SSE on this class of graphs.

We first show in Section 2 how to approximate Weighted Small-Set Expansion (in both general and excluded-minor graphs). We then show in Section 2.4 that an approximation algorithm for Weighted Small-Set Expansion also yields one for Weighted $\rho$-Unbalanced Cut. In Section 3 we present an approximation algorithm for Min–Max $k$–Partitioning that uses the aforementioned algorithm for $\rho$–Unbalanced Cut (and in turn the one for Weighted Small-Set Expansion). The common generalization of both Min–Max $k$–Partitioning and Min-Max-Multiway-Cut, Min–Max Cut, appears in Section 4. Theorem 1.5 is proved in Section 5.

Approximation Algorithms for Small Set Expansion

In this section we design approximation algorithms for the Small-Set Expansion problem. Our main result is for general graphs and uses an SDP relaxation. It actually holds for a slight generalization of the problem, where expansion is measured with respect to vertex weights (see Definition 2.1 and Theorem 2.1). We further obtain improved approximation for certain graph families such as planar graphs (see Section 2.3).

To simplify notation, we shall assume that vertex weights are normalized: we consider measures $\mu$ and $\eta$ with $\mu(V)=\eta(V)=1$. We denote $\mu(u)=\mu(\{u\})$ and $\eta(u)=\eta(\{u\})$. We let $(V,w)$ denote a complete (undirected) graph on vertex set $V$ with edge-weight $w(u,v)=w(v,u)\geq 0$ for every $u\neq v\in V$. In our context, such $(V,w)$ can easily model a specific edge set $E$, by simply setting $w(u,v)=0$ for every non-edge $(u,v)\notin E$. Recall that we let $\delta(S)\mathrel{\mathop{:}}=\sum_{u\in S,v\in V\setminus S}w(u,v)$ be the total weight of edges crossing the cut $(S,V\setminus S)$, and further let $w(E)$ denote the total weight of all edges.

Let $G=(V,w)$ be a graph with nonnegative edge-weights, and let $\mu$ and $\eta$ be two measures on the vertex set $V$ with $\mu(V)=\eta(V)=1$. The weighted small set expansion with respect to $\rho\in(0,1/2]$ is

(I) For every fixed $\varepsilon>0$, there is a polynomial-time algorithm that given as input an edge-weighted graph $G=(V,w)$, two measures $\mu$ and $\eta$ on $V$ ($\mu(V)=\eta(V)=1$), and some $\rho\in(0,1/2]$, finds a set $S\subset V$ satisfying $\eta(S)>0$, $\mu(S)\leq(1+\varepsilon)\rho$ and

where $D=O_{\varepsilon}(\sqrt{\log n\log(1/\rho)})$.

(II) When the input contains in addition a parameter $H\in(0,1)$, the algorithm finds a non-empty set $S\subset V$ satisfying $\mu(S)\leq(1+\varepsilon)\rho$, $\eta(S)\in[\Omega(H),2(1+\varepsilon)H]$, and

where $D=O_{\varepsilon}(\sqrt{\log n\log(\max\{1/\rho,1/H\})})$.

We prove part I of the theorem in Section 2.1, and part II in Section 2.2. These algorithms require the following notion of $m$-orthogonal separators due to Chlamtac, Makarychev, and Makarychev [CMM06].

For all $u\in X$ we have $\Pr(u\in S)=\alpha\,\|u\|^{2}$.

For all $u,v\in X$ with $\|u-v\|^{2}\geq\beta\min(\|u\|^{2},\|v\|^{2})$,

For all $u,v\in X$ we have $\Pr(I_{S}(u)\neq I_{S}(v))\leq\alpha D\times\|u-v\|^{2}$, where $I_{S}$ is the indicator function of the set $S$.

There exists a polynomial-time randomized algorithm that given a set of vectors $X$, positive number $m$, and $\beta<1$ generates $m$-orthogonal separator with distortion $D=O_{\beta}(\sqrt{\log|X|\log m})$ and scale $\alpha\geq 1/p(|X|)$ for some polynomial $p$.

In the original paper [CMM06], the second requirement in the definition of orthogonal separators was slightly different, however, exactly the same algorithm and proof works in our case: If $\|u-v\|^{2}\geq\beta\|u\|^{2}$ and $\|u\|^{2}\leq\|v\|^{2}$, then $\langle u,v\rangle=(\|u\|^{2}+\|v\|^{2}-\|u-v\|^{2})/2\leq((1-\beta)\|u\|^{2}+\|v\|^{2})/2\leq(1-\beta/2)\|v\|^{2}$. Then, by Lemma 4.1 in [CMM06], $\langle\varphi(u),\varphi(v)\rangle\leq(1-\beta/2)$; hence $\|\varphi(u)-\varphi(v)\|^{2}\geq\beta>0$ and, in Corollary 4.6, $\|\psi(u)-\psi(v)\|\geq 2\gamma=\sqrt{\beta}/4>0$.

In our relaxation we introduce a vector $\bar{v}$ for every vertex $v\in V$. In the intended solution of the SDP corresponding to the optimal solution $S\subset V$, $\bar{v}=1$ (or, a fixed unit vector $e$), if $v\in S$; and $\bar{v}=0$, otherwise. The objective is to minimize the fraction of cut edges

We denote $\eta(u)=\eta(\{u\})$ and $\mu(u)=\mu(\{u\})$. Finally, we introduce new spreading constraints: for every $u\in V$,

(Alternatively, we could use a slightly simpler, almost equivalent constraint $\sum_{v\in V}\langle\bar{u},\bar{v}\rangle\mu(v)\leq\rho\|\bar{u}\|^{2}$. We chose to use the former formulation because an analogous constraint can be written in a linear program, see Section 2.3.) In the intended solution this constraint is satisfied, since if $u\in S$, then $\bar{u}=1$ and the sum above equals $\mu(V\setminus S)\geq 1-\rho$. If $u\notin S$, then $\bar{u}=0$ and both sides of the constraint equal .

The SDP relaxation used in our algorithm is presented below in its entirety. Note that the second constraint can be written as ${\langle{u,v}\rangle}\leq\|u\|^{2}$, and the third constraint can be written as $\langle u,v\rangle\geq 0$.

We now describe the approximation algorithm.

Approximation Algorithm.

We may assume that $\varepsilon$ is sufficiently small i.e., $\varepsilon\in(0,1/4)$. The approximation algorithm guesses approximate value of the weight $H$: $H\leq\eta(S)\leq 2H$. Set the length of all vectors $\bar{u}$ with $\eta(u)>2H$ to be 0. Solves the SDP and obtains a set of vectors $X=\{\bar{v}\}_{v\in V}$. Then, it finds an orthogonal separator $S$ with $m=\max(\varepsilon^{-1}\rho^{-1})$ and $\beta=\varepsilon$. For convenience, we let $S$ be the set of vertices corresponding to vectors belonging to the orthogonal separator rather than the vectors themselves. The algorithm repeats the previous step ${\lceil{\alpha^{-1}n^{2}}\rceil}$ times (recall $\alpha$ is the probabilistic scale of the orthogonal separator) and outputs the best $S$ satisfying $0<\mu(S)<(1+10\varepsilon)\rho$. With an exponentially small probability no $S$ satisfies this constraint, in which case, the algorithm outputs an arbitrary set satisfying constraints.

Analysis.

We first estimate the probability of the event “$u\in S$ and $\mu(S)<(1+10\varepsilon)\rho$” for a fixed vertex $u\in V$. Let $A_{u}=\{v:\|\bar{u}-\bar{v}\|^{2}\geq\beta\|\bar{u}\|^{2}\}$ and $B_{u}=\{v:\|\bar{u}-\bar{v}\|^{2}<\beta\|\bar{u}\|^{2}\}$. We show that only a small fraction of $A_{u}$ belongs to $S$, and that the set $B_{u}$ is small.

Finally, we use the third property of orthogonal separators to bound the size of the cut $\delta(S)$

Here, as usual, $SDP$ denotes the value of the SDP solution; and $D=O_{\varepsilon}(\sqrt{\log n\log(1/\delta)})$ is the distortion of $m$-orthogonal separators.

if $|S|\neq\varnothing$, $\mu(S)<(1+10\varepsilon)\rho$, and $f(S)=0$, otherwise. The expectation

The random variable $f(S)$ is always bounded by $2nH$, thus with probability at least $\alpha/n$, $f(S)>0$. Therefore, with probability exponentially close to 1, after $\alpha^{-1}n^{2}$ iterations, the algorithm will find $S$ with $f(S)>0$. Since $f(S)>0$, we get $\eta(S)>0$, $\mu(S)<(1+10\varepsilon)\rho$, and

This finishes the proof of part I since $SDP/(2H)\leq\Phi_{\rho,\mu,\eta}(G)$.

2 Algorithm II: Small-Set Expansion in General Graphs

We now prove part II of Theorem 2.1. This algorithm uses an SDP relaxation similar to part I, although we need a few additional constraints. We write a constraint ensuring that “$\eta(S)\leq 2H$” (recall $H$ is an approximate value of $\eta(S)$ in the optimal solution): we add spreading constraints for all $u\in V$,

and we let $m=\max\{\varepsilon^{-1}\rho^{-1},H^{-1}\rho^{-1}\}$. We also require

Algorithm II gets $H$, the approximate value of the measure $\eta(S)$, as input, and thus does not need to guess it.

To handle terminals in the extended version of the problem (see Section 4) we guess which terminal $u\in T$ belongs to the optimal solution $S$ (if any), and set $\|\bar{u}\|=1$ and $\|\bar{v}\|=0$ for $v\in T\setminus\{u\}$. Since an orthogonal separator never contains the zero vector, we will never choose more than one terminal in the set $S$.

Approximation Algorithm. The algorithm consists of many iterations of a slightly modified Algorithm I. At every step the algorithm obtains a set $S$ of vertices (returned by Algorithm I) and adds it to the set $T$, which is initially empty. Then, the algorithm removes vectors corresponding to $S$ from the set $X$, the SDP solution, and repeats the same procedure till $\mu(T)\geq\rho/4$ or $\eta(T)\geq H/4$. In the end, the algorithm returns the set $T$ if $\mu(T)\leq\rho$ and $\eta(T)\leq H$, and the last set $S$ otherwise.

The algorithm changes the SDP solution (by removing some vectors), however we can ignore these changes, since the objective value of the SDP may only decrease and all constraints but (3) are still satisfied. Since the total weight $\eta(T)$ of removed vertices is at most $H/4$, a slightly weaker variant of constraint (3) is satisfied. Namely,

We now describe the changes in Algorithm I: instead of $f$, we define function $f^{\prime}$:

if $|S|\neq\varnothing$, $\mu(S)<(1+10\varepsilon)\rho$ and $\eta(S)\leq(1+10\varepsilon)H$ and $f^{\prime}(S)=0$, otherwise. Notice, that $f^{\prime}$ has an extra term comparing to $f$ and, in order for $f^{\prime}(S)$ to be positive, the constraint $\eta(S)\leq 2(1+10\varepsilon)H$ should be satisfied. The new variant of Algorithm I, returns $S$, once $f^{\prime}(S)>0$.

Again, after at most $O(\alpha^{-1}n^{2})$ iterations the algorithm will find $S$ with $f^{\prime}(S)>0$ (and only with exponentially small probability fail)In fact, now $f^{\prime}(S)\leq 2H$, thus we need only $O(\alpha^{-1}n)$ iterations.. Then, $f^{\prime}(S)>0$ implies

The last inequality implies that at every moment $\eta(T)\geq H\times\mu(T)/(4\rho)$. Hence, if $\mu(T)\geq\rho/4$ (recall, this is one of the two conditions, when the algorithm stops), then $\eta(T)\geq H/16$. Therefore, if the algorithm returns set $T$, then $\eta(T)\geq H/16$. If the algorithm returns set $S$ then either $\mu(S)\geq 3/4\,\rho$ and thus $\eta(S)\geq 3H/16$ or $\eta(S)\geq 3/4\,H$.

Both, $\mu(T)$ and $\eta(T)$ are bounded from above by $\rho$ and $H$ respectively; $\mu(S)$ and $\eta(S)$ are bounded from above by $(1+10\varepsilon)\rho$ and $2(1+10\varepsilon)H$ respectively.

The inequality (6) holds for every set $S$ added in $T$, hence this inequality holds for $T$.

3 Small-Set Expansion in Minor-Closed Graph Families

In this subsection we prove Theorem 1.6. We start by writing an LP relaxation. For every vertex $u\in V$ we introduce a variable $x(u)$ taking values in $$; and for every pair of vertices$u,v\in V$we introduce a variable$z(u,v)=z(v,u)$also taking values in$$. In the intended integral solution corresponding to a set$S\subset V$,$x(u)=1$if$u\in S$, and$x(u)=0$otherwise;$z(u,v)=|x(u)-x(v)|$. (One way of thinking of$x(u)$is as the distance to some imaginary vertex$O$that never belongs to$S$. In the SDP relaxation vertex$O$is the origin.) It is instructive to think of$x(u)$as an analog of$\|\bar{u}\|^{2}$and of$z(u,v)$as an analog of$\|\bar{u}-\bar{v}\|^{2}$.

It is easy to verify that LP (2.3) below is a relaxation of the Small-Set Expansion problem. It has a constraint saying that $z(u,v)$ is a metric (or, strictly speaking, semi-metric). A novelty of the LP is in the third constraint, which is a new spreading constraints for ensuring the size of $S$ is small.

We introduce an analog of $m$-orthogonal separators for linear programming, which we call LP separators.

Let $G=(V,E)$ be a graph, and let $\{x(u),z(u,v)\}_{u,v\in V}$ be a set of numbers. We say that a distribution over subsets of $V$ is an LP separator of $V$ with distortion $D\geq 1$, probability scale $\alpha>0$ and separation threshold $\beta\in(0,1)$ if the following conditions hold for $S\subset V$ chosen according to this distribution:

For all $u\in V$, $\Pr(u\in S)=\alpha\,x(u)$.

For all $u,v\in V$ with $z(u,v)\geq\beta\min\{x(u),x(v)\}$, $\Pr(u\in S\text{ and }v\in S)=0$.

For all $(u,v)\in E$, $\Pr(I_{S}(u)\neq I_{S}(v))\leq\alpha D\times z(u,v)$, where $I_{S}$ is an indicator for the set $S$.

Below we present an efficient algorithm for an LP separator: given a graph $G=(V,E)$ excluding $K_{r,r}$ as a minor, a parameter $\beta\in(0,1)$, and a set of numbers $\{x(u),z(u,v)\}_{u,v\in V}$ satisfying the triangle inequalities described above (but not necessarily the spreading constraints), the algorithm computes an LP separator with distortion $O(r^{2})$ (for genus $g$ graphs the distortion is $O(\log g)$). This proves Theorem 1.6 as follows: by replacing in the algorithms above the SDP relaxation (2.1) with the LP relaxation (2.3), and the orthogonal separators with LP separators, we obtain $O(r^{2})$ approximation algorithm approximation algorithm for SSE in $K_{r,r}$ excluded-minor graphs. Combined with the framework in Section 3, we consequently obtain an $O(r^{2})$-approximation algorithm for Min–Max $k$–Partitioning and Min-Max-Multiway-Cut on such graphs.

We now describe an algorithm that samples an LP separator (see Definition 2.4) with respect to a feasible solution to LP (2.3). We recall a standard notion of low-diameter decomposition of a metric space, see e.g. [Bar96, GKL03, KR11] and references therein.

Let $(V,d)$ be a finite metric space. Given a partition $P$ of $V$ and a point $v\in V$, we refer to the elements of $P$ as clusters, and let $P(v)$ denote the cluster $S\in P$ that contains $v$, so $v\in S\in{\mathcal{P}}$. A stochastic decomposition of this metric is a probability distribution $\nu$ over partitions $P$ of $V$.

Let $D,\Delta>0$. A stochastic decomposition $\nu$ of a finite metric space $(V,d)$ is called a $D$-separating $\Delta$-bounded decomposition if it satisfies:

For every partition $P\in\operatorname{supp}(\nu)$ and every cluster $S\in P$,

For every $u,v\in V$, the probability that a partition $P$ sampled from $\nu$ separates them is

Let $G=(V,E)$ be a graph excluding $K_{r,r}$ as a minor, equipped with nonnegative edge-lengths. Then the graph’s shortest-path metric $d_{G}$ admits, for every $\Delta>0$, an $O(r^{2})$-separating $\Delta$-bounded decomposition. Moreover, there is a polynomial-time algorithm that samples a partition from this distribution.

Lee and Sidiropoulos [LS10] show similarly for graphs with genus $g\geq 1$ an $O(\log g)$-separating decomposition. Alternative algorithms for both cases are shown in [KR11].

Consider a graph $G=(V,E)$ and nonnegative numbers $\{x(u),z(u,v)\}_{u,v\in V}$. We say that a distribution $\nu$ over partitions of $V$ is called a probabilistic partitioning with distortion $D>0$ and separation threshold $\beta>0$ if the following properties hold:

For every edge $(u,v)\in E$ with $x(u)>0$:

For every $u,v\in V$ with $z(u,v)\geq\beta x(u)$, we have $P(u)\neq P(v)$ for all $P\in\operatorname{supp}(\nu)$.

Let $G=(V,E)$ be a graph that excludes $K_{r,r}$ as a minor, and let $\{x(u),z(u,v)\}_{u,v\in V}$ satisfy the first two constraints of LP (2.3). Then for every $\beta\in(0,1]$, there is a probabilistic partitioning $\nu$ with distortion $D=O(r^{2}\beta^{-1})$ and separation threshold $\beta$.

For all $u,v\in V$ we have $d(u,v)\geq\tfrac{2}{3}\,y(u,v)$.

Pick two vertices $u,v\in V$ and consider an arbitrary path $u=w_{1},w_{2},\dots,w_{N}=v$. We prove that the length of the path (in which the length of each edge $(w_{i},w_{i+1})$ is $y(w_{i},w_{i+1})$) is at least $\tfrac{2}{3}\,y(u,v)$. If the length of the path is greater than $2/3$ we are done. Thus, we may assume that the lengths of all edges are at most $2/3<1$. We also assume that $x(u)\geq x(v)$ and thus $y(u,v)\leq z(u,v)/x(u)$. We have,

The second inequality holds since $z(\cdot,\cdot)$ is a metric. If $x(u)/\max_{i}(x(w_{i}))\geq 2/3$, we are done. Assume that for $j=\operatorname{argmax}x(w_{j})$, $x(u)/x(w_{j})<2/3$. Then,

We now apply the theorem of Klein, Plotkin, and Rao [KPR93] to the metric $d(u,v)$ and obtain a probabilistic partition ${\mathcal{P}}$ with $\Delta=\beta/3$ and $D^{\prime}=O(r^{2})$. This partition satisfies the following properties.

If $z(u,v)\geq\beta x(u)$ for $u,v\in V$, then either $x(u)\geq x(v)$ and hence $y(u,v)\geq\beta$, or $x(v)\geq x(u)$, then (using $z(u,v)\geq x(v)-x(u)$)

Thus, $y(u,v)\geq\beta/2$ in either case and $d(u,v)\geq 2/3\,y(u,v)\geq\beta/3\equiv\Delta$ (by Claim 2.5).

The distortion $D$ equals $D^{\prime}/\Delta=O(r^{2}/\beta)$. ∎

Given a solution for LP (2.3) (the relaxation for SSE problem), we could proceed as follows: Construct a probabilistic partition ${\mathcal{P}}$ with distortion $D=O(r^{2}\beta^{-1})$ and some constant separation threshold $\beta\in(0,1)$, then pick a random vertex $w\in V$ with probability $x(w)\eta(w)\left/\sum_{u}x(u)\eta(u)\right.$ and, finally, output the cluster $P_{w}$. However, to highlight the similarity between this LP-algorithm and the previous SDP-algorithm (for general graphs), we give an algorithm for constructing LP separators, which in turn is used by the Small-Set Expansion algorithm.

There exists an algorithm that given a graph $G=(V,E)$ with an excluded minor $K_{r,r}$, a set of numbers $\{x(u),z(u,v)\}_{u,v\in V}$ satisfying the triangle inequality constraints, and a parameter $\beta\in$, returns an LP separator $S\subset V$ with distortion $D=r^{2}\beta^{-1}$ and separation threshold $\beta$.

Algorithm. The algorithm samples a random partition $P$ with distortion $D=O(r^{2}\beta^{-1})$ and a separation threshold $\beta$. For every $C\in P$, let

The algorithm picks a random set $S\in P$ with probability $\Pr(S=C)=x_{\infty}(C)/n$; and with the remaining probability

Now, to guarantee that every vertex $u$ is chosen with probability exactly $\alpha x(u)$, where $\alpha=1/n$, the algorithm removes some elements from $S$: it picks at random $t\in$ and outputs set

Analysis. Verify that $S^{\prime}$ satisfies the properties of LP separators (with $\alpha=1/n$). For every $u\in V$,

Then, if $z(u,v)\geq\min(x(u),x(v))$, then $P(u)\neq P(v)$ and hence

We estimate the first term (using that $\nu$ has distortion $D=O(r^{2}\beta^{-1})$; see Definition 2.6)

4 From SSE to ρ𝜌\rho–Unbalanced Cut

$\rho$–Unbalanced Cut and SSE are equivalent, up to some constants, with respect to bicriteria approximation guarantees. Indeed, the two problems are related in the same way that Balanced Cut and Sparsest Cut are. We refer the reader to [LR99, RST10a], and omit details from this version of the paper.

Our intended application of approximating Min–Max $k$–Partitioning (in Section 3), requires a weighted version of the $\rho$–Unbalanced Cut problem, as follows.

The unweighted version of the problem (defined in Section 1.2) has $\tau=\rho$ and unit vertex-weights, i.e. $y(v)=1$ for all $v\in V$. We focus on the direction of reducing Weighted $\rho$-Unbalanced Cut to Weighted Small-Set Expansion, which is needed for our intended application. Formally, we have the following corollary of Theorem 2.1. We use $\mathsf{OPT}_{{\langle{G,y,w,\tau,\rho}\rangle}}$ to denote the optimal value of the corresponding weighted $\rho$–Unbalanced Cut instance.

For every $\varepsilon>0$, there exists a polynomial-time algorithm that given an instance ${\langle{G,y,w,\tau,\rho}\rangle}$ of Weighted $\rho$-Unbalanced Cut, finds a set $S$ satisfying $|S|\leq\beta\rho n$, $y(S)\geq\tau/\gamma$ and $\delta(S)\leq\alpha\cdot\mathsf{OPT}_{{\langle{G,y,w,\tau,\rho}\rangle}}$ for $\alpha=O_{\varepsilon}(\sqrt{\log n\log(\max(1/\rho,1/\tau))})$, $\beta=1+\varepsilon$ and $\gamma=O(1)$.

Let $S^{*}$ be an optimal solution to ${\langle{G,y,w,\tau,\rho}\rangle}$, note that $|S^{*}|\leq\rho n$, $y(S^{*})\geq\tau\cdot y(V)$ and $\delta(S^{*})=\mathsf{OPT}_{{\langle{G,y,w,\tau,\rho}\rangle}}$ the optimal value of this instance. Define two measures on $V$ as follows. For any $S\subseteq V$, set $\mu(S):=|S|/n$ and $\eta(S)\mathrel{\mathop{:}}=y(S)/y(V)$.

The algorithm guesses $H\geq\tau$ such that $H\leq\eta(S^{*})\leq 2H$ (see Algorithm I above for an argument why we can guess $H$). Then it invokes the algorithm from part II on $G$ with measures $\mu$ and $\eta$ as defined above, and parameters $\rho,H$. The obtained solution $S$ satisfies $|S|=\mu(S)\cdot n\leq(1+\varepsilon)\rho\,n$ and $y(S)=\eta(S)\cdot y(V)\geq\Omega_{\varepsilon}(1)\,H\cdot y(V)\geq\Omega_{\varepsilon}(1)\,\tau\cdot y(V)$, since $H\geq\tau$. Furthermore, $\delta(S)\leq\alpha\cdot\delta(S^{*})\cdot\eta(S)/\eta(S^{*})\leq\alpha\cdot\delta(S^{*})\cdot\Theta_{\varepsilon}(1)$, where $\alpha=O_{\varepsilon}(\sqrt{\log n\log(\max(1/\rho,1/\tau))})$. ∎

Min-max Balanced Partitioning

In this section, we present our algorithm for Min–Max $k$–Partitioning, assuming a subroutine that approximates Weighted $\rho$-Unbalanced Cut (which is essentially a rephrasing of Weighted Small-Set Expansion). Our algorithm for Min–Max $k$–Partitioning follows by a straightforward composition of Theorem 3.1 and Theorem 3.3 below. Plugging in for $(\alpha,\beta,\gamma)$ the values obtained in Section 2 would complete the proof of Theorem 1.1.

We first consider a covering relaxation of Min–Max $k$–Partitioning and solve it using multiplicative updates. This covering relaxation can alternatively be viewed as a fractional solution to a configuration LP of exponential size, as discussed further below.

Let $\mathcal{C}=\left\{S\subseteq V:\,|S|\leq n/k\right\}$ denote all the vertex-sets that are feasible for a single part. Note that a feasible solution in Min–Max $k$–Partitioning corresponds to a partition of $V$ into $k$ parts, where each part belongs to $\mathcal{C}$. Algorithm 1, described below, uniformly covers $V$ using sets in $\mathcal{C}$ (actually a slightly larger family than $\mathcal{C}$). It is important to note that its output ${\mathcal{S}}$ is a multiset.

Running Algorithm 1 on an instance of Min–Max $k$–Partitioning outputs ${\mathcal{S}}$ that satisfies (here $\mathsf{OPT}$ denotes the optimal value of the instance):

For all $S\in{\mathcal{S}}$ we have $\delta(S)\leq\alpha\cdot\mathsf{OPT}$ and $|S|\leq\beta\cdot n/k$.

For all $v\in V$ we have $|\{S\in{\mathcal{S}}:S\ni v\}|/|{\mathcal{S}}|\geq 1/(5\gamma k)$.

For an iteration $t$, let us denote $Y^{t}\mathrel{\mathop{:}}=\sum_{v\in V}y^{t}(v)$. The first assertion of the theorem is immediate from the following claim.

Every iteration $t$ of Algorithm 1 satisfies $\delta(S^{t})\leq\alpha\cdot\mathsf{OPT}$ and $|S^{t}|\leq\beta\cdot n/k$.

It suffices to show that the optimal value of the Weighted $\rho$-Unbalanced Cut instance $\langle G,\,y^{t},\,w,\,\frac{1}{k},\,\frac{1}{k}\rangle$ is at most $\mathsf{OPT}$. To see this, consider the optimal solution $\{S^{*}_{i}\}_{i=1}^{k}$ of the original Min–Max $k$–Partitioning instance. We have $|S^{*}_{i}|\leq n/k$ and $w(\delta(S^{*}_{i}))\leq\mathsf{OPT}$ for all $i\in[k]$. Since $\{S^{*}_{i}\}_{i=1}^{k}$ partitions $V$, there is some $j\in[k]$ with $y^{t}(S^{*}_{j})\geq Y^{t}/k$. It now follows that $S^{*}_{j}$ is a feasible solution to the Weighted $\rho$-Unbalanced Cut instance $\langle G,\,y^{t},\,w,\,\frac{1}{k},\,\frac{1}{k}\rangle$, with objective value at most $\mathsf{OPT}$, which proves the claim. ∎

We now describe an alternate approach to finding a cover ${\mathcal{S}}$. Given a bound $\lambda$ on the cost of any single cut, define the set of feasible cuts as follows:

We define a configuration LP for Min–Max $k$–Partitioning as follows. There is a variable $x_{S}$ for each $S\in\mathcal{F}_{\lambda}$ indicating whether/not cut $S$ is chosen.

The goal is determine the smallest $\lambda>0$ such that ${\mathcal{P}}(\lambda)\leq k$. One can approximately solve this using the dual formulation:

The dual separation oracle can be solved using Weighted Small-Set Expansion; so we can apply the Ellipsoid algorithm. Since we only have a multi-criteria approximation for Weighted Small-Set Expansion (see Section 2), the details for approximating the configuration LP are rather technical.

2 Aggregation

The aggregation process, which might be of independent interest, transforms a cover of $G$ into a partition. Intuitively, we first let the sets randomly compete with each other over the vertices so as to form a partition; then, to make sure no set has large cost, we repeatedly fix the partition locally, and use a potential function to track progress.

2. After each iteration of step 2, the following invariant holds: the collection of sets $\{P_{i}\}$ is a partition of $V$ and $P_{i}\subset S_{i}$ for all $i$. Particularly, $|P_{i}|\leq|S_{i}|\leq 2n/k$. The key observation is that at every iteration of the “while” loop, the sum $\sum_{j}\delta(P_{j})$ decreases by at least $2B$. This is due to the following uncrossing argument:

3. The following analysis holds conditional on any value of $B^{\prime}$. After each iteration of step 3, the following invariant holds: the collection of sets $\{P_{i}\}$ is a partition of $V$. Moreover, $|P_{i}|\leq 2(1+\varepsilon)n/k$ and $\delta(P_{i})\leq 2B^{\prime}\varepsilon^{-1}$ (note: after step 2, $\delta(P_{i})\leq 2B\leq B^{\prime}$ for each $i$).

When the loop terminates, we obtain a partition of $V$ into sets $P_{i}$ satisfying $|P_{i}|\leq 2(1+\varepsilon)n/k$, $\sum_{i}|P_{i}|=n$, $\delta(P_{i})\leq 2B^{\prime}\varepsilon^{-1}$, $\sum_{i}\delta(P_{i})\leq kB^{\prime}$, such that no two sets can be merged without violating above constraints. Hence by Lemma 3.4 below (with $a_{i}=|P_{i}|$ and $b_{i}=\delta(P_{i})$), the number of non-empty sets is at most $2\;\frac{n}{2(1+\varepsilon)n/k}+\frac{kB^{\prime}}{2B^{\prime}\varepsilon^{-1}}=(1+\varepsilon)^{-1}k+(\varepsilon/2)k\leq k.$ ∎

Let $a_{1},\dots,a_{t}$ and $b_{1},\dots b_{t}$ be two sequences of nonnegative numbers satisfying the following constraints $a_{i}<A$, $b_{i}<B$, $\sum_{i=1}^{t}a_{i}\leq S$ and $\sum_{i=1}^{t}b_{i}\leq T$ (for some positive real numbers $A$, $B$, $S$, and $T$). Moreover, assume that for every $i$ and $j$ ($i\neq j$) either $a_{i}+a_{j}>A$ or $b_{i}+b_{j}>B$. Then, $t<S/A+T/B+\max(S/A,T/B,1)$.

By rescaling we assume that $A=1$ and $B=1$. Moreover, we may assume that $\sum_{i=1}^{t}a_{i}<S$ and $\sum_{i=1}^{t}b_{i}<T$ by slightly decreasing values of all $a_{i}$ and $b_{i}$ so that all inequalities still hold.

We write two linear programs. The first LP ($LP_{I}$) has variables $x_{i}$ and constraints $x_{i}+x_{j}\geq 1$ for all $i,j$ such that $a_{i}+a_{j}\geq 1$. The second LP ($LP_{II}$) has variables $y_{i}$ and constraints $y_{i}+y_{j}\geq 1$ all $i,j$ such that $b_{i}+b_{j}\geq 1$. The LP objectives are to minimize $\sum_{i}x_{i}$ and to minimize $\sum_{i}y_{i}$. Note, that $\{a_{i}\}$ is a feasible point for $LP_{I}$ and $\{b_{i}\}$ is a feasible point for $LP_{II}$. Thus, the optimum values of $LP_{I}$ and $LP_{II}$ are strictly less than $S$ and $T$ respectively.