Arrow Research search

Author name cluster

Vera Traub

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
1 author row

Possible papers

11

FOCS Conference 2024 Conference Paper

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller Than 2

  • Jaroslaw Byrka
  • Fabrizio Grandoni 0001
  • Vera Traub

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 possibly further vertices). The best-known approximation algorithms for Steiner tree involve enumeration of a (polynomial but) very large number of candidate components and are therefore slow in practice. A promising ingredient for the design of fast and accurate approximation algorithms for Steiner tree is the bidirected cut relaxation (BCR): bidirect all edges, choose an arbitrary terminal as a root, and enforce that each cut containing some terminal but not the root has one unit of fractional edges leaving it. BCR is known to be integral in the spanning tree case [Edmonds'67], i. e. , when all the vertices are terminals. For general instances, however, it was not even known whether the integrality gap of BCR is better than the integrality gap of the natural undirected relaxation, which is exactly 2. We resolve this question by proving an upper bound of 1. 9988 on the integrality gap of BCR.

Details

FOCS Conference 2021 Conference Paper

A Better-Than-2 Approximation for Weighted Tree Augmentation

  • Vera Traub
  • Rico Zenklusen

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. −

Details

FOCS Conference 2018 Conference Paper

Beating the Integrality Ratio for s-t-Tours in Graphs

  • Vera Traub
  • Jens Vygen

Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomial-time algorithm for the s-t-path graph TSP with approximation ratio 1. 497. Our algorithm can be viewed as a refinement of the 3/2-approximation algorithm by Sebo and Vygen [16], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics).

Details