Martin Nägele

Last Name

Nägele

First Name

Martin

ORCID

0000-0002-3059-6402

Organisational unit

09487 - Zenklusen, Rico / Zenklusen, Rico

Show all metadata

Search Results

Publications 1 - 9 of 9

Constrained Submodular Minimisation
Nägele, Martin (2017)
We study two classes of constrained submodular minimisation problems, where a submodular function f defined on a lattice family L is to be minimised over a subfamily of L. In the first class, so-called congruency constrained submodular minimisation (CSM) problems, the subfamilies are of the form F = { S ∈ L : |S| ≡ r (mod m) }. For the second class of problems, namely generalised congruency constrained submodular minimisation (GCSM) problems, we are given a constant number of fixed sets S_1, ..., S_k and consider subfamilies of the form F = { S ∈ L : ∀ i: |S_i ∩ S| ≡ r_i (mod m) }. If m is a prime power, we provide polynomial time algorithms to solve both CSM and GCSM problems. Our algorithms rely on guessing a constant number of elements that belong to an optimal solutions and a constant number that do not. While our approaches and algorithms for CSM and GCSM problems can be seen as generalisations of a result by Goemans and Ramakrishnan for minimising submodular functions over parity families, we introduce and apply new techniques for proving correctness of the algorithms. Among others, this includes handling purely combinatorial problems on existence of set systems with certain covering properties and restricted intersections modulo m. We also show that for strong combinatorial reasons, our current methods do not generalise to CSM and GCSM problems with moduli other than prime powers.
Congruency-Constrained TU Problems Beyond the Bimodular Case
Nägele, Martin; Santiago, Richard; Zenklusen, Rico (2022)
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
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.
A better-than-1.6-approximation for prize-collecting TSP
Blauth, Jannis; Klein, Nathan; Nägele, Martin (2025)
Mathematical Programming
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 (1+$\sqrt{5}$)/2 ≈ 1.618, the golden ratio. With some additional technical care we further improve the approximation guarantee to 1.599. Furthermore, we show that for the path version of Prize-Collecting TSP (known as Prize-Collecting Stroll) our approach yields an approximation guarantee of 1.6662, improving upon the previous best-known guarantee of 1.926.
Advances on Strictly Δ-Modular IPs
Nägele, Martin; Nöbel, Christian; Santiago, Richard; et al. (2023)
Lecture Notes in Computer Science ~ Integer Programming and Combinatorial Optimization
A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
Nägele, Martin; Zenklusen, Rico (2024)
Mathematics of Operations Research
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 in which the value of a table entry does not only depend on the values of previous table entries, as 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 + epsilon, 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 (or, more precisely, a proxy thereof) as used in the context of (path) TSP and one of its generalizations and discuss implications in this context.
Congruency-Constrained TU Problems Beyond the Bimodular Case
Nägele, Martin; Santiago, Richard; Zenklusen, Rico (2024)
Mathematics of Operations Research
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{cTx : Tx ≤ b, γTx ≡ r(mod m), x ∈ Zn} with a totally unimodular constraint matrix T. Such problems are shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, that is, full-rank matrices whose n × n subdeterminants are bounded by two in absolute value. Whereas these advances heavily rely on existing results on well-known combinatorial problems with parity constraints, new approaches are needed beyond the bimodular case, that is, 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 using a randomized algorithm. 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.
Efficient Methods for Congruency-Constrained Optimization
Nägele, Martin (2021)
In this thesis, we study discrete combinatorial optimization problems with congruency constraints and present new techniques for dealing with such constraint types. Strong motivation for studying congruency constraints comes from a long-standing open question in Integer Programming whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min { : Tx ≤ b, <γ, x> ≡ r (mod m), x ∈ Z^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 by n subdeterminants are bounded by two in absolute value. Whereas these advances heavily relied on existing results on well-known combinatorial minimum cut and circulation problems with parity constraints, new approaches are needed beyond the bimodular case, i.e., 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. In the second part of this thesis, we study a generalization of the aforementioned parity-constrained minimum cut problems (and therefore also a generalization of other well-known variants of minimum cut problems such as global minimum cuts and minimum s-t cuts), namely congruency-constrained minimum cuts, where we consider cuts whose number of vertices is congruent to r modulo m, for some integers r and m. 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. Finally, we present results on finding a spanning tree subject to constraints on the edges in a family of cuts forming a laminar family of small width. Especially in the context of the Traveling Salesman Problem (TSP), new techniques for finding spanning trees with well-defined properties, and in particular, trees satisfying parity constraints on a chain of cuts, have been crucial in pushing a the analysis of a certain class of approximation algorithms. 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, including a relaxation of congruency constraints, or upper and lower bounds on the number of edges in each cut. Concretely, we present a quasi-polynomial time algorithm for the Minimum Chain-Constrained Spanning Tree Problem with an essentially best possible guarantee. Furthermore, we show how parity constraints as used in the context of (path) TSP and a generalization thereof can be handled, and discuss implications in this context.
A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP
Armbruster, Susanne; Mnich, Matthias; Nägele, Martin (2024)
Leibniz International Proceedings in Informatics (LIPIcs) ~ Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
We present a new (3/2+1/e)-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classic metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately 1.868 holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of 5/2 for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction.
Advances on strictly ∆-modular IPs
Nägele, Martin; Nöbel, Christian; Santiago, Richard; et al. (2024)
Mathematical Programming
There has been significant work recently on integer programs (IPs) min {cᵀx : Ax ≤ b, x ∈ Zⁿ} with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant ∆ ∈ Z_>0, ∆-modular IPs are efficiently solvable, which are IPs where the constraint matrix A ∈ Zᵐ ˣ ⁿ has full column rank and all n x 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 x 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 there is a randomized algorithm to check feasibility of strictly ∆-modular IPs in strongly polynomial time if ∆ ≤ 4.

Publications 1 - 9 of 9

Martin Nägele

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results