Constant-Factor Approximation Algorithms for Parity-Constrained Facility Location Problems

Hyung-Chan An; Kangsan Kim; Yongho Shin

arxiv: 1907.03129 · v1 · pith:XQR6S46Xnew · submitted 2019-07-06 · 💻 cs.DS

Constant-Factor Approximation Algorithms for Parity-Constrained Facility Location Problems

Kangsan Kim , Yongho Shin , Hyung-Chan An This is my paper

Pith reviewed 2026-05-25 01:43 UTC · model grok-4.3

classification 💻 cs.DS

keywords facility locationapproximation algorithmsparity constraintsT-joink-centermetric spacescombinatorial optimization

0 comments

The pith

Parity constraints on client assignments can be satisfied with only constant-factor increase in cost for facility location problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows how to approximate the facility location problem when each facility has a required parity for the number of clients it serves. The unconstrained version of the problem can be solved to a constant factor but may violate the parities. The authors correct these violations by constructing an auxiliary graph and finding a low-cost T-join that adjusts the assignments. This yields the first constant-factor approximation for the constrained version, and a similar result for the k-center problem. A reader would care because parity is a basic combinatorial constraint that arises in many settings, and facility location is a core problem in network design and operations research.

Core claim

We present the first constant-factor approximation algorithm for the facility location problem with parity constraints. Although the unconstrained facility location problem as a relaxation has unbounded gap, its structured solution's parity violation can be corrected at small cost by a T-join on an auxiliary graph that does not satisfy the triangle inequality, achieved through shortcutting operations and a combinatorial multi-step construction of an upper bound. We also give the first constant-factor approximation for the parity-constrained k-center problem.

What carries the argument

A T-join on an auxiliary graph constructed from the unconstrained solution, with shortcutting operations to produce a cheap and sparse solution despite the graph lacking the triangle inequality.

If this is right

The parity-constrained facility location problem admits a constant-factor approximation algorithm.
The parity-constrained k-center problem admits a constant-factor approximation algorithm.
Parity violations can be corrected without increasing the total cost by more than a constant factor of the optimum.
The correction technique works on auxiliary graphs that do not satisfy the triangle inequality.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The T-join correction approach may extend to other modular or parity-type constraints in clustering and location problems.
This suggests that adding parity requirements does not change the constant-factor approximability status of these metric problems.

Load-bearing premise

The assumption that parity violations present in an optimal unconstrained facility-location solution can always be corrected at small additional cost by a cheap sparse T-join on an auxiliary graph via shortcutting and multi-step upper bound construction.

What would settle it

A concrete instance of the parity-constrained facility location problem in which every feasible solution has cost more than a fixed constant times the cost of the best unconstrained solution, or in which no bounded-cost T-join correction exists for the auxiliary graph.

Figures

Figures reproduced from arXiv: 1907.03129 by Hyung-Chan An, Kangsan Kim, Yongho Shin.

**Figure 1.** Figure 1: (A): An initial solution (SI, σI) and an optimal solution (SO, σO). A facility (and a client) is represented as a square (and a circle, respectively). Odd-constrained facilities have red dashed borders; even-constrained ones have navy-blue solid borders. The upper-right triangle is filled with black if the facility is open in the initial solution; the lower-left triangle is filled with gray if it is open i… view at source ↗

read the original abstract

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather disturbing when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement--odd, even, or unconstrained--of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse T-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also present the first constant-factor approximation algorithm for the parity-constrained k-center problem, the bottleneck optimization variant.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives the first constant-factor approximations for parity-constrained facility location and its k-center variant by correcting an unconstrained solution with a T-join on a non-metric auxiliary graph.

read the letter

The headline result is the first constant-factor approximation for facility location where each open facility must serve an odd or even number of clients as specified, plus the same guarantee for the parity-constrained k-center problem. Prior work left these open, and the unconstrained version has unbounded gap, so the contribution rests on showing the violations can be fixed cheaply. They construct an auxiliary graph, find a T-join to prescribe the fixes, apply shortcutting to make it sparse, and then use a combinatorial multi-step construction to bound the added cost. That construction is the new technical step not in the standard unconstrained literature. The outline is straightforward and reuses known T-join algorithms, which is a plus. Extending the same idea to k-center is a clean extra. The citation pattern is normal for the area and does not rely on self-referential constants. The soft spot is the load-bearing bound on the T-join cost. The auxiliary graph violates the triangle inequality, so the multi-step upper bound must stay a fixed constant times OPT rather than growing with n or the number of violations. If that step only produces a looser guarantee, the overall ratio is not constant. The abstract asserts it works, but the details of the construction determine whether the claim holds. This paper is for people working on approximation algorithms for facility-location variants and constrained combinatorial problems. A reader already familiar with T-joins and metric embeddings would get the most out of the technique. It deserves a serious referee to verify the bounding argument in full.

