Degree-Bounded Polymatroids, with Applications to the Many-Visits TSP

Matthias Mnich - COLLOQUIUM LECTURE

Tuesday, 03.12.2019, 14:30

Room 337 Taub Bld.

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(e) and g(e) for each hyperedge e. The objective is to find a minimum-cost
basis B such that f(e) <= |B \cap e| <= g(e) for each hyperedge e. Kiraly, Lau and Singh
(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.
We consider an extension of the matroid basis problem to generalized polymatroids, and
additionally allow element multiplicities. Building on the approach of Kiraly, Lau and
Singh, 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 number r_v of
times. Our approach combines our algorithm for the Lower Bounded Degree Generalized
Polymatroid Basis Problem with Multiplicities with the principle of Christofides'
algorithm from 1976 for the (single-visit) metric TSP, whose approximation guarantee it
matches.
We also present a new algorithm for the general many-visits TSP without any metric
assumptions on the edge cost. For this problem, Cosmadakis and Papadimitriou (SICOMP,
1984) provided an algorithm that finds an optimal tour in time and space that depends
superexponentially on the number of cities. We give an improved algorithm which
simultaneously improves the time complexity to single-exponential, and the space
complexity to polynomial. Assuming the Exponential Time Hypothesis, the run time of our
algorithm is asymptotically optimal. Our algorithm is arguably simpler than the one by
Cosmadakis and Papadimitriou.
(Based on joint work with Kristof Berczi, Andre Berger, Tamas Kiraly, Laszlo Kozma, Gyula
Pap and Roland Vincze)
Short Bio:
==========
Matthias Mnich is an assistant professor of quantitative economics at Maastricht
University, The Netherlands, currently on leave for research in theoretical computer
science at the Rheinische Friedrich-Wilhelms Universitaet Bonn, Germany.
He obtained his PhD in 2010 at Eindhoven University of Technology, for which he received
the Philips Prize 2010. Since then he held positions at UC Berkeley, USA and the Max
Planck Institute for Computer Science, and a visiting professorship at TU Darmstadt,
Germany.
His research interests are in combinatorial algorithms, social choice theory, algorithms
for big data, and algorithms in artificial intelligence.
==================================================
Refreshments will be served from 14:15
Lecture starts at 14:30