Zobrazeno 1 - 9
of 9
pro vyhledávání: '"Jens Vygen"'
Publikováno v:
Mathematical Programming. 183:379-395
We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. If $\rho_{\text{ATSP}}$ and $\rho_{\text{ATSPP}}$ denote the integrality ratios for the asymmetric TSP and its path ver
Publikováno v:
SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, 2021, 35 (2), pp.752-769. ⟨10.1137/20M1319401⟩
SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2021, 35 (2), pp.752-769. ⟨10.1137/20M1319401⟩
SIAM Journal on Discrete Mathematics, 2021, 35 (2), pp.752-769. ⟨10.1137/20M1319401⟩
SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2021, 35 (2), pp.752-769. ⟨10.1137/20M1319401⟩
International audience; We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges form a planar graph. By planar duality this is equivalent t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b39abe85a4d30b0ffe66488a3d812d6a
https://hal.archives-ouvertes.fr/hal-03099892/document
https://hal.archives-ouvertes.fr/hal-03099892/document
We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is denoted by $d$
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::79a559a8a695aa5803ca7833ebf7ce83
http://arxiv.org/abs/2011.02446
http://arxiv.org/abs/2011.02446
Publikováno v:
STOC
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
We present a black-box reduction from the path version of the Traveling Salesman Problem (Path TSP) to the classical tour version (TSP). More precisely, we show that given an $\alpha$-approximation algorithm for TSP, then, for any $\epsilon >0$, ther
Autor:
Klaus Heeger, Jens Vygen
Publikováno v:
SIAM Journal on Discrete Mathematics. 31:1820-1835
We present a $\frac{10}{7}$-approximation algorithm for the minimum 2-vertex-connected spanning subgraph problem. Similarly to the work of Cheriyan, Sebo, and Szigeti for 2-edge-connected spanning subgraphs, our algorithm is based on computing a care
Autor:
Jens Vygen, Vera Traub
Publikováno v:
STOC
We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and V\'egh. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simp
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::974d7b79f7c4920b0d84d341dcbbd76c
Autor:
Jens Vygen, Vera Traub
Publikováno v:
FOCS
Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fb9219fa0973540ebeb44c95d52b397b
http://arxiv.org/abs/1804.03112
http://arxiv.org/abs/1804.03112
Autor:
Jens Vygen, Jannik Silvanus
We consider representations of general non-overlapping placements of rectangles by spatial relations (west, south, east, north) of pairs of rectangles. We call a set of representations complete if it contains a representation of every placement of $n
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9840d6b7fdb2c6f095d8494fb8111e38
http://arxiv.org/abs/1708.09779
http://arxiv.org/abs/1708.09779
Autor:
Jens Vygen
Many recent approximation algorithms for different variants of the traveling salesman problem (asymmetric TSP, graph TSP, s-t-path TSP) exploit the well-known fact that a solution of the natural linear programming relaxation can be written as convex
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4f0e194713df078fbbe8a50e3de8b725
http://arxiv.org/abs/1502.03715
http://arxiv.org/abs/1502.03715