Referee Report

1 major / 1 minor

Summary. The paper claims the first constant-factor approximation algorithms for the facility location problem with parity constraints (odd/even/unconstrained) on the number of clients assigned to each open facility, and for the parity-constrained k-center problem. It proceeds by solving the unconstrained facility location instance (which has unbounded gap to the constrained optimum) and correcting the resulting parity violations via a T-join on an auxiliary graph; shortcutting is used to obtain a sparse T-join, whose cost is then bounded via a combinatorial multi-step construction. The same approach is applied to the k-center variant.

Significance. If the T-join correction cost is provably bounded by a constant times OPT, the result would be significant: it would resolve the open question of constant-factor approximability for these parity-constrained variants, which are natural extensions of well-studied problems but previously lacked such guarantees. The approach leverages standard metric facility location and T-join algorithms while addressing the non-metric auxiliary graph via the multi-step bound.

major comments (1)

Abstract (and the section presenting the T-join construction): the central claim that shortcutting plus the combinatorial multi-step construction yields a cheap sparse T-join whose cost is O(OPT) (independent of n and the number of parity violations) is load-bearing for the constant-factor guarantee, because the unconstrained solution already has unbounded gap. The analysis must explicitly derive a constant-factor upper bound on this auxiliary-graph T-join despite the explicit violation of the triangle inequality; without a concrete constant or a proof that the bound does not grow with the number of violations, the overall approximation ratio is not shown to be constant.

minor comments (1)

The abstract and introduction should clarify the precise approximation ratios obtained (e.g., whether they match the best known unconstrained ratios up to a fixed multiplicative constant).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for recognizing the significance of resolving the constant-factor approximability of these parity-constrained problems. We address the single major comment below.

read point-by-point responses

Referee: [—] Abstract (and the section presenting the T-join construction): the central claim that shortcutting plus the combinatorial multi-step construction yields a cheap sparse T-join whose cost is O(OPT) (independent of n and the number of parity violations) is load-bearing for the constant-factor guarantee, because the unconstrained solution already has unbounded gap. The analysis must explicitly derive a constant-factor upper bound on this auxiliary-graph T-join despite the explicit violation of the triangle inequality; without a concrete constant or a proof that the bound does not grow with the number of violations, the overall approximation ratio is not shown to be constant.

Authors: The manuscript already derives the required bound in the T-join section via the combinatorial multi-step construction after shortcutting. The construction iteratively matches parity-violating clients using paths whose lengths are charged directly to the cost of the unconstrained solution (itself a constant-factor approximation to the true OPT), ensuring the total correction cost is at most a fixed multiple of OPT independent of n and the number of violations. The multi-step process uses a charging scheme that pairs violations without accumulation. We agree the presentation of this independence and the explicit constant could be stated more prominently to avoid any ambiguity, and we will revise the section for greater clarity on these points. revision: partial

Circularity Check

0 steps flagged

No circularity: derivation uses standard FL relaxation plus independent combinatorial T-join bound

full rationale

The paper begins with the known unconstrained facility location solution (unbounded gap acknowledged) and corrects parity violations via a T-join on an auxiliary graph. The correction cost is bounded by shortcutting followed by an explicit multi-step combinatorial construction of an upper bound, without any fitted parameters, self-definitional equations, or load-bearing self-citations that reduce the claimed constant factor to the paper's own inputs. The central approximation guarantee rests on this external combinatorial argument rather than any renaming or ansatz smuggled from prior author work. No step exhibits the required reduction by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on the existence and efficient computability of T-joins in undirected graphs and on the ability to shortcut paths in a non-metric graph while preserving cost bounds; no free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Input distances form a metric (satisfy triangle inequality)
Standard assumption stated for the facility-location input; used to justify shortcutting.
standard math A minimum-cost T-join can be found in polynomial time
Invoked when the algorithm constructs the correction step on the auxiliary graph.

