# Jens Vygen

According to our database1, Jens Vygen authored at least 58 papers between 1995 and 2020.

Collaborative distances:

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2020
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths.
CoRR, 2020

2019
An improved upper bound on the integrality ratio for the s-t-path TSP.
Oper. Res. Lett., 2019

Approaching 3/2 for the s-t-path TSP.
J. ACM, 2019

Vehicle routing with subtours.
Discret. Optim., 2019

An improved approximation algorithm for ATSP.
CoRR, 2019

Reducing Path TSP to TSP.
CoRR, 2019

The Asymmetric Traveling Salesman Path LP Has Constant Integrality Ratio.
Proceedings of the Integer Programming and Combinatorial Optimization, 2019

2018
An Approximation Algorithm for Threshold Voltage Optimization.
ACM Trans. Design Autom. Electr. Syst., 2018

Global Routing With Timing Constraints.
IEEE Trans. on CAD of Integrated Circuits and Systems, 2018

Better s-t-tours by Gao trees.
Math. Program., 2018

Approaching for the s-t-path TSP.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Beating the Integrality Ratio for s-t-Tours in Graphs.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges.
SIAM J. Discrete Math., 2017

Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm.
Math. Program. Comput., 2017

Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP.
CoRR, 2017

On the Integrality Gap of the Prize-Collecting Steiner Forest LP.
Proceedings of the Approximation, 2017

2016
Reassembling Trees for the Traveling Salesman.
SIAM J. Discrete Math., 2016

Two-connected spanning subgraphs with at most 10/7 OPT edges.
CoRR, 2016

2015
Preface.
Math. Program., 2015

Global Routing with Inherent Static Timing Constraints.
Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2015

2014
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, 2014

2013
BonnRoute: Algorithms and data structures for fast and good VLSI routing.
ACM Trans. Design Autom. Electr. Syst., 2013

d-dimensional arrangement revisited.
Inf. Process. Lett., 2013

2012
Shorter Tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs.
CoRR, 2012

Algorithms and data structures for fast and good VLSI routing.
Proceedings of the 49th Annual Design Automation Conference 2012, 2012

2011
Combinatorial Optimization in VLSI Design.
Proceedings of the Combinatorial Optimization - Methods and Applications, 2011

Faster min-max resource sharing in theory and practice.
Math. Program. Comput., 2011

Faster algorithm for optimum Steiner trees.
Inf. Process. Lett., 2011

Splitting trees at vertices.
Discret. Math., 2011

2010
The repeater tree construction problem.
Inf. Process. Lett., 2010

2009
A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing.
J. Discrete Algorithms, 2009

Fast buffering for optimizing worst slack and resource consumption in repeater trees.
Proceedings of the 2009 International Symposium on Physical Design, 2009

2008
Analytical Methods in Placement.
Proceedings of the Handbook of Algorithms for Physical Design Automation., 2008

BonnPlace: Placement of Leading-Edge Chips by Advanced Combinatorial Algorithms.
IEEE Trans. on CAD of Integrated Circuits and Systems, 2008

Approximation algorithms for a facility location problem with service capacities.
ACM Trans. Algorithms, 2008

2007
BonnTools: Mathematical Innovation for Layout and Timing Closure of Systems on a Chip.
Proceedings of the IEEE, 2007

From stars to comets: Improved local search for universal facility location.
Oper. Res. Lett., 2007

New theoretical results on quadratic placement.
Integr., 2007

2006
Slack in static timing analysis.
IEEE Trans. on CAD of Integrated Circuits and Systems, 2006

Efficient generation of short and fast repeater tree topologies.
Proceedings of the 2006 International Symposium on Physical Design, 2006

2005
Geometric quadrisection in linear time, with application to VLSI placement.
Discret. Optim., 2005

Approximation Algorithms for Network Design and Facility Location with Service Capacities.
Proceedings of the Approximation, 2005

2004
Legalizing a placement with minimum total movement.
IEEE Trans. on CAD of Integrated Circuits and Systems, 2004

Almost optimum placement legalization by minimum cost flow and dynamic programming.
Proceedings of the 2004 International Symposium on Physical Design, 2004

Near-Optimum Global Routing with Coupling, Delay Bounds, and Power Consumption.
Proceedings of the Integer Programming and Combinatorial Optimization, 2004

2003
A note on Schrijver's submodular function minimization algorithm.
J. Comb. Theory, Ser. B, 2003

Clock Scheduling and Clocktree Construction for High Performance ASICS.
Proceedings of the 2003 International Conference on Computer-Aided Design, 2003

2002
On dual minimum cost flow algorithms.
Math. Meth. of OR, 2002

Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chip.
Discret. Appl. Math., 2002

2001
Worst-case ratios of networks in the rectilinear plane.
Networks, 2001

The edge-disjoint paths problem is NP-complete for series-parallel graphs.
Discret. Appl. Math., 2001

2000
On dual minimum cost flow algorithms (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Faster Optimal Single-Row Placement with Fixed Ordering.
Proceedings of the 2000 Design, 2000

1999
Cycle time and slack optimization for VLSI-chips.
Proceedings of the 1999 IEEE/ACM International Conference on Computer-Aided Design, 1999

1998
Algorithms for Detailed Placement of Standard Cells.
Proceedings of the 1998 Design, 1998

1997
Algorithms for Large-Scale Flat Placement.
Proceedings of the 34st Conference on Design Automation, 1997

1996
Plazierung im VLSI-Design und ein zweidimensionales Zerlegungsproblem.
PhD thesis, 1996

1995
NP-completeness of Some Edge-disjoint Paths Problems.
Discret. Appl. Math., 1995