Jens Vygen

[Homepage] [Bio] [Projects] [Publications] [Committees] [Courses] [Information for Students]

Books:

V. Traub, J. Vygen:
Approximation Algorithms for Traveling Salesman Problems
Cambridge University Press 2025
More information
B. Korte, J. Vygen:
Combinatorial Optimization: Theory and Algorithms
Algorithms and Combinatorics 21, Springer
First Edition 2000
Second Edition 2002
Japanese Edition 2005
Third Edition 2006
Fourth Edition 2008
German Edition 2008
Second Japanese Edition 2009
French Edition 2010
Italian Edition 2011
Fifth Edition 2012
Second German Edition 2012
Chinese Edition 2014
Russian Edition 2015
Second French Edition 2018
Sixth Edition 2018
Third German Edition 2018
Third Japanese Edition 2022
More Information
S. Hougardy, J. Vygen:
Algorithmic Mathematics
Springer
German Edition 2016
English Edition 2016
Second German Edition 2018
Chinese Edition 2020
More Information
J. Vygen, J. Byrka (Eds.):
Integer Programming and Combinatorial Optimization
(Proceedings of IPCO 2024)
LNCS 14679, Springer 2024
More information
J. Lee, J. Vygen (Eds.):
Integer Programming and Combinatorial Optimization
(Proceedings of IPCO 2014)
LNCS 8494, Springer 2014
More Information
W.J. Cook, L. Lovász, J. Vygen (Eds.):
Research Trends in Combinatorial Optimization
(Bonn 2008)
Springer 2009
More Information

Selected papers (newest first):

Please send me an e-mail if you are interested in any paper that you cannot find here. For an almost complete list with many links, see Google Scholar.