pith-pipeline@v0.9.0 · 5833 in / 1369 out tokens · 31820 ms · 2026-05-25T01:43:10.684555+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

[1]

Ahamad and M

M. Ahamad and M. H. Ammar. Performance characterization of quorum-consensus algorithms for replicated data. IEEE Transactions on Software Engineering, 15(4):492–496, 1989

work page 1989
[2]

Ahmadian, Z

S. Ahmadian, Z. Friggstad, and C. Swamy. Local-search based approximation algorithms for mobile facility location problems. In ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1607– 1621, 2013

work page 2013
[3]

H.-C. An, A. Bhaskara, C. Chekuri, S. Gupta, V . Madan, and O. Svensson. Centrality of trees for capacitatedk-center. Mathematical Programming, 154(1):29–53, 2015

work page 2015
[4]

H.-C. An, M. Singh, and O. Svensson. LP-based algorithms for capacitated facility location. SIAM Journal on Computing, 46(1):272–306, 2017

work page 2017
[5]

M. L. Balinski. On ﬁnding integer solutions to linear programs. Technical report, Mathematica Prince- ton NJ, 1964

work page 1964
[6]

Bansal, N

M. Bansal, N. Garg, and N. Gupta. A 5-approximation for capacitated facility location. In European Symposium on Algorithms (ESA), pages 133–144, 2012

work page 2012
[7]

A. A. Bencz ´ur and O. F ¨ul¨op. Fast algorithms for even/odd minimum cuts and generalizations. In European Symposium on Algorithms (ESA), pages 88–99, 2000

work page 2000
[8]

J. Byrka. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- niques, pages 29–43. 2007. 12

work page 2007
[9]

T.-H. H. Chan, A. Guerqin, and M. Sozio. Fully dynamic k-center clustering. In World Wide Web Conference (WWW), pages 579–587, 2018

work page 2018
[10]

Cheriyan, Z

J. Cheriyan, Z. Friggstad, and Z. Gao. Approximating minimum-cost connectedT -joins. Algorithmica, 72(1):126–147, 2015

work page 2015
[11]

Cygan, A

M. Cygan, A. Czumaj, M. Mucha, and P. Sankowski. Online facility location with deletions. In European Symposium on Algorithms (ESA), pages 21:1–21:15, 2018

work page 2018
[12]

Cygan, M

M. Cygan, M. Hajiaghayi, and S. Khuller. LP rounding fork-centers with non-uniform hard capacities. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 273–282, 2012

work page 2012
[13]

E. D. Demaine, F. V . Fomin, M. Hajiaghayi, and D. M. Thilikos. Fixed-parameter algorithms for (k,r )-center in planar graphs and map graphs. ACM Transactions on Algorithms, 1(1):33–47, 2005

work page 2005
[14]

Edmonds and E

J. Edmonds and E. Johnson. Matching, Euler tours and the Chinese postman. Mathematical Program- ming, 5:88–124, 1973

work page 1973
[15]

Eisenstat, P

D. Eisenstat, P. N. Klein, and C. Mathieu. Approximating k-center in planar graphs. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 617–627, 2014

work page 2014
[16]

Eisenstat, C

D. Eisenstat, C. Mathieu, and N. Schabanel. Facility location in evolving metrics. In Automata, Languages, and Programming, pages 459–470, 2014

work page 2014
[17]

A. Ene, S. Har-Peled, and B. Raichel. Fast clustering with lower bounds: No customer too far, no shop too small. Computing Research Repository (CoRR), 2013

work page 2013
[18]

Everett, C

H. Everett, C. M. De Figueiredo, C. Linhares-Sales, F. Maffray, O. Porto, and B. A. Reed. Path parity and perfection. Discrete Mathematics, 165:233–252, 1997

work page 1997
[19]

Frank and L

F. Frank and L. R. Anderson. Effects of task and group size upon group productivity and member satisfaction. Sociometry, 34(1):135–149, 1971

work page 1971
[20]

Goranci, M

G. Goranci, M. Henzinger, and D. Leniowski. A tree structure for dynamic facility location. In European Symposium on Algorithms (ESA), pages 39:1–39:13, 2018

work page 2018
[21]

Gr ¨otschel, L

M. Gr ¨otschel, L. Lov´asz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169–197, 1981

work page 1981
[22]

the ellipsoid method and its consequences in combinatorial optimization

