6 citations · 19 across the 16 of their papers we have counts for
4 papers · 2 filters
Improving the Approximation Ratio for Capacitated Vehicle Routing
Jannis Blauth, Vera Traub, Jens Vygen
We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for th…
Approximating the discrete time-cost tradeoff problem with bounded depth
Siad Daboul, Stephan Held, Jens Vygen
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 i…
Approximating maximum integral multiflows on bounded genus graphs
Chien-chung Huang, Mathieu Mari, Claire Mathieu +1
We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with t…
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
Chien-Chung Huang, Mathieu Mari, Claire Mathieu +2
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…