  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.