M. Gr ¨otschel, L. Lov ´asz, and A. Schrijver. Corrigendum to our paper “the ellipsoid method and its consequences in combinatorial optimization”. Combinatorica, 4(4):291–295, 1984

work page 1984
[23]

Gr ¨otschel and W

M. Gr ¨otschel and W. R. Pulleyblank. Weakly bipartite graphs and the max-cut problem. Operations Research Letters, 1(1):23–27, 1981

work page 1981
[24]

D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180–184, 1985

work page 1985
[25]

K. Jain, M. Mahdian, and A. Saberi. A new greedy approach for facility location problems. In ACM Symposium on Theory of Computing (STOC), pages 731–740, 2002. 13

work page 2002
[26]

Jain and V

K. Jain and V . V . Vazirani. Approximation algorithms for metric facility location andk-median prob- lems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 48(2):274–296, 2001

work page 2001
[27]

Kakimura, K.-i

N. Kakimura, K.-i. Kawarabayashi, and Y . Kobayashi. Erd˝os-P´osa property and its algorithmic appli- cations — parity constraints, subset feedback set, and subset packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1726–1736, 2012

work page 2012
[28]

Kaminski and N

M. Kaminski and N. Nishimura. Finding an induced path of given parity in planar graphs in polynomial time. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 656–670, 2012

work page 2012
[29]

Khuller and Y

S. Khuller and Y . Sussmann. The capacitatedk-center problem. SIAM Journal on Discrete Mathemat- ics, 13(3):403–418, 2000

work page 2000
[30]

M. R. Korupolu, C. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37(1):146–188, 2000

work page 2000
[31]

A. A. Kuehn and M. J. Hamburger. A heuristic program for locating warehouses.Management Science, 9(4):643–666, 1963

work page 1963
[32]

Lammersen and C

C. Lammersen and C. Sohler. Facility location in dynamic geometric data streams. In European Symposium on Algorithms (ESA), pages 660–671, 2008

work page 2008
[33]

H. Lang. Online facility location against at-bounded adversary. InACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1002–1014, 2018

work page 2018
[34]

S. Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. In Automata, Languages and Programming, pages 77–88, 2011

work page 2011
[35]

S. Li. On facility location with general lower bounds. In ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pages 2279–2290, 2019

work page 2019
[36]

A. S. Manne. Plant location under economies-of-scale—decentralization and computation. Manage- ment Science, 11(2):213–235, 1964

work page 1964
[37]

Marx and M

D. Marx and M. Pilipczuk. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In European Symposium on Algorithms (ESA), pages 865–877, 2015

work page 2015
[38]

Menon and K

T. Menon and K. W. Phillips. Getting even or being at odds? Cohesion in even-and odd-sized small groups. Organization Science, 22(3):738–753, 2011

work page 2011
[39]

M. W. Padberg and M. R. Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 7(1):67–80, 1982

work page 1982
[40]

M. Pal, T. Tardos, and T. Wexler. Facility location with nonuniform hard capacities. In IEEE Sympo- sium on Foundations of Computer Science (FOCS), pages 329–338, 2001

work page 2001
[41]

Schrijver

A. Schrijver. Combinatorial optimization: polyhedra and efﬁciency . Springer Science & Business Media, 2003

work page 2003
[42]

Schrijver and P

A. Schrijver and P. Seymour. Packing odd paths. Journal of Combinatorial Theory, 62:280–288, 1994. 14

work page 1994
[43]

A. Seb ˝o. Eight-ﬁfth approximation for the path TSP. In Integer Programming and Combinatorial Optimization (IPCO), pages 362–374, 2013

work page 2013
[44]

D. B. Shmoys and K. Aardal. Approximation algorithms for facility location problems. Utrecht Uni- versity: Information and Computing Sciences, 1997

work page 1997
[45]

J. F. Stollsteimer. A working model for plant numbers and locations. Journal of Farm Economics , 45(3):631–645, 1963

work page 1963
[46]

admissible

The Apache Software Foundation. Apache ZooKeeper. http://zookeeper.apache.org/. A Analysis for the All-Even Case We present the full analysis of our algorithm described in Section 3. We assume that|D| is even; otherwise, the instance is infeasible. It is easy to see that our algorithm returns a feasible solution since every facility is assigned exactly tw...

work page

[1] [1]

Ahamad and M

