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 discouraging when we consider the central role of parity in the field of combinatorics.
In this paper, we present the first constantfactor 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 parityconstrained 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 Tjoin on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse Tjoin. Finally, we bound the correction cost by exhibiting a combinatorial multistep construction of an upper bound.
BibTeX  Entry
@InProceedings{kim_et_al:LIPIcs:2020:13365,
author = {Kangsan Kim and Yongho Shin and HyungChan An},
title = {{ConstantFactor Approximation Algorithms for the ParityConstrained Facility Location Problem}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {21:121:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13365},
URN = {urn:nbn:de:0030drops133652},
doi = {10.4230/LIPIcs.ISAAC.2020.21},
annote = {Keywords: Facility location problems, approximation algorithms, clustering problems, parity constraints}
}
Keywords: 

Facility location problems, approximation algorithms, clustering problems, parity constraints 
Collection: 

31st International Symposium on Algorithms and Computation (ISAAC 2020) 
Issue Date: 

2020 
Date of publication: 

04.12.2020 