Degree-Bounded Generalized Polymatroids and Approximating the Metric Many-Visits TSP

Abstract

In the Bounded Degree Matroid Basis Problem, we are given a matroid and a hypergraph on the same ground set, together with costs for the elements of that set as well as lower and upper bounds $f(\epsilon )$ and $g(\epsilon )$ for each hyperedge $\epsilon$. The objective is to find a minimum-cost basis $B$ such that $f(\epsilon )\le |B\cap \epsilon |\le g(\epsilon )$ for each hyperedge $\epsilon$. Király et al. (Combinatorica, 2012) provided an algorithm that finds a basis of cost at most the optimum value which violates the lower and upper bounds by at most $2\Delta -1$, where $\Delta$ is the maximum degree of the hypergraph. When only lower or only upper bounds are present for each hyperedge, this additive error is decreased to $\Delta -1$. We consider an extension of the matroid basis problem to generalized polymatroids, or g-polymatroids, and additionally allow element multiplicities. The Bounded Degree g-polymatroid Element Problem with Multiplicities takes as input a g-polymatroid $Q(p,b)$ instead of a matroid, and besides the lower and upper bounds, each hyperedge $\epsilon$ has element multiplicities $m_{\epsilon }$. Building on the approach of Király et al., we provide an algorithm for finding a solution of cost at most the optimum value, having the same additive approximation guarantee. As an application, we develop a $1.5$-approximation for the metric Many-Visits TSP, where the goal is to find a minimum-cost tour that visits each city $v$ a positive $r(v)$ number of times. Our approach combines our algorithm for the Bounded Degree g-polymatroid Element Problem with Multiplicities with the principle of Christofides' algorithm from 1976 for the (single-visit) metric TSP, whose approximation guarantee it matches.

17 pages