5 papers
On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
Martin Nägele, Christian Nöbel, Rico Zenklusen
The odd-red bipartite perfect matching problem asks to find a perfect matching containing an odd number of red edges in a given red-blue edge-colored bipartite graph. While this pr…
Approximation Schemes for Planar Graph Connectivity Problems
Meike Neuwohner, Vera Traub, Rico Zenklusen
Finding a smallest subgraph that is k-edge-connected, or augmenting a k-edge-connected graph with a smallest subset of given candidate edges to become (k+1)-edge-connected, are amo…
Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-Uniform k-Center
Jannis Blauth, Christian Nöbel, Rico Zenklusen
One of the most elementary spreading models on graphs can be described by a fire spreading from a burning vertex in discrete time steps. At each step, all neighbors of burning vert…
Unsplittable Cost Flows from Unweighted Error-Bounded Variants
Chaitanya Swamy, Vera Traub, Laura Vargas Koch +1
A famous conjecture of Goemans on single-source unsplittable flows states that one can turn any fractional flow into an unsplittable one of no higher cost, while increasing the loa…
Nearly Tight Sample Complexity for Matroid Online Contention Resolution
Moran Feldman, Ola Svensson, Rico Zenklusen
Due to their numerous applications, in particular in Mechanism Design, Prophet Inequalities have experienced a surge of interest. They describe competitive ratios for basic stoppin…