Jens Vygen

Affiliations:
  • University of Bonn, Germany


According to our database1, Jens Vygen authored at least 68 papers between 1995 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Cost Allocation for Set Covering: the Happy Nucleolus.
CoRR, 2024

2023
Beating the Integrality Ratio for $s$-$t$-Tours in Graphs.
SIAM J. Comput., December, 2023

Approximating Maximum Integral Multiflows on Bounded Genus Graphs.
Discret. Comput. Geom., December, 2023

Approximating the discrete time-cost tradeoff problem with bounded depth.
Math. Program., February, 2023

Improving the approximation ratio for capacitated vehicle routing.
Math. Program., February, 2023

Packing cycles in planar and bounded-genus graphs.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Improved Guarantees for the a Priori TSP.
Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

2022
Reducing Path TSP to TSP.
SIAM J. Comput., June, 2022

An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem.
SIAM J. Comput., 2022

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks.
CoRR, 2022

Faster Goal-Oriented Shortest Path Search for Bulk and Incremental Detailed Routing.
Proceedings of the Integer Programming and Combinatorial Optimization, 2022

2021
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths.
SIAM J. Discret. Math., 2021

2020
Few Sequence Pairs Suffice: Representing All Rectangle Placements.
SIAM J. Discret. Math., 2020

The asymmetric traveling salesman path LP has constant integrality ratio.
Math. Program., 2020

An improved approximation algorithm for ATSP.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 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 <i>s</i>-<i>t</i>-path TSP.
J. ACM, 2019

Vehicle routing with subtours.
Discret. Optim., 2019

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

Global Routing With Timing Constraints.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2018

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

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

2017
Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges.
SIAM J. Discret. 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. Discret. 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.
Comb., 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. Comput. Aided Des. Integr. Circuits Syst., 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.
Proc. 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. Comput. Aided Des. Integr. Circuits Syst., 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. Comput. Aided Des. Integr. Circuits Syst., 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. Methods Oper. Res., 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


  Loading...