Vera Traub

Vera Traub

Auto-generated profile, based on publicly available information

Vera Traub

Department of Computer Science, ETH Zurich, Zurich, Switzerland

Research Focus & Metrics

Academic Career Length

7Years (2020-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
9 June 2022
Verified
Conference Paper
Open access
FGFabrizio Grandoni
Fabrizio Grandoni
AAAfrouz Jabal Ameli
Afrouz Jabal Ameli
VTVera Traub
Vera Traub
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 for a wide class of these problems. However nothing better is known even for very basic special cases, raising the natural question whether any improved approximation factor is possible at all. In this paper we address one of the most basic problems in this family for which 2 is still the best-known approximation factor, the Forest Augmentation Problem (FAP): given an undirected unweighted graph (that w.l.o.g. we can assume to be a forest) and a collection of extra edges (links), compute a minimum cardinality subset of links whose addition to the graph makes it 2-edge-connected. Several better-than-2 approximation algorithms are known for the special case where the input graph is a tree, a.k.a. the Tree Augmentation Problem (TAP), see e.g. [Grandoni, Kalaitzis, Zenklusen - STOC'18; Cecchetto, Traub, Zenklusen - STOC'21] and references therein. Recently this was achieved also for the weighted version of TAP [Traub, Zenklusen - FOCS'21], and for the k-connectivity generalization of TAP [Byrka, Grandoni, Jabal-Ameli - STOC'20; Cecchetto, Traub, Zenklusen - STOC'21]. These results heavily exploit the fact that the input graph is connected, a condition that does not hold in FAP. In this paper we breach the 2-approximation barrier for FAP. Our result is based on two main ingredients. First, we describe a reduction to the Path Augmentation Problem (PAP), the special case of FAP where the input graph is a collection of disjoint paths. Our reduction is not approximation preserving, however it is sufficiently accurate to improve on a factor 2 approximation. Second, we present a better-than-2 approximation algorithm for PAP, an open problem on its own. Here we exploit a novel notion of implicit credits which might turn out to be helpful in future related work.

16 March 2025 in Journal of the ACM
Verified
Journal Article
Open access
VTVera Traub
Vera Traub
RZRico Zenklusen
Rico Zenklusen
We present the first approximation algorithms for the Weighted Tree Augmentation Problem (WTAP) that beat the longstanding approximation factor of 2, which can be achieved through standard techniques. The core of our approach is a novel decomposition theorem based on a well-chosen class of thin components . The decomposition theorem asserts that for any pair of a highly structured (but potentially expensive) WTAP solution and a cheaper WTAP solution, there is a way to decompose the cheaper solution into thin components, one of which allows for improving the structured solution. Together with the fact that we can efficiently optimize over thin components through a dynamic program, our decomposition theorem leads to a relative greedy algorithm for WTAP that is a (1 + ln 2 + ϵ)-approximation. Moreover, we present an approach to improve on some relative greedy procedures by well-chosen (non-oblivious) local search algorithms. The main application of this approach leads to a (1.5 + ϵ)-approximation for WTAP. Furthermore, for the Steiner Tree Problem, it provides an alternative way to obtain the currently best known approximation factor of ln 4 + ϵ. Contrary to prior methods, our approach is purely combinatorial without the need to solve an LP. Nevertheless, the solution value can still be bounded in terms of the well-known hypergraphic LP, leading to an alternative, and arguably simpler, way to bound its integrality gap by ln 4.

26 September 2023 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
FCFederica Cecchetto
Federica Cecchetto
VTVera Traub
Vera Traub
RZRico Zenklusen
Rico Zenklusen
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 approximation algorithms with guarantees below 2 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 1.393 through quite sophisticated techniques. We present a new and arguably simple matching-based method for the well-known special case of leaf-to-leaf instances. Combining our work with prior techniques, we readily obtain a $$(4/3+\varepsilon )$$ ( 4 / 3 + ε ) -approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a $$4/3$$ 4 / 3 -guarantee was only known for Leaf-to-Leaf TAP instances on trees of height 2. Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned 1.393-approximation, we can further improve the approximation factor to 1.29, obtaining for the first time a factor below $$\frac{4}{3}$$ 4 3 for a nontrivial class of TAP/CAP instances.

28 August 2024 in Operations Research Letters
Verified
Journal Article
Open access
JBJannis Blauth
Jannis Blauth
AEAntonia Ellerbrock
Antonia Ellerbrock
VTVera Traub
Vera Traub
JVJens Vygen
Jens 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, and so that the excess vector is lexicographically maximized. This happy nucleolus has several nice properties. In particular, we show that it can be computed considering a small subset of “simple” coalitions only. While computing the nucleolus for set covering is NP-hard, our results imply that the happy nucleolus can be computed in polynomial time.

4 June 2025
Verified
Book Chapter
Closed access
PDF file
JBJarosław Byrka
Jarosław Byrka
FGFabrizio Grandoni
Fabrizio Grandoni
VTVera Traub
Vera Traub

14 April 2020
Verified
Book Chapter
Closed access
PDF file
VTVera Traub
Vera Traub
TTThorben Tröbst
Thorben Tröbst