Polyhedral properties of the \(K\)-median problem on a tree (Q879965)

This paper investigates the polyhedral structure of the \(K\)-median problem on trees. Despite the problem being solvable in polynomial time, no exact LP formulation is known. The authors give an IP formulation and show that for every tree with at least 4 vertices there is a dataset such that the polytope \(Q_K\) of the LP relaxation of this formulation is not integral for all \(K \geq 2\). They investigate the structure of \(Q_K\) and show that \(x^{\text{LP}}=z^*\) if \(T\) is a path or a 1-star and that these are the only trees with this property. Furthermore, for general graphs, \(Q_K\) is shown to be integral if and only if \(K\in \{1,n-1, n\}\). The authors also show that \(z^*/z^{LP} < 2-2/(K+1)\) and that this bound is asymptotically tight. Next, they give a new proof that an alternative formulation for \(K=2\) is integral. This is followed by the identification of a class of constraints that they demonstrate to result in integer polytopes for all \(K\) if \(T\) is a 1-star. Finally, a class of facets for general graphs and \(K\geq 2\) is established. This class is then used to prove integrality of a new description of the problem for 2-stars.