Zobrazeno 1 - 10
of 294
pro vyhledávání: '"P. Vygen"'
We consider cost allocation for set covering problems. We allocate as much cost to the elements (players) as possible without violating the group rationality condition (no subset of players pays more than covering this subset would cost), and so that
Externí odkaz:
http://arxiv.org/abs/2401.04040
We revisit the a priori TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the a priori TSP, we are given a metric space $(V,c)$ and an activation probability $p(v)$ for each customer $v\in V$
Externí odkaz:
http://arxiv.org/abs/2309.10663
We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here disjoint can mean vertex-disjoint or edge-disjoint, and the graph can be
Externí odkaz:
http://arxiv.org/abs/2207.00450
Autor:
Blauth, Jannis, Held, Stephan, Müller, Dirk, Schlomberg, Niklas, Traub, Vera, Tröbst, Thorben, Vygen, Jens
We develop theoretical foundations and practical algorithms for vehicle routing with time-dependent travel times. We also provide new benchmark instances and experimental results. First, we study basic operations on piecewise linear arrival time func
Externí odkaz:
http://arxiv.org/abs/2205.00889
Publikováno v:
Mathematical Programming (2023)
We develop new algorithmic techniques for VLSI detailed routing. First, we improve the goal-oriented version of Dijkstra's algorithm to find shortest paths in huge incomplete grid graphs with edge costs depending on the direction and the layer, and p
Externí odkaz:
http://arxiv.org/abs/2111.06169
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
Externí odkaz:
http://arxiv.org/abs/1907.10376
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 the unit-demand case and the splittable variant. Our results hold in arb
Externí odkaz:
http://arxiv.org/abs/2011.05235
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:
http://arxiv.org/abs/2011.02446
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 the demand edges can be embedded on an orientable surface of bounded ge
Externí odkaz:
http://arxiv.org/abs/2005.00575
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 to packing cuts in a plan
Externí odkaz:
http://arxiv.org/abs/2001.01715