Zobrazeno 1 - 10
of 69
pro vyhledávání: '"TRAUB, VERA"'
The Steiner tree problem is one of the most prominent problems in network design. Given an edge-weighted undirected graph and a subset of the vertices, called terminals, the task is to compute a minimum-weight tree containing all terminals (and possi
Externí odkaz:
http://arxiv.org/abs/2407.19905
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
The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to different terminals with unrelated demands, each terminal being served through a single path. One of the most heavily studied SSUF objectives is to minimize
Externí odkaz:
http://arxiv.org/abs/2308.02651
Autor:
Traub, Vera, Zenklusen, Rico
Connectivity augmentation problems are among the most elementary questions in Network Design. Many of these problems admit natural $2$-approximation algorithms, often through various classic techniques, whereas it remains open whether approximation f
Externí odkaz:
http://arxiv.org/abs/2209.07860
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
The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximati
Externí odkaz:
http://arxiv.org/abs/2204.06944
The basic goal of survivable network design is to build cheap networks that guarantee the connectivity of certain pairs of nodes despite the failure of a few edges or nodes. A celebrated result by Jain [Combinatorica'01] provides a 2-approximation fo
Externí odkaz:
http://arxiv.org/abs/2112.11799
Autor:
Blauth, Jannis, Held, Stephan, Müller, Dirk, Schlomberg, Niklas, Traub, Vera, Tröbst, Thorben, Vygen, Jens
Publikováno v:
In Discrete Optimization August 2024 53
Autor:
Traub, Vera, Zenklusen, Rico
We present a technique that allows for improving on some relative greedy procedures by well-chosen (non-oblivious) local search algorithms. Relative greedy procedures are a particular type of greedy algorithm that start with a simple, though weak, so
Externí odkaz:
http://arxiv.org/abs/2107.07403
Autor:
Traub, Vera, Zenklusen, Rico
We present an approximation algorithm for Weighted Tree Augmentation with approximation factor $1+\ln 2 + \varepsilon < 1.7$. This is the first algorithm beating the longstanding factor of $2$, which can be achieved through many standard techniques.
Externí odkaz:
http://arxiv.org/abs/2104.07114