Online Bisection with Ring Demands Mateusz Basiak, Marcin Bienkowski, Guy Even, Agnieszka Tatarczuk Abstract The online bisection problem requires maintaining a dynamic partition of n n nodes into two equal-sized clusters. Requests arrive sequentially as node pairs. If the nodes lie in different clusters, the algorithm pays unit cost. After each request, the algorithm may migrate nodes between clusters at unit cost per node. This problem models datacenter resource allocation where virtual machines must be assigned to servers, balancing communication costs against migration overhead. We study the variant where requests are restricted to edges of a ring network, an abstraction of ring-allreduce patterns in distributed machine learning. Despite this restriction, the problem remains challenging with an Ω ⁡ ( n ) \Omega(n) deterministic lower bound. We present a randomized algorithm achieving O ⁡ ( ε − 3 ⋅ log 2 ⁡ n ) O(\varepsilon^{-3}\cdot\log^{2}n) competitive ratio using resource augmentation that allows clusters of size at most ( 3 / 4 + ε ) ⋅ n (3/4+\varepsilon)\cdot n . Our approach formulates the problem as a metrical task system with a restricted state space. By limiting the number of cut-edges (i.e., ring edges between clusters) to at most 2 ​ k 2k , where k = Θ ⁡ ( 1 / ε ) k=\Theta(1/\varepsilon) , we reduce the state space from exponential to polynomial (i.e., n O ⁡ ( k ) n^{O(k)} ). The key technical contribution is proving that this restriction increases cost by only a factor of O ⁡ ( k ) O(k) . Our algorithm follows by applying the randomized MTS solution of Bubeck et al. [SODA 2019]. The best result to date for bisection with ring demands is the O ⁡ ( n ⋅ log ⁡ n ) O(n\cdot\log n) -competitive deterministic online algorithm of Rajaraman and Wasim [ESA 2024] for the general setting. While prior work for ring-demands by Räcke et al. [SPAA 2023] achieved O ⁡ ( log 3 ⁡ n ) O(\log^{3}n) for multiple clusters, their approach employs a resource augmentation factor of 2 + ε 2+\varepsilon , making it inapplicable to bisection. University of Wrocław, Polandmateusz.basiak@cs.uni.wroc.plhttps://orcid.org/0009-0009-0210-6451 University of Wrocław, Polandmarcin.bienkowski@cs.uni.wroc.plhttps://orcid.org/0000-0002-2453-7772 School of Electrical Engineering, Tel-Aviv University, Tel Aviv, Israel and Max Planck Institute for Informatics, Saarbrücken, Germanyguyeven@mpi-inf.mpg.dehttps://orcid.org/0000-0001-5407-330X University of Wrocław, Polandagnieszka.tatarczuk@cs.uni.wroc.plhttps://orcid.org/0009-0008-3849-9165 ccs Theory of computation Online algorithms keywords Online Bisection, Competitive Analysis, Resource Augmentation, Ring Network † † runningauthor: M. Basiak, M. Bienkowski, G. Even and A. Tatarczuk † † copyright: Mateusz Basiak, Marcin Bienkowski, Guy Even and Agnieszka Tatarczuk † † funding: Supported by Polish National Science Centre grant 2022/45/B/ST6/00559. For the purpose of open access, the authors have applied CC-BY public copyright license to any Author Accepted Manuscript (AAM) version arising from this submission. 1 Introduction This work is motivated by the increasing interest in online graph partitioning problems. Among these, one of the most elegant and succinctly defined problems is the online bisection problem [ AvLoPS16 ] . The goal is to maintain a time-varying partition of n nodes into two clusters, each of capacity n/2 . The input is a sequence of requests, each corresponding to a pair of nodes. Serving a pair whose nodes are in different clusters incurs a unit cost, while serving requests between nodes in the same cluster is free. After serving a request, the algorithm may update the partition, paying a unit cost for each node that changes clusters. The objective is to minimize the total incurred cost. This is an online problem : requests arrive sequentially, and the algorithm has to serve each before observing the next. The performance of an algorithm is measured by its competitive ratio [ BorEl-98 ] , defined as the worst-case ratio between its total cost and that of an optimal offline algorithm Opt that knows the entire sequence in advance. Motivation. Node pairs are ephemeral: once a request is served, it no longer incurs any cost. The online bisection problem models trade-offs that naturally arise in datacenters, where virtual machines (nodes) exchanging data have to be assigned to racks or physical servers (clusters). When two virtual machines are colocated (in the same cluster), their communication is cost-free; otherwise, it incurs latency and consumes bandwidth. Modern virtualization enables migration of virtual machines between servers (i.e., changes of node clusters), but such migrations incur network cost of their own. 1.1 Previous results. This seemingly simple problem has proved surprisingly challenging, and despite substantial effort over the past decade, our understanding remains limited. Exact online bisection. The first algorithm, proposed by Avin et al. [ AvLoPS16 , AvBLPS20 ] , was a simple deterministic O(n^{2}) -competitive algorithm that maintained connected components of nodes that had communicated so far, mapping each component to a single cluster. This idea was later refined by Bienkowski and Schmid [ BieSch24 ] , who proved that a slightly randomized version of this approach achieves a sub-quadratic competitive ratio of \widetilde{O}(n^{2-1/{12}}) . A polynomial dependence on n is unavoidable for deterministic algorithms: via a reduction from online paging [ SleTar85 ] , one obtains a lower bound of \Omega(n) [ AvBLPS20 ] . For randomized algorithms, however, the known lower bound is merely \Omega(\log n) [ HeNeRS21 ] , leaving an exponential gap between the best upper and lower bounds. 1 1 1 The lower bound of [ HeNeRS21 ] was established for the so-called learning-model, but repeating their construction multiple times yields a lower bound for the general variant of the problem. Resource augmentation. The limited progress on exact bisection prompted the exploration of resource-augmented variants, where the online algorithm is permitted to relax the requirement of equal-sized clusters. More precisely, a (1+\varepsilon) -augmented algorithm allows at most (1+\varepsilon)\cdot(n/2) nodes in each cluster, while being compared against a non-augmented Opt with clusters of equal size n/2 . We refer to 1+\varepsilon as the augmentation factor or balance parameter of the algorithm. This relaxation is well motivated in practice because servers often have spare capacity that can be exploited to improve performance. Surprisingly, the lower bound for deterministic algorithms in this setting remains \Omega(n) , and it holds for any nontrivial amount of augmentation, as long as it is not possible to place all nodes in a single cluster [ AvBLPS20 ] . On the positive side, Rajaraman and Wasim [ RajWas22 ] presented an O(n\log n) -competitive deterministic algorithm for any fixed \varepsilon>0 . 2 2 2 Their algorithm also applies to the multi-cluster variant and uses an approach of Henzinger et al. [ HeNeRS21 ] as a subroutine, thereby inheriting an exponential dependence on 1/\varepsilon hidden in the O -notation. However, for the online bisection, a straightforward extension of the component-based algorithm of [ AvBLPS20 ] to the resource-augmented setting would trivially yield an O(\varepsilon^{-1}\cdot n\log n) -competitive algorithm. No randomized algorithm achieving a better bound than O(n\log n) is known. Multiple clusters. The online bisection problem has also been studied in a generalized form, known as online balanced graph partitioning , where there are \ell\geq 2 clusters, each of size n/\ell [ AvBLPS20 , AvLoPS16 , BBKRSV21 , FoRSc21 , PaPaSc21 , RScZa22 , RajWas22 ] . This generalization has also been investigated in models with a large augmentation factor of 1+\varepsilon\geq 2 [ AvBLPS20 , AvLoPS16 , FoRSc21 , RScZa22 ] , which would trivialize the online bisection problem, as all nodes could then be placed in a single cluster. Ring demands. Another natural restriction is to assume that requests must belong to a predefined subset Q\subseteq V\times V that is known a priori to the online algorithm. The case when Q is a cycle connecting all nodes is of particular theoretical and practical interest. In fact, the ring-allreduce communication pattern [ SerBal18 ] used in distributed machine learning follows this structure. For the theoretical perspective, the deterministic lower bound of \Omega(n) holds even under ring demands [ AvLoPS16 , AvBLPS20 ] . Ring demands were also studied by Räcke et al. in the multi-cluster case, for which they presented an O(\log^{3}n) -competitive randomized algorithm [ RScZa23 ] . However, their algorithm crucially requires an augmentation factor 2+\varepsilon , which makes it inapplicable to the online bisection problem. 1.2 Our Contribution In this work, we present a randomized online algorithm for the online bisection problem with ring demands. The augmentation factor is 3/2+\varepsilon , for \varepsilon\in(0,1/2] , 3 3 3 In other words, each cluster may contain at most (3/4+\varepsilon/2)\cdot n nodes. and the competitive ratio is O(\varepsilon^{-3}\cdot\log^{2}n) . For this setting, the best known solution to date is the (1+\varepsilon) -augmented, O(n\log n) -competitive deterministic algorithm by Rajaraman and Wasim [ RajWas22 ] , which remains the state of the art even when randomization and arbitrarily high augmentation are permitted. Overview. The bisection problem can be viewed as a metrical task system (MTS) [ BoLiSa92 ] in which every state is a partition, and distances between states are the “edit distances” between these partitions. Let \mathcal{S} denote the set of states. The randomized online MTS algorithm of Bubeck et al. [ BuCoLL19 ] yields a competitive ratio O(\log^{2}|\mathcal{S}|) , which is O(n^{2}) since |S|=\binom{n}{n/2} . To reduce the competitive ratio, we restrict the number of states to n^{O(k)} , for k=\Theta(1/\varepsilon) , as follows. Any partition of the cycle into two clusters can be represented by an even set of cut-edges , meaning ring edges between nodes assigned to different clusters. A natural choice for restricting the state space is to consider sets of at most 2k cut-edges. More formally, let MTS (2k,\alpha) denote the MTS in which every state is an \alpha -balanced partition induced by at most 2k cut-edges. As the number of states of this MTS is O(n^{O(k)}) , the randomized online MTS algorithm of Bubeck et al. [ BuCoLL19 ] has cost at most O(k^{2}\cdot\log^{2}n) times that of an optimal offline \alpha -balanced algorithm using at most 2k cut-edges. This approach shifts the challenge to bounding the increase in cost caused by this sparsification of the set of states, i.e., bounding the ratio between the costs of the optimal solutions for MTS (n,1) and MTS (2k,\alpha) . We succeed in bounding this ratio by O(k) if \alpha=3/2+1/k (see Theorem 2 ). Our analysis works in phases in which an offline solution Off for MTS (2k,\alpha) (for \alpha=3/2+1/k ) “chases” an optimal solution Opt for MTS (n,1) until the \alpha -balance parameter is violated. At all times, we maintain the invariant that the cut-edges in Off form a subset of the cut-edges of Opt . This invariant guarantees that a request incurs a cost on Off only if it incurs cost on Opt . At the beginning of each phase, we start by sparsifying the cut-edges of Opt to a subset of cardinality at most 2k . 1 proves that this is possible with balance parameter of 1+1/k . The phase proceeds with Off iteratively responding to changes in Opt and ends when this response leads to a partition that is no longer \alpha -balanced. We show that changes in Off (in response to the single-node changes of Opt ) incur amortized cost that is bounded by the cost of Opt within the phase (see 12 ). Moreover, the O(n) rebalancing cost per phase can be charged to the cost of Opt within the phase, which we lower-bound by \Omega(n/k) (see 14 ). Comparison to prior work. Superficially, our algorithm shares certain similarities (the notion of cut-edges and the use of MTS routines) with the algorithm of Räcke et al. [ RScZa23 ] , but the underlying mechanisms differ. In particular, in their approach, the number of cut-edges corresponds to the number of clusters, whereas in our case it serves as a parameter that affects both the cost and the augmentation factor. Moreover, the partition of the cycle in their approach is more rigid, since cut-edges are confined to specific segments of the cycle that remain fixed throughout the execution, whereas in our approach the partition is more flexible, allowing cut-edges to appear anywhere on the cycle. 1.3 Other Related Work The online bisection problem and its generalization to the online balanced partitioning problem were also studied in several relaxed variants, such as the learning model (where the input admits a partition incurring no service cost) [ HeNeRS21 , HeNeSc19 , PaPaSc20 , PaPaSc21 , RScZa23 , RScZa25 ] and stochastic inputs [ AvCoPS19 ] . The offline counterparts of these problems (bisection and k -balanced partitioning) are NP-hard, and their approximation ratios have been improved in a long line of works; see [ SarVaz95 , ArKaKa99 , FeKrNi00 , FeiKra02 , KraFei06 , Raec08 ] for bisection and [ SimTen97 , KrNaSc09 , AndRae06 , EvNaRS99 ] for k -balanced partitioning. Recently, balanced partitioning was also studied in a setting where the input and output are as in the online model, but the algorithm operates offline and has access to the entire input [ RScZa22 ] . Closely related online problems include online disengagement (a “dual” of online bisection, where the algorithm pays for requests whose endpoints lie in the same cluster) [ AzMaPT23 , PaRoUm25 , RajWas24 ] and the minimum linear arrangement problem, where the goal is to maintain a dynamically changing linear ordering of nodes [ BieEve24 , OlPSSS18 ] . 1.4 Problem Definition In the online bisection problem, we are given n nodes v_{1},v_{2},\dots,v_{n} , where n is even. Instead of defining the problem in terms of partitions, we use an equivalent but more convenient coloring formulation: the algorithm maintains a coloring of all nodes with two colors, red and blue. There is a fixed initial coloring, where half of the nodes are colored red and the other half blue. Requests arrive online. Each request is a pair of nodes, referred to as its endpoints. For every request in an input sequence: • if its endpoints have the same color, the algorithm pays a hit cost of 0 ; • if its endpoints have different colors, the algorithm pays a hit cost of 1 ; • after paying the hit cost, the algorithm may recolor any number of nodes, paying a recoloring cost equal to the number of recolored nodes. For an algorithm Alg and input \sigma , we write \textsc{Alg}(\sigma) for the total cost on \sigma . We denote by \textsc{Alg}_{\textrm{HIT}} and \textsc{Alg}_{\textrm{REC}} the hit cost and recoloring cost , respectively. Resource augmentation. A coloring is \alpha -balanced (for \alpha\geq 1 ) if at most \alpha\cdot(n/2) nodes are assigned each color. An algorithm is \alpha -augmented if, once it performs the recoloring in response to a request, the resulting coloring is \alpha -balanced. An ( \alpha -augmented) algorithm Alg is R -competitive if there exists \beta such that, for every input \sigma , it holds that \textsc{Alg}(\sigma)\leq R\cdot\textsc{Opt}(\sigma)+\beta , where Opt denotes the optimal offline algorithm that maintains a 1 -balanced coloring. The parameter \beta cannot depend on \sigma , but may be a function of n . For randomized algorithms, we replace \textsc{Alg}(\sigma) above by its expected value and assume standard, oblivious adversary [ BorEl-98 ] that does not see random bits used by the algorithm. Ring demands. In the variant studied in this paper, all requests correspond to edges of a cycle. Thus, there are n possible request types: (v_{1},v_{2}),(v_{2},v_{3}),\dots,(v_{n},v_{1}) . 2 Outline of Our Solution We show that for every \varepsilon\in(0,1/2] , there exists an online (3/2+\varepsilon) -augmented randomized algorithm that is O(\varepsilon^{-3}\cdot\log^{2}n) -competitive. Below we outline our approach, starting with several necessary definitions. Cut-edges. At any time, the coloring maintained by algorithm Alg induces a set of cut-edges , denoted \textsc{cut}(\textsc{Alg}) , consisting of edges of the cycle whose endpoints have different colors. Note that |\textsc{cut}(\textsc{Alg})| is even. Conversely, each even-cardinality set \mathcal{C} of cut-edges corresponds to two equivalent colorings of the nodes, obtained from each other by swapping color names. A set of cut-edges is valid if its cardinality is even. Hence, a valid set \mathcal{C} of cut-edges uniquely represents a coloring, up to a swap of color names. Fix any valid set \mathcal{C} of cut-edges. The set \mathcal{C} partitions the cycle into monochromatic arcs of alternating colors. Each such arc consists entirely of red or blue nodes, and we refer to it as a red or blue arc, respectively. We also define other arcs: for edges e_{i} and e_{j} , let A(e_{i},e_{j}) denote the set of nodes on the shorter path between e_{i} and e_{j} along the cycle. Let d(e_{i},e_{j})\triangleq|A(e_{i},e_{j})| . Color frequency. For a given coloring, a color is called more frequent if the number of nodes of that color exceeds n/2 , and less frequent otherwise. When both colors contain exactly n/2 nodes, either color may be treated as more frequent. For a valid set \mathcal{C} of cut-edges, let \textsc{less}(\mathcal{C}) denote the number of nodes assigned the less frequent color in the coloring induced by \mathcal{C} ; cf. Figure 1 . c_{1} c_{2} c_{3} c_{4} c_{5} c_{6} c_{7} c_{8} c_{9} c_{10} Figure 1: An example coloring of a cycle with the set of cut-edges \mathcal{C}={c_{1},c_{2},\dots,c_{10}} . The cycle contains 22 blue and 14 red nodes; hence the less frequent color is red, and \textsc{less}(\mathcal{C})=14 . Global rebalancing. As stated in the introduction, we consider algorithms that use at most 2k cut-edges, for an integer constant k . However, although the initial coloring is 1 -balanced, it may involve more than 2k cut-edges. To address this, we introduce a global rebalancing procedure; its properties are stated in the lemma below and proved in subsection 3.1 . The procedure is executed at the beginning and may also be invoked later during the execution of the algorithm. Lemma 1 (Global rebalancing procedure) . For any valid 1 -balanced set \mathcal{C} of cut-edges, there exists a deterministic procedure that computes a subset \mathcal{C}_{2k}\subseteq\mathcal{C} of size \min\{2k,|\mathcal{C}|\} such that \mathcal{C}_{2k} is (1+1/k) -balanced. For every integer k\geq 1 and \alpha\geq 1+1/k , define the class \mathcal{A}^{k}_{\alpha} of algorithms that (i) are \alpha -augmented, (ii) perform global rebalancing, as specified in 1 , before processing the input sequence, and (iii) during execution, maintain at most 2k cut-edges. Algorithms in \mathcal{A}^{k}_{\alpha} may be either offline or online. Main bounds and paper organization. The main technical contribution of this paper is the following theorem on offline algorithms. Theorem 2 . Fix an integer k\geq 1 and let \alpha\triangleq 3/2+1/k . There exists an offline algorithm \textsc{Off}\in\mathcal{A}^{k}_{\alpha} such that, for every input \sigma , it holds that \textsc{Off}(\sigma)\leq O(k)\cdot\textsc{Opt}(\sigma)+O(n) . The theorem guarantees the existence of an algorithm Off ; the algorithm need not be efficient. section 3 presents its construction and analysis. Next, we show that within the class \mathcal{A}^{k}_{\alpha} , one can construct an online randomized algorithm that is O(k^{2}\cdot\log^{2}n) -competitive against any offline algorithm in the same class . The proof proceeds by formulating the problem as a metrical task system [ BoLiSa92 ] and applying the algorithm of Bubeck et al. [ BuCoLL19 ] . It is given in section 4 . Theorem 3 . Fix an integer k\geq 1 and \alpha\geq 1+1/k . It is possible to construct an online randomized algorithm \textsc{Onl}\in\mathcal{A}^{k}_{\alpha} such that, for a fixed \beta , it holds that \mathbf{E}[\textsc{Onl}(\sigma)]\leq O(k^{2}\cdot\log^{2}n)\cdot\textsc{Off}(\sigma)+\beta , for every offline algorithm \textsc{Off}\in\mathcal{A}^{k}_{\alpha} and every input \sigma . Corollary 4 . For any \varepsilon\in(0,1/2] , there exists a (3/2+\varepsilon) -augmented and O(\varepsilon^{-3}\cdot\log^{2}n) -competitive online randomized algorithm for the online bisection problem on n nodes, where all requests correspond to edges of a cycle connecting all nodes. Proof. Let k\triangleq\lceil 1/\varepsilon\rceil and \alpha\triangleq 3/2+1/k\leq 3/2+\varepsilon . Consider the online randomized algorithm \textsc{Onl}\in\mathcal{A}^{k}_{\alpha} guaranteed by Theorem 3 . Since \textsc{Onl}\in\mathcal{A}^{k}_{\alpha} , it is \alpha -augmented, and thus also (3/2+\varepsilon) -augmented. Fix an input \sigma and the offline algorithm \textsc{Off}\in\mathcal{A}^{k}_{\alpha} provided by Theorem 2 . Let \beta be the parameter from the statement of Theorem 3 . Then, for every input \sigma , \displaystyle\mathbf{E}[\textsc{Onl}(\sigma)] \displaystyle\leq O(k^{2}\cdot\log^{2}n)\cdot\textsc{Off}(\sigma)+\beta (by Theorem 3 ) \displaystyle\leq O(k^{3}\cdot\log^{2}n)\cdot\textsc{Opt}(\sigma)+O(n\cdot k^{2}\cdot\log^{2}n)+\beta (by Theorem 2 ) \displaystyle\leq O(\varepsilon^{-3}\cdot\log^{2}n)\cdot\textsc{Opt}(\sigma)+O(\varepsilon^{-2}\cdot n\cdot\log^{2}n+\beta). This completes the proof of the claimed competitive ratio. ∎ 3 Offline Algorithm In this section, we fix an integer k\geq 1 , set \alpha\triangleq 3/2+1/k , and we construct an offline algorithm \textsc{Off}\in\mathcal{A}^{k}_{\alpha} that generates a solution on the basis of actions of Opt . 4 4 4 Although the algorithm is well defined for any integer k\geq 1 , only values k\geq 3 yield non-trivial augmentation factors. Before processing the input, Off applies 1 to compute a coloring that uses at most 2k edges derived from the initial coloring of Opt . Definition 5 . An offline algorithm Off maintains cut-edge invariants if • \textsc{cut}(\textsc{Off})\subseteq\textsc{cut}(\textsc{Opt}) and • |\textsc{cut}(\textsc{Off})|=\min\{2k,|\textsc{cut}(\textsc{Opt})|\} . Note that the cut-invariants imply that \textsc{cut}(\textsc{Off})=\textsc{cut}(\textsc{Opt}) if \textsc{cut}(\textsc{Opt})\leq 2k . By 1 , the cut-edge invariants hold after the global rebalancing procedure is applied at the beginning. We will also show that Off maintains these invariants throughout execution. As \textsc{cut}(\textsc{Off})\subseteq\textsc{cut}(\textsc{Opt}) , Off never incurs hit cost unless Opt does. Hence, \textsc{Off}_{\textrm{HIT}}(\sigma)\leq\textsc{Opt}_{\textrm{HIT}}(\sigma) for every input \sigma . Therefore, our goal is to construct Off such that \textsc{Off}_{\textrm{REC}}(\sigma)\leq O(k)\cdot\textsc{Opt}_{\textrm{REC}}(\sigma)+O(n) for every input \sigma . Steps. Recall that in response to a single request, Opt may recolor multiple nodes, and after these changes are executed, the coloring of Opt has to be 1 -balanced. In subsection 3.3 , we define the changes that Off performs to mimic a single-node recoloring by Opt . Each such change maintains the cut-edge invariants (cf. 5 ), but does not necessarily preserve color balance. Thus, when Off processes all node recolorings of Opt in response to a single request, it verifies whether its coloring is \alpha -balanced. If this is not the case, Off executes the global rebalancing procedure described in 1 . This procedure produces an \alpha -balanced coloring and preserves the cut-edge invariants. For succinctness, we number the node recolorings performed by Opt and assume that each such recoloring corresponds to a single step , while a single request may correspond to multiple recoloring steps. We use superscript t to indicate that the state (or cost) refers to step t , and omit it when the considered step is clear from the context. 3.1 Global Rebalancing In this section, we prove 1 by presenting a procedure that selects a subset of cut-edges from \textsc{cut}(\textsc{Opt}) guaranteeing the cut-edge invariants (cf. 5 ). Note that this procedure disregards the current set of cut-edges of Off . The construction begins with the cut-edges of Opt and removes them iteratively until the desired number of cut-edges is reached, controlling the color imbalance introduced at each step. Proof of 1 . If |\mathcal{C}|\leq 2k , we simply set \mathcal{C}_{2k}=\mathcal{C} and the claim follows since \textsc{less}(\mathcal{C}_{2k})=n/2 . Therefore, in what follows, we assume that |\mathcal{C}|=2m>2k . We now describe how to iteratively construct the sets \mathcal{C}_{2m},\mathcal{C}_{2m-2},\dots,\mathcal{C}_{2k+2},\mathcal{C}_{2k} . For every j\in\{k,\dots,m\} , we maintain the invariant \textsc{less}(\mathcal{C}_{2j})\geq n/2-n/(2j) . The final set \mathcal{C}_{2k} is then (1+1/k) -balanced as required. We start with \mathcal{C}_{2m}\triangleq\mathcal{C} . Clearly, the invariant holds since \textsc{less}(\mathcal{C}_{2m})=n/2 . It now suffices to describe how to choose \mathcal{C}_{2j-2} based on \mathcal{C}_{2j} (for m\geq j>k ), so that if the invariant holds for \mathcal{C}_{2j} , it also holds for \mathcal{C}_{2j-2} . Let c_{0},c_{1},\dots,c_{2j-1} denote the cut-edges of \mathcal{C}_{2j} in clockwise order, starting from an arbitrary one. These cut-edges are numbered modulo 2j , that is, c_{i+2j} is identified with c_{i} . Fix one of the two colorings induced by \mathcal{C}_{2j} ; without loss of generality, red is more frequent in \mathcal{C}_{2j} . Let A(c_{i},c_{i+1}) be the smallest red arc. Define \mathcal{C}_{2j-2}\triangleq\mathcal{C}_{2j}\setminus\{c_{i},c_{i+1}\} . In other words, \mathcal{C}_{2j-2} is obtained from \mathcal{C}_{2j} by changing the color of arc A(c_{i},c_{i+1}) from red to blue. The resulting number of blue nodes in \mathcal{C}_{2j-2} equals \textsc{less}(\mathcal{C}_{2j})+d(c_{i},c_{i+1}) . We first upper-bound d(c_{i},c_{i+1}) . Since the invariant holds for \mathcal{C}_{2j} , we have \textsc{less}(\mathcal{C}_{2j})\geq n/2-n/(2j) , and therefore the number of red nodes in \mathcal{C}_{2j} is at most n/2+n/(2j) . Because \mathcal{C}_{2j} contains j red arcs and A(c_{i},c_{i+1}) is the smallest among them, we obtain d(c_{i},c_{i+1})\leq n/(2j)+n/(2j^{2}) . If blue remains the less frequent color also in \mathcal{C}_{2j-2} , the invariant follows immediately, since \textsc{less}(\mathcal{C}_{2j-2})=\textsc{less}(\mathcal{C}_{2j})+d(c_{i},c_{i+1})\geq\textsc{less}(\mathcal{C}_{2j})\geq n/2-n/(2j)>n/2-n/(2j-2) . Otherwise, red becomes the less frequent color in \mathcal{C}_{2j-2} . Then \displaystyle\textsc{less}(\mathcal{C}_{2j-2}) \displaystyle=n-\textsc{less}(\mathcal{C}_{2j})-d(c_{i},c_{i+1}) \displaystyle\geq n-n/2-n/(2j)-n/(2j^{2}) (as \textsc{less}(\mathcal{C}_{2j})\leq n/2 ) \displaystyle>n/2-n/(2j-2). In either case, the invariant holds for \mathcal{C}_{2j-2} , and the construction is therefore complete. ∎ 3.2 Distance Between OPT and OFF (Green Sectors) We define \Phi as the “edit distance” between Opt and Off , representing the smallest set of nodes that must switch clusters to transform the partition of Off into that of Opt . To this end, we adapt the notion of an arc: a clockwise arc A^{\circ}(c_{i},c_{j}) includes all nodes between c_{i} and c_{j} in the clockwise order (not necessarily along the shorter path connecting them). The symbol \uplus denotes the disjoint union of sets. Definition 6 . If \textsc{cut}(\textsc{Opt})=\textsc{cut}(\textsc{Off}) , then \Phi=\emptyset . Otherwise, let c_{1},c_{2},\ldots,c_{m} denote the cut-edges from \textsc{cut}(\textsc{Opt})\setminus\textsc{cut}(\textsc{Off}) listed in clockwise order. Define • \Phi_{0}\triangleq A^{\circ}(c_{1},c_{2})\uplus A^{\circ}(c_{3},c_{4})\uplus\ldots\uplus A^{\circ}(c_{m-1},c_{m}) , and • \Phi_{1}\triangleq A^{\circ}(c_{m},c_{1})\uplus A^{\circ}(c_{2},c_{3})\uplus\ldots\uplus A^{\circ}(c_{m-2},c_{m-1}) . Then, \Phi is the smaller of the two sets, with ties broken arbitrarily; cf. subsection 3.2 . \textsc{cut}(\textsc{Opt})={c_{1},c_{2},\dots,c_{12}} \textsc{cut}(\textsc{Off})={c_{1},c_{3},c_{7},c_{12}} \Phi \textsc{cut}(\textsc{Opt})\setminus\textsc{cut}(\textsc{Off}) \Phi \Phi_{0} \Phi_{1} \Phi_{0} \Phi_{1} \Phi=\emptyset e_{1} e_{2} A(e_{1},e_{2}) \Phi t w 8 w \textsc{cut}(\textsc{Off}^{t-1}) \textsc{cut}(\textsc{Opt}^{t-1}) \Phi^{t-1} \Phi t \textsc{cut}(\textsc{Off}^{t-1})\subseteq\textsc{cut}(\textsc{Opt}^{t-1}) c_{i} c_{i}\in\textsc{cut}(\textsc{Off}^{t-1}) w c_{i} c_{i} c_{j} |\textsc{cut}(\textsc{Off}^{t-1})|\leq 2(k-1) w c_{i} c_{j} \textsc{cut}(\textsc{Off}) c_{i} c_{j} c_{i},c_{j}\notin\textsc{cut}(\textsc{Off}^{t-1}) c_{i},c_{j}\in\textsc{cut}(\textsc{Off}^{t-1}) \textsc{cut}(\textsc{Off}^{t-1})=\textsc{cut}(\textsc{Opt}^{t-1}) w c_{i} c_{j} \textsc{cut}(\textsc{Off}) c_{i},c_{j}\in\textsc{cut}(\textsc{Off}^{t-1}) \textsc{cut}(\textsc{Opt}^{t-1})\setminus\textsc{cut}(\textsc{Off}^{t-1})\neq\emptyset w c_{i} c_{j} A(c_{x},c_{y})\in\Phi^{t-1} 6 A(c_{x},c_{y}) 8 c_{x} c_{y} \textsc{cut}(\textsc{Off}) \{c_{i},c_{j}\} c_{i} \textsc{cut}(\textsc{Off}^{t-1}) c_{i}\in\textsc{cut}(\textsc{Opt}^{t-1})\setminus\textsc{cut}(\textsc{Off}^{t-1}) 6 A(c_{i},c_{y})\in\Phi^{t-1} A(c_{j},c_{y}) 8 c_{j} \textsc{cut}(\textsc{Off}) c_{y} \textsc{cut}(\textsc{Opt}^{t}) t w \Phi^{t-1} \Phi^{t} \Phi t \Phi^{t}_{*} \Phi^{t}_{0} \Phi^{t-1}=\Phi^{t-1}_{0} \Phi^{t}_{1} \Phi^{t}_{*} \Phi^{t-1} \Phi_{0} \Phi_{1} |\Phi^{t}|\leq|\Phi^{t}_{*}| \phi\triangleq|\Phi| \Delta^{t}\phi=\phi^{t}-\phi^{t-1} \Delta^{t}_{*}\phi=\phi^{t}_{*}-\phi^{t-1} \textsc{Off}^{t}_{\textrm{REC}}+\Delta^{t}_{*}\phi\leq 1 \phi^{t}\leq\phi^{t}_{*} \textsc{Off}^{t}_{\textrm{REC}}+\Delta^{t}\phi\leq\textsc{Off}^{t}_{\textrm{REC}}+\Delta^{t}_{*}\phi\leq 1=\textsc{Opt}^{t}_{\textrm{REC}} \oplus \textsc{Off}^{t}_{\textrm{REC}}+\Delta^{t}_{*}\phi\leq 1 c_{i} c_{i}\in\textsc{cut}(\textsc{Off}^{t-1}) w 1 Figure 6 3.2 \Phi \Delta^{t}_{*}\phi=0 c_{i}\notin\textsc{cut}(\textsc{Off}^{t-1}) 0 Figure 6 \Phi^{t}_{*}=\Phi^{t-1}\oplus\{w\} \Delta^{t}_{*}\phi=\pm 1 {subfigure} 1 2 3 4 5 6 7 8 9 i {subfigure} 1 2 3 i {subfigure} 1 2 i 4 5 6 7 8 9 10 \Phi i c_{i} w \textsc{cut}(\textsc{Off}^{t-1}) \Phi^{t-1} \textsc{Off}^{t}_{\textrm{REC}}+\Delta^{t}_{*}\phi\leq 1 \textsc{cut}(\textsc{Off}^{t-1}) |\textsc{cut}(\textsc{Off}^{t-1})|=2k Figure 10 3.2 \Phi^{t}_{*}=\Phi^{t-1}\oplus\{w\} \Delta^{t}_{*}\phi=\pm 1 |\textsc{cut}(\textsc{Off}^{t-1})|\leq 2(k-1) w 1 Figure 10 \Phi \Delta^{t}_{*}\phi=0 {subfigure} 1 2 3 4 5 6 7 8 9 10 {subfigure} 1 2 3 4 5 6 7 8 9 10 11 12 {subfigure} 1 2 3 4 \Phi Figure 6 \textsc{Off}^{t}_{\textrm{REC}}+\Delta^{t}_{*}\phi\leq 1 c_{i},c_{j} c_{i},c_{j}\notin\textsc{cut}(\textsc{Off}^{t-1}) Figure 15 \Phi^{t}_{*}=\Phi^{t-1}\oplus\{w\} \Delta^{t}_{*}\phi=\pm 1 c_{i},c_{j}\in\textsc{cut}(\textsc{Off}^{t-1}) \textsc{cut}(\textsc{Off}^{t-1})=\textsc{cut}(\textsc{Opt}^{t-1}) w 1 \Phi \Delta^{t}_{*}\phi=0 c_{i},c_{j}\in\textsc{cut}(\textsc{Off}^{t-1}) \textsc{cut}(\textsc{Opt}^{t-1})\setminus\textsc{cut}(\textsc{Off}^{t-1})\neq\emptyset A(c_{x},c_{y})\in\Phi^{t-1} Figure 15 w A(c_{x},c_{y}) w 1 \Phi A(c_{x},c_{y}) d(c_{x},c_{y}) \Phi^{t}_{*}=\Phi^{t-1}\oplus A(c_{x},c_{y}) A(c_{x},c_{y})\subseteq\Phi^{t-1} \Phi^{t}_{*}=\Phi^{t-1}\setminus A(c_{x},c_{y}) \textsc{Off}^{t}_{\textrm{REC}}=1+d(c_{x},c_{y}) \Delta\phi=-d(c_{x},c_{y}) c_{i}\notin\textsc{cut}(\textsc{Off}^{t-1}) c_{j}\in\textsc{cut}(\textsc{Off}^{t-1}) 6 A(c_{i},c_{y})\subseteq\Phi^{t-1} Figure 15 3.2 A(c_{j},c_{y}) A(c_{j},c_{y})=A(c_{i},c_{y})\oplus\{w\} d(c_{i},c_{y})+1 \Phi^{t}_{*}=\Phi^{t-1}\oplus A(c_{j},c_{y})\oplus\{w\}=\Phi^{t-1}\oplus A(c_{i},c_{y}) A(c_{i},c_{y})\subseteq\Phi^{t-1} \Phi^{t}_{*}=\Phi^{t-1}\setminus A(c_{i},c_{y}) \Delta^{t}_{*}\phi=-d(c_{i},c_{y}) {subfigure} 1 2 3 4 5 6 i j 9 10 {subfigure} 1 2 x 4 y 6 7 i j 10 * {subfigure} i j 3 4 5 6 7 8 9 10 y 12 * {subfigure} j i 3 4 5 6 7 8 9 10 y 12 * \Phi Figure 6 9 10 11 \Delta^{t}\phi\leq\Delta^{t}_{*}\phi \textsc{Opt}^{t}_{\textrm{REC}}=1 t \textsc{Off}^{t}_{\textrm{REC}}+\Delta^{t}\phi\leq\textsc{Opt}^{t}_{\textrm{REC}} 1 (1+1/k) \alpha \alpha=3/2+1/k \alpha \textsc{Off}\in\mathcal{A}^{k}_{\alpha} 1 \textsc{less}(\textsc{cut}(\textsc{Off}))+\phi\geq n/2 z_{\mathrm{RR}} z_{\mathrm{RB}} z_{\mathrm{BR}} z_{\mathrm{BB}} \phi \textsc{less}(\textsc{cut}(\textsc{Off})) \displaystyle\textsc{less}(\textsc{cut}(\textsc{Off}))+\phi \displaystyle=\min\{z_{\mathrm{RR}}+z_{\mathrm{BR}},z_{\mathrm{BB}}+z_{\mathrm{RB}}\}+\min\{z_{\mathrm{RB}}+z_{\mathrm{BR}},z_{\mathrm{RR}}+z_{\mathrm{BB}}\}, \displaystyle\geq\min\{z_{\mathrm{RB}}+z_{\mathrm{RR}},z_{\mathrm{BR}}+z_{\mathrm{BB}}\} \displaystyle=\min\{n/2,n/2\}=n/2, 1 \sigma p \textsc{Off}_{\textrm{REC}}(p) p \Delta_{p}\phi \phi p p \textsc{Off}_{\textrm{REC}}(p)+\Delta_{p}\phi\geq n/(2k) \mathcal{C}_{b} \mathcal{C}_{e} p \displaystyle\textsc{less}(\mathcal{C}_{e}) \displaystyle