Zobrazeno 1 - 10
of 23
pro vyhledávání: '"Nägele, Martin"'
We present a new $(\frac32+\frac1{\mathrm{e}})$-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metric Traveling Salesperson Problem (TSP) where a specified subset of vert
Externí odkaz:
http://arxiv.org/abs/2405.06244
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
Externí odkaz:
http://arxiv.org/abs/2308.06254
There has been significant work recently on integer programs (IPs) $\min\{c^\top x \colon Ax\leq b,\,x\in \mathbb{Z}^n\}$ with a constraint marix $A$ with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any co
Externí odkaz:
http://arxiv.org/abs/2302.07029
Autor:
Nägele, Martin, Zenklusen, Rico
Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms. Especially in the context of the Traveling Salesman Problem (TSP), new techniques for finding spanning trees with well-defined p
Externí odkaz:
http://arxiv.org/abs/2301.09340
Autor:
Blauth, Jannis, Nägele, Martin
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 not include a vertex of the input graph in the returned
Externí odkaz:
http://arxiv.org/abs/2212.03776
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\{c^\t
Externí odkaz:
http://arxiv.org/abs/2109.03148
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Nägele, Martin1 mnaegele@uni-bonn.de, Santiago, Richard2 rtorres@ethz.ch, Zenklusen, Rico2 ricoz@ethz.ch
Publikováno v:
Mathematics of Operations Research. Aug2024, Vol. 49 Issue 3, p1303-1348. 46p.
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 unde
Externí odkaz:
http://arxiv.org/abs/1707.06212
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.