Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solution is then measured by adding the length of the tour and the sum of all penalties of vertices that are not visited. We present a polynomial-time approximation algorithm with an approximation guarantee slightly below 1.6, where the guarantee is with respect to the natural linear programming relaxation of the problem. This improves upon the previous best-known approximation ratio of 1.774.
Our approach is based on a known decomposition for solutions of this linear relaxation into rooted trees. Our algorithm takes a tree from this decomposition and then performs a pruning step before doing parity correction on the remainder. Using a simple analysis, we bound the approximation guarantee of the proposed algorithm by the golden ratio (approx. 1.618). With some additional technical care we further improve it to 1.599.
@misc{blauth_2024_better,author={Blauth, Jannis and Klein, Nathan and N{\"a}gele, Martin},title={A Better-Than-1.6-Approximation Algorithm for Prize-Collecting TSP},eprinttype={arXiv},eprint={2308.06254},eprintclass={cs.DS},note={To appear in <i>Proceedings of the 25th Conference on Integer Programming and Combinatorial Optimization (IPCO~'24)</i>},year={2024},year_corrected={2023},doi={10.48550/arXiv.2208.06254}}
2023
Math. Oper. Res.
A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global minimum cuts, minimum s-t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers r and m. Apart from being a natural generalization of odd cuts, congruency-constrained minimum cuts exhibit an interesting link to a long-standing open problem in Integer Programming, namely whether integer programs described by an integer constraint matrix with bounded subdeterminants can be solved efficiently.
We develop a new contraction technique inspired by Karger’s celebrated contraction algorithm for minimum cuts, that, together with further insights, leads to a polynomial time randomized approximation scheme for congruency-constrained minimum cuts for any constant modulus m. Instead of contracting edges of the original graph, we use splitting-off techniques to create an auxiliary graph on a smaller vertex set, which is used for performing random edge contractions. This way, a well-structured distribution of candidate pairs of vertices to be contracted is obtained, where the involved pairs are generally not connected by an edge. As a byproduct, our technique reveals new structural insights into near-minimum odd cuts, and, more generally, near-minimum congruency-constrained cuts.
@article{naegele_2023_newDP,author={N{\"a}gele, Martin and Zenklusen, Rico},title={A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond},year={2023},journal={Mathematics of Operations Research},issue={0},number={0},pages={},doi={10.1287/moor.2023.0012}}
STOC ’23
An improved approximation guarantee for Prize-Collecting TSP
We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (TSP), one may choose to not include a vertex of the input graph in the returned tour at the cost of a given vertex-dependent penalty, and the objective is to balance the length of the tour and the incurred penalties for omitted vertices by minimizing the sum of the two. We present an algorithm that achieves an approximation guarantee of 1.774 with respect to the natural linear programming relaxation of the problem. This significantly reduces the gap between the approximability of classical TSP and PCTSP, beating the previously best known approximation factor of 1.915. As a key ingredient of our improvement, we present a refined decomposition technique for solutions of the LP relaxation, and show how to leverage components of that decomposition as building blocks for our tours.
@inproceedings{blauth_2023_improved,author={Blauth, Jannis and N{\"a}gele, Martin},title={An improved approximation guarantee for Prize-Collecting TSP},year={2023},pages={1848--1861},booktitle={Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC~'23)},doi={10.1145/3564246.3585159}}
There has been significant work recently on integer programs (IPs) min{cTx : Ax ≤ b, x ∊ ℤn} with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant positive integer ∆, ∆-modular IPs are efficiently solvable, which are IPs where the m by n constraint matrix A has full column rank and all n by n minors of A are within {-∆, …, ∆}. Previous progress on this question, in particular for ∆ = 2, relies on algorithms that solve an important special case, namely strictly ∆-modular IPs, which further restrict the n by n minors of A to be within {-∆, 0, ∆}. Even for ∆ = 2, such problems include well-known combinatorial optimization problems like the minimum odd/even cut problem. The conjecture remains open even for strictly ∆-modular IPs. Prior advances were restricted to prime ∆, which allows for employing strong number-theoretic results.
In this work, we make first progress beyond the prime case by presenting techniques not relying on such strong number-theoretic prime results. In particular, our approach implies that one can check feasibility of strictly ∆-modular IPs in strongly polynomial time if ∆ ≤ 4.
@inproceedings{naegele_2023_advances,author={N{\"a}gele, Martin and N{\"o}bel, Christian and Santiago, Richard and Zenklusen, Rico},title={Advances on Strictly $\Delta$-Modular IPs},year={2023},pages={393--407},booktitle={Proceedings of the 24th Conference on Integer Programming and Combinatorial Optimization (IPCO~'23)},doi={10.1007/978-3-031-32726-1_28}}
Math. Oper. Res.
Congruency-Constrained TU Problems Beyond the Bimodular Case
A long-standing open question in Integer Programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min { cT x: Tx ≤ b, γT x ≡ r (mod m), x ∊ ℤn } with a totally unimodular constraint matrix T. Such problems have been shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, i.e., full-rank matrices whose n × n subdeterminants are bounded by two in absolute value. Whereas these advances heavily relied on existing results on well-known combinatorial problems with parity constraints, new approaches are needed beyond the bimodular case, i.e., for m > 2.
We make first progress in this direction through several new techniques. In particular, we show how to efficiently decide feasibility of congruency-constrained integer programs with a totally unimodular constraint matrix for m = 3. Furthermore, for general m, our techniques also allow for identifying flat directions of infeasible problems, and deducing bounds on the proximity between solutions of the problem and its relaxation.
@article{naegele_2023_congruency,author={N{\"a}gele, Martin and Santiago, Richard and Zenklusen, Rico},title={Congruency-Constrained TU Problems Beyond the Bimodular Case},year={2023},journal={Mathematics of Operations Research},issue={0},number={0},pages={},doi={10.1287/moor.2023.1381}}
2022
SODA ’22
Congruency-Constrained TU Problems Beyond the Bimodular Case
A long-standing open question in Integer Programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min { cT x: Tx ≤ b, γT x ≡ r (mod m), x ∊ ℤn } with a totally unimodular constraint matrix T. Such problems have been shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, i.e., full-rank matrices whose n × n subdeterminants are bounded by two in absolute value. Whereas these advances heavily relied on existing results on well-known combinatorial problems with parity constraints, new approaches are needed beyond the bimodular case, i.e., for m > 2.
We make first progress in this direction through several new techniques. In particular, we show how to efficiently decide feasibility of congruency-constrained integer programs with a totally unimodular constraint matrix for m = 3. Furthermore, for general m, our techniques also allow for identifying flat directions of infeasible problems, and deducing bounds on the proximity between solutions of the problem and its relaxation.
@inproceedings{naegele_2022_congruency,author={N{\"a}gele, Martin and Santiago, Richard and Zenklusen, Rico},title={Congruency-Constrained TU Problems Beyond the Bimodular Case},booktitle={Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA~'22)},year={2022},pages={2743--2790},doi={10.1137/1.9781611977073.108}}
2020
Math. Program.
A new contraction technique with applications to congruency-constrained cuts
Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global mininmum cuts, minimum s–t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers r and m. Apart from being a natural generalization of odd cuts, congruency-constrained minimum cuts exhibit an interesting link to a long-standing open problem in Integer Programming, namely whether integer programs described by an integer constraint matrix with bounded subdeterminants can be solved efficiently. We develop a new contraction technique inspired by Karger’s celebrated contraction algorithm for minimum cuts, which, together with further insights, leads to a polynomial time randomized approximation scheme for congruency-constrained minimum cuts for any constant modulus m. Instead of contracting edges of the original graph, we use splitting-off techniques to create an auxiliary graph on a smaller vertex set, which is used for performing random edge contractions. This way, a well-structured distribution of candidate pairs of vertices to be contracted is obtained, where the involved pairs are generally not connected by an edge. As a byproduct, our technique reveals new structural insights into near-minimum odd cuts, and, more generally, near-minimum congruency-constrained cuts.
@article{naegele_2020_newContraction,author={N{\"a}gele, Martin and Zenklusen, Rico},year={2020},pages={455--481},title={A new contraction technique with applications to congruency-constrained cuts},volume={183},number={1},journal={Mathematical Programming},doi={10.1007/s10107-020-01498-x}}
2019
Combinatorica
Submodular Minimization Under Congruency Constraints
Submodular function minimization (SFM) is a fundamental and efficiently solvable problem in combinatorial optimization with a multitude of applications in various fields. Surprisingly, there is only very little known about constraint types under which SFM remains efficiently solvable. The arguably most relevant non-trivial constraint class for which polynomial SFM algorithms are known are parity constraints, i.e., optimizing only over sets of odd (or even) cardinality. Parity constraints capture classical combinatorial optimization problems like the odd-cut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose subdeterminants are bounded by two in absolute value.
We show that efficient SFM is possible even for a significantly larger class than parity constraints, by introducing a new approach that combines techniques from Combinatorial Optimization, Combinatorics, and Number Theory. In particular, we can show that effi- cient SFM is possible over all sets (of any given lattice) of cardinality r mod m, as long as m is a constant prime power. This covers generalizations of the odd-cut problem with open complexity status, and has interesting links to integer programming with bounded subdeterminants. To obtain our results, we establish a connection between the correctness of a natural algorithm, and the nonexistence of set systems with specific combinatorial properties. We introduce a general technique to disprove the existence of such set systems, which allows for obtaining extensions of our results beyond the above-mentioned setting. These extensions settle two open questions raised by Geelen and Kapadia [Combinatorica, 2017] in the context of computing the girth and cogirth of certain types of binary matroids.
@article{naegele_2019_submodular,author={N{\"a}gele, Martin and Sudakov, Benny and Zenklusen, Rico},title={Submodular Minimization Under Congruency Constraints},journal={Combinatorica},volume={39},number={6},pages={1351--1386},year={2019},doi={10.1007/s00493-019-3900-1}}
IPCO ’19
A new contraction technique with applications to congruency-constrained cuts
Minimum cut problems are among the most classical problems in Combinatorial Optimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global minimum cuts, minimum s-t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers r and m. Apart from being a natural generalization of odd cuts, congruency-constrained minimum cuts exhibit an interesting link to a long-standing open problem in Integer Programming, namely whether integer programs described by an integer constraint matrix with bounded subdeterminants can be solved efficiently.
We develop a new contraction technique inspired by Karger’s celebrated contraction algorithm for minimum cuts, that, together with further insights, leads to a polynomial time randomized approximation scheme for congruency-constrained minimum cuts for any constant modulus m. Instead of contracting edges of the original graph, we use splitting-off techniques to create an auxiliary graph on a smaller vertex set, which is used for performing random edge contractions. This way, a well-structured distribution of candidate pairs of vertices to be contracted is obtained, where the involved pairs are generally not connected by an edge. As a byproduct, our technique reveals new structural insights into near-minimum odd cuts, and, more generally, near-minimum congruency-constrained cuts.
@inproceedings{naegele_2019_newContraction,author={N{\"a}gele, Martin and Zenklusen, Rico},year={2019},pages={327--340},title={A new contraction technique with applications to congruency-constrained cuts},booktitle={Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization (IPCO~'19)},doi={10.1007/978-3-030-17953-3_25}}
SODA ’19
A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms, and, moreover, they capture interesting problem settings on their own. Especially in the context of the Traveling Salesman Problem (TSP), new techniques for finding spanning trees with well-defined properties have been crucial in recent progress. We consider the problem of finding a spanning tree subject to constraints on the edges in a family of cuts forming a laminar family of small width. Our main contribution is a new dynamic programming approach where the value of a table entry does not only depend on the values of previous table entries, as it is usually the case, but also on a specific representative solution saved together with each table entry. This allows for handling a broad range of constraint types. In combination with other techniques—including negatively correlated rounding and a polyhedral approach that, in the problems we consider, allows for avoiding potential losses in the objective through the randomized rounding—we obtain several new results. We first present a quasi-polynomial time algorithm for the Minimum Chain-Constrained Spanning Tree Problem with an essentially optimal guarantee. More precisely, each chain constraint is violated by a factor of at most 1 + ε, and the cost is no larger than that of an optimal solution not violating any chain constraint. The best previous procedure is a bicriteria approximation violating each chain constraint by up to a constant factor and losing another factor in the objective. Moreover, our approach can naturally handle lower bounds on the chain constraints, and it can be extended to constraints on cuts forming a laminar family of constant width. Furthermore, we show how our approach can also handle parity constraints as used in the context of (path) TSP and a generalization thereof, and discuss implications in this context.
@inproceedings{naegele_2019_newDP,author={N{\"a}gele, Martin and Zenklusen, Rico},title={A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond},booktitle={Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA~'19)},year={2019},pages={1550--1569},doi={10.1137/1.9781611975482.94}}
2018
SODA ’18
Submodular Minimization Under Congruency Constraints
Submodular function minimization (SFM) is a fundamental and efficiently solvable problem class in combinatorial optimization with a multitude of applications in various fields. Surprisingly, there is only very little known about constraint types under which SFM remains efficiently solvable. The arguably most relevant non-trivial constraint class for which polynomial SFM algorithms are known are parity constraints, i.e., optimizing only over sets of odd (or even) cardinality. Parity constraints capture classical combinatorial optimization problems like the odd-cut problem, and they are a key tool in a recent technique to efficiently solve integer programs with a constraint matrix whose subdeterminants are bounded by two in absolute value.
We show that efficient SFM is possible even for a significantly larger class than parity constraints, by introducing a new approach that combines techniques from Combinatorial Optimization, Combinatorics, and Number Theory. In particular, we can show that efficient SFM is possible over all sets (of any given lattice) of cardinality r mod m, as long as m is a constant prime power. This covers generalizations of the odd-cut problem with open complexity status, and with relevance in the context of integer programming with higher subdeterminants. To obtain our results, we establish a connection between the correctness of a natural algorithm, and the inexistence of set systems with specific combinatorial properties. We introduce a general technique to disprove the existence of such set systems, which allows for obtaining extensions of our results beyond the above-mentioned setting. These extensions settle two open questions raised by Geelen and Kapadia [Combinatorica, 2017] in the context of computing the girth and cogirth of certain types of binary matroids.
@inproceedings{naegele_2018_submodular,author={N{\"a}gele, Martin and Sudakov, Benny and Zenklusen, Rico},title={Submodular Minimization Under Congruency Constraints},booktitle={Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms 2018 (SODA~'18)},pages={849--866},year={2018},doi={10.1137/1.9781611975031.55}}
2016
Oper. Res. Lett.
Refuting a conjecture of Goemans on bounded degree spanning trees
In 2006, Goemans presented an approximation algorithm for the minimum bounded degree spanning tree problem that constructs a tree with cost at most the optimal value of an LP relaxation but degree bound violations of up to two units per vertex. He conjectured that violations of at most one per vertex are attainable, providing a second conjecture that would make his approach achieve this guarantee. While the first conjecture was answered positively by Singh and Lau, we refute the second.
@article{chestnut_2016_refuting,author={Chestnut, Stephen R. and N\"agele, Martin and Zenklusen, Rico},title={Refuting a conjecture of Goemans on bounded degree spanning trees},journal={Operations Research Letters},volume={44},number={6},pages={766--771},year={2016},doi={10.1016/j.orl.2016.09.014}}
Note: PDFs provided here may include potential updates and corrections done after publication (check links to the publishers for their versions). For conference publications, the PDF corresponds to full versions of the paper (if available).