2019/11/22 by Kristóf Bérczi, André Berger, Bérczi, Kristóf +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1911.09890
17 pages
openalex publication_date 2019/11/22 · arxiv created 2019/12/14 · arxiv updated 2019/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(ε) and g(ε) for each hyperedge ε. The objective is to find a minimum-cost basis B such that f(ε) ≤ |B ∩ ε| ≤ g(ε) for each hyperedge ε. 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 Δ-1, where Δ 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 Δ-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 ε has element multiplicities mε. 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.