M. Ahamad and M. H. Ammar. Performance characterization of quorum-consensus algorithms for replicated data. IEEE Transactions on Software Engineering, 15(4):492–496, 1989

work page 1989

[2] [2]

Ahmadian, Z

S. Ahmadian, Z. Friggstad, and C. Swamy. Local-search based approximation algorithms for mobile facility location problems. In ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1607– 1621, 2013

work page 2013

[3] [3]

H.-C. An, A. Bhaskara, C. Chekuri, S. Gupta, V . Madan, and O. Svensson. Centrality of trees for capacitatedk-center. Mathematical Programming, 154(1):29–53, 2015

work page 2015

[4] [4]

H.-C. An, M. Singh, and O. Svensson. LP-based algorithms for capacitated facility location. SIAM Journal on Computing, 46(1):272–306, 2017

work page 2017

[5] [5]

M. L. Balinski. On ﬁnding integer solutions to linear programs. Technical report, Mathematica Prince- ton NJ, 1964

work page 1964

[6] [6]

Bansal, N

M. Bansal, N. Garg, and N. Gupta. A 5-approximation for capacitated facility location. In European Symposium on Algorithms (ESA), pages 133–144, 2012

work page 2012

[7] [7]

A. A. Bencz ´ur and O. F ¨ul¨op. Fast algorithms for even/odd minimum cuts and generalizations. In European Symposium on Algorithms (ESA), pages 88–99, 2000

work page 2000

[8] [8]

J. Byrka. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- niques, pages 29–43. 2007. 12

work page 2007

[9] [9]

T.-H. H. Chan, A. Guerqin, and M. Sozio. Fully dynamic k-center clustering. In World Wide Web Conference (WWW), pages 579–587, 2018

work page 2018

[10] [10]

Cheriyan, Z

J. Cheriyan, Z. Friggstad, and Z. Gao. Approximating minimum-cost connectedT -joins. Algorithmica, 72(1):126–147, 2015

work page 2015

[11] [11]

Cygan, A

M. Cygan, A. Czumaj, M. Mucha, and P. Sankowski. Online facility location with deletions. In European Symposium on Algorithms (ESA), pages 21:1–21:15, 2018

work page 2018

[12] [12]

Cygan, M

M. Cygan, M. Hajiaghayi, and S. Khuller. LP rounding fork-centers with non-uniform hard capacities. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 273–282, 2012

work page 2012

[13] [13]

E. D. Demaine, F. V . Fomin, M. Hajiaghayi, and D. M. Thilikos. Fixed-parameter algorithms for (k,r )-center in planar graphs and map graphs. ACM Transactions on Algorithms, 1(1):33–47, 2005

work page 2005

[14] [14]

Edmonds and E

J. Edmonds and E. Johnson. Matching, Euler tours and the Chinese postman. Mathematical Program- ming, 5:88–124, 1973

work page 1973

[15] [15]

Eisenstat, P

D. Eisenstat, P. N. Klein, and C. Mathieu. Approximating k-center in planar graphs. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 617–627, 2014

work page 2014

[16] [16]

Eisenstat, C

D. Eisenstat, C. Mathieu, and N. Schabanel. Facility location in evolving metrics. In Automata, Languages, and Programming, pages 459–470, 2014

work page 2014

[17] [17]

A. Ene, S. Har-Peled, and B. Raichel. Fast clustering with lower bounds: No customer too far, no shop too small. Computing Research Repository (CoRR), 2013

work page 2013

[18] [18]

Everett, C

H. Everett, C. M. De Figueiredo, C. Linhares-Sales, F. Maffray, O. Porto, and B. A. Reed. Path parity and perfection. Discrete Mathematics, 165:233–252, 1997

work page 1997

[19] [19]

Frank and L

F. Frank and L. R. Anderson. Effects of task and group size upon group productivity and member satisfaction. Sociometry, 34(1):135–149, 1971

work page 1971

[20] [20]

Goranci, M

G. Goranci, M. Henzinger, and D. Leniowski. A tree structure for dynamic facility location. In European Symposium on Algorithms (ESA), pages 39:1–39:13, 2018

work page 2018

[21] [21]

Gr ¨otschel, L

M. Gr ¨otschel, L. Lov´asz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169–197, 1981

work page 1981

[22] [22]

the ellipsoid method and its consequences in combinatorial optimization

