Total Dual Integrality in Some Facility Location Problems

Abstract

Facility location, arising in a rich variety of applications, has been studied extensively in the fields of operations research and computer science. In this paper we consider the classical uncapacitated facility location problem and its “prize-collecting' variant introduced by Baïou and Barahona, and we show that the linear systems associated with these problems are totally dual integral if and only if the input graphs do not contain a certain type of odd cycles. As corollaries, we get structural characterizations of two min-max relations on facility location. Our results strengthen the integrality theorems on facility location polytopes proved by Baïou and Barahona; our proofs lead to combinatorial polynomial-time algorithms for the facility location problems that we consider.