J. Blauth, M. Neuwohner, L. Puhlmann, J. Vygen: Improved guarantees for the a priori TSP. Mathematics of Operations Research, to appear. Extended abstract in the Proceedings of ISAAC 2023, Article 14
N. Schlomberg, H. Thiele, J. Vygen: Packing cycles in planar and bounded-genus graphs. SIAM Journal on Computing 54 (2025), 469–502. Extended abstract in SODA 2023
J. Blauth, A. Ellerbrock, V. Traub, J. Vygen: Cost allocation for set covering: the happy nucleolus. Operations Research Letters 57 (2024), 107158
J. Blauth, S. Held, D. Müller, N. Schlomberg, V. Traub, T. Tröbst, J. Vygen: Vehicle routing with time-dependent travel times: theory, practice, and benchmarks. Discrete Optimization 53 (2024), 100848
M. Ahrens, D. Henke, S. Rabenstein, J. Vygen: Faster goal-oriented shortest path search for bulk and incremental detailed routing. Mathematical Programming 206 (2024), 3–32. Extended abstract in IPCO 2022
J. Blauth, V. Traub, J. Vygen: Improving the approximation ratio for capacitated vehicle routing. Mathematical Programming 197 (2023), 451–497. Extended abstract in IPCO 2021 (Best Paper Award)
S. Daboul, S. Held, J. Vygen: Approximating the discrete time-cost tradeoff problem with bounded depth. Mathematical Programming 197 (2023), 529–547. Extended abstract in IPCO 2021
C.-C. Huang, M. Mari, C. Mathieu, J. Vygen: Approximating maximum integral multiflows on bounded genus graphs. Discrete & Computational Geometry 70 (2023), 1266–1291. Extended abstract in ICALP 2021
V. Traub, J. Vygen: An improved approximation algorithm for the asymmetric traveling salesman problem. SIAM Journal on Computing 51 (2022), 139–173. Extended abstract in STOC 2020
V. Traub, J. Vygen, R. Zenklusen: Reducing Path TSP to TSP. SIAM Journal on Computing 51 (2022), STOC20-24–STOC-20-53. Extended abstract in STOC 2020
C.-C. Huang, M. Mari, C. Mathieu, K. Schewior, J. Vygen: An approximation algorithm for fully planar edge-disjoint paths. SIAM Journal on Discrete Mathematics 35 (2021), 752–769
A. Köhne, V. Traub, J. Vygen: The asymmetric traveling salesman path LP has constant integrality ratio. Mathematical Programming 183 (2020), 379–395. Preliminary version in IPCO 2019
V. Traub, J. Vygen: Beating the integrality ratio for s-t-tours in graphs. SIAM Journal on Computing 52 (2023), FOCS18-37–FOCS18-84. Extended abstract in FOCS 2018
J. Silvanus, J. Vygen: Few sequence pairs suffice: representing all rectangle placements. SIAM Journal on Discrete Mathematics 34 (2020), 2017–2032
S. Held, J. Könemann, J. Vygen: Vehicle routing with subtours. Discrete Optimization 33 (2019), 87–100
V. Traub, J. Vygen: An improved upper bound on the integrality ratio for the s-t-path TSP. Operations Research Letters 47 (2019), 225–228
V. Traub, J. Vygen: Approaching 3/2 for the s-t-path TSP. Journal of the ACM 66 (2019), Article 14. Preliminary version in SODA 2018 (Best Paper Award)
S. Daboul, S. Held, J. Vygen, S. Wittke: An approximation algorithm for threshold voltage optimization. ACM Transactions on Design Automation of Electronic Systems 23 (2018), Article 68
C. Gottschalk, J. Vygen: Better s-t-tours by Gao trees. Mathematical Programming B 172 (2018), 191–207. Preliminary version in IPCO 2016
S. Held, D. Müller, D. Rotter, R. Scheifele, V. Traub, J. Vygen: Global routing with timing constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37 (2018), 406–419. Preliminary version in ICCAD 2015
J. Könemann, N. Olver, K. Pashkovish, R. Ravi, C. Swamy, J. Vygen: On the integrality gap of the prize-collecting Steiner forest LP. Proceedings of APPROX 2017, Article 17
K. Heeger, J. Vygen: Two-connected spanning subgraphs with at most 10/7 OPT edges. SIAM Journal on Discrete Mathematics 31 (2017), 1820–1835
S. Hougardy, J. Silvanus, J. Vygen: Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm. Mathematical Programming Computation 9 (2017), 135–202
J. Vygen: Reassembling trees for the traveling salesman. SIAM Journal on Discrete Mathematics 30 (2016), 875–894
A. Sebő, J. Vygen: Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica 34 (2014), 597–629
D. Rotter, J. Vygen: d-dimensional arrangement revisited. Information Processing Letters 113 (2013), 498–505
M. Gester, D. Müller, T. Nieberg, C. Panten, C. Schulte, J. Vygen: BonnRoute: Algorithms and data structures for fast and good VLSI routing. ACM Transactions on Design Automation of Electronic Systems 18 (2013), Article 32. Preliminary version in DAC 2012
J. Vygen: New approximation algorithms for the TSP. OPTIMA 90 (2012), 1–12
J. Vygen: Faster algorithm for optimum Steiner trees. Information Processing Letters 111 (2011), 1075–1079
D. Müller, K. Radke, J. Vygen: Faster min-max resource sharing in theory and practice. Mathematical Programming Computation 3 (2011), 1–35
S. Held, B. Korte, D. Rautenbach, J. Vygen: Combinatorial optimization in VLSI design. In: "Combinatorial Optimization: Methods and Applications" (V. Chvátal, ed.), IOS Press, Amsterdam 2011, pp. 33–96
C. Bartoschek, S. Held, J. Maßberg, D. Rautenbach, J. Vygen: The repeater tree construction problem. Information Processing Letters 110 (2010), 1079–1083. Preliminary version in ISPD 2006
S. Peyer, D. Rautenbach, J. Vygen: A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing. Journal of Discrete Algorithms 7 (2009), 377–390
C. Bartoschek, S. Held, D. Rautenbach, J. Vygen: Fast buffering for optimizing worst slack and resource consumption in repeater trees. Proceedings of the International Symposium on Physical Design (2009), 43–50
U. Brenner, J. Vygen: Analytical methods in VLSI placement. In: Handbook of Algorithms for VLSI Physical Design Automation (C.J. Alpert, D.P. Mehta, S.S. Sapatnekar, eds.), Taylor and Francis, Boca Raton 2009, pp. 327–346
B. Korte, J. Vygen: Combinatorial problems in chip design. In: Building Bridges Between Mathematics and Computer Science (M. Grötschel, G.O.H. Katona, eds.), Springer, Berlin 2008, pp. 333–368
U. Brenner, M. Struzyna, J. Vygen: BonnPlace: Placement of leading-edge chips by advanced combinatorial algorithms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27 (2008), 1607–1620. Preliminary version in DAC 1997
J. Maßberg, J. Vygen: Approximation algorithms for a facility location problem with service capacities. ACM Transactions on Algorithms 4 (2008), Article 50. Preliminary version in APPROX 2005
J. Vygen: From stars to comets: Improved local search for universal facility location. Operations Research Letters 35 (2007), 427–433
B. Korte, D. Rautenbach, J. Vygen: BonnTools: Mathematical innovation for layout and timing closure of systems on a chip. Proceedings of the IEEE 95 (2007), 555–572
J. Vygen: New theoretical results on quadratic placement. Integration, the VLSI Journal 40 (2007), 305–314
J. Vygen: Slack in static timing analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25 (2006), 1876–1885
J. Vygen: Approximation algorithms for facility location problems (Lecture Notes). Technical Report No. 05950, Research Institute for Discrete Mathematics, University of Bonn, 2005
J. Vygen: Geometric quadrisection in linear time, with application to VLSI placement. Discrete Optimization 2 (2005), 362–390
U. Brenner, J. Vygen: Legalizing a placement with minimum total movement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 23 (2004), 1597–1613. Preliminary versions and related results in DATE 1998, DATE 2000, and ISPD 2004
S. Held, B. Korte, J. Maßberg, M. Ringe, J. Vygen: Clock scheduling and clocktree construction for high performance ASICs. Proceedings of the IEEE International Conference on Computer-Aided Design (2003), 232–239
J. Vygen: A note on Schrijver's submodular function minimization algorithm. Journal of Combinatorial Theory B 88 (2003), 399–402
C. Albrecht, B. Korte, J. Schietke, J. Vygen: Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chip. Discrete Applied Mathematics 123 (2002), 103–127. Preliminary version in ICCAD 1999
J. Vygen: On dual minimum cost flow algorithms. Mathematical Methods of Operations Research 56 (2002), 101–126. Preliminary version in STOC 2000
U. Brenner, J. Vygen: Worst-case ratios of networks in the rectilinear plane. Networks 38 (2001), 126–139
T. Nishizeki, J. Vygen, X. Zhou : The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discrete Applied Mathematics 115 (2001), 177–186
J. Vygen: NP-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics 61 (1995), 83–90