M. Gr ¨otschel, L. Lov ´asz, and A. Schrijver. Corrigendum to our paper “the ellipsoid method and its consequences in combinatorial optimization”. Combinatorica, 4(4):291–295, 1984

work page 1984

[23] [23]

Gr ¨otschel and W

M. Gr ¨otschel and W. R. Pulleyblank. Weakly bipartite graphs and the max-cut problem. Operations Research Letters, 1(1):23–27, 1981

work page 1981

[24] [24]

D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180–184, 1985

work page 1985

[25] [25]

K. Jain, M. Mahdian, and A. Saberi. A new greedy approach for facility location problems. In ACM Symposium on Theory of Computing (STOC), pages 731–740, 2002. 13

work page 2002

[26] [26]

Jain and V

K. Jain and V . V . Vazirani. Approximation algorithms for metric facility location andk-median prob- lems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 48(2):274–296, 2001

work page 2001

[27] [27]

Kakimura, K.-i

N. Kakimura, K.-i. Kawarabayashi, and Y . Kobayashi. Erd˝os-P´osa property and its algorithmic appli- cations — parity constraints, subset feedback set, and subset packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1726–1736, 2012

work page 2012

[28] [28]

Kaminski and N

M. Kaminski and N. Nishimura. Finding an induced path of given parity in planar graphs in polynomial time. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 656–670, 2012

work page 2012

[29] [29]

Khuller and Y

S. Khuller and Y . Sussmann. The capacitatedk-center problem. SIAM Journal on Discrete Mathemat- ics, 13(3):403–418, 2000

work page 2000

[30] [30]

M. R. Korupolu, C. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37(1):146–188, 2000

work page 2000

[31] [31]

A. A. Kuehn and M. J. Hamburger. A heuristic program for locating warehouses.Management Science, 9(4):643–666, 1963

work page 1963

[32] [32]

Lammersen and C

C. Lammersen and C. Sohler. Facility location in dynamic geometric data streams. In European Symposium on Algorithms (ESA), pages 660–671, 2008

work page 2008

[33] [33]

H. Lang. Online facility location against at-bounded adversary. InACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1002–1014, 2018

work page 2018

[34] [34]

S. Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. In Automata, Languages and Programming, pages 77–88, 2011

work page 2011

[35] [35]

S. Li. On facility location with general lower bounds. In ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pages 2279–2290, 2019

work page 2019

[36] [36]

A. S. Manne. Plant location under economies-of-scale—decentralization and computation. Manage- ment Science, 11(2):213–235, 1964

work page 1964

[37] [37]

Marx and M

D. Marx and M. Pilipczuk. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In European Symposium on Algorithms (ESA), pages 865–877, 2015

work page 2015

[38] [38]

Menon and K

T. Menon and K. W. Phillips. Getting even or being at odds? Cohesion in even-and odd-sized small groups. Organization Science, 22(3):738–753, 2011

work page 2011

[39] [39]

M. W. Padberg and M. R. Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 7(1):67–80, 1982

work page 1982

[40] [40]

M. Pal, T. Tardos, and T. Wexler. Facility location with nonuniform hard capacities. In IEEE Sympo- sium on Foundations of Computer Science (FOCS), pages 329–338, 2001

work page 2001

[41] [41]

Schrijver

A. Schrijver. Combinatorial optimization: polyhedra and efﬁciency . Springer Science & Business Media, 2003

work page 2003

[42] [42]

Schrijver and P

A. Schrijver and P. Seymour. Packing odd paths. Journal of Combinatorial Theory, 62:280–288, 1994. 14

work page 1994

[43] [43]

A. Seb ˝o. Eight-ﬁfth approximation for the path TSP. In Integer Programming and Combinatorial Optimization (IPCO), pages 362–374, 2013

work page 2013

[44] [44]

D. B. Shmoys and K. Aardal. Approximation algorithms for facility location problems. Utrecht Uni- versity: Information and Computing Sciences, 1997

work page 1997

[45] [45]

J. F. Stollsteimer. A working model for plant numbers and locations. Journal of Farm Economics , 45(3):631–645, 1963

work page 1963

[46] [46]

admissible

The Apache Software Foundation. Apache ZooKeeper. http://zookeeper.apache.org/. A Analysis for the All-Even Case We present the full analysis of our algorithm described in Section 3. We assume that|D| is even; otherwise, the instance is infeasible. It is easy to see that our algorithm returns a feasible solution since every facility is assigned exactly tw...

work page