
A BetterThan2 Approximation for Weighted Tree Augmentation
We present an approximation algorithm for Weighted Tree Augmentation wit...
read it

Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches
We consider the Connectivity Augmentation Problem (CAP), a classical pro...
read it

Simpler and Stronger Approaches for NonUniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture
A wellknown conjecture of Füredi, Kahn, and Seymour (1993) on nonunifo...
read it

A Technique for Obtaining True Approximations for kCenter with Covering Constraints
There has been a recent surge of interest in incorporating fairness aspe...
read it

The Oneway Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
We consider the classical problem of maximizing a monotone submodular fu...
read it

Reducing Path TSP to TSP
We present a blackbox reduction from the path version of the Traveling ...
read it

An Optimal Monotone Contention Resolution Scheme for Bipartite Matchings via a Polyhedral Viewpoint
Relaxation and rounding approaches became a standard and extremely versa...
read it

Approximate MultiMatroid Intersection via Iterative Refinement
We introduce a new iterative rounding technique to round a point in a ma...
read it

A 1.5Approximation for Path TSP
We present a 1.5approximation for the Metric Path Traveling Salesman Pr...
read it

Improved Approximation for Tree Augmentation: Saving by Rewiring
The Tree Augmentation Problem (TAP) is a fundamental network design prob...
read it

Lifting Linear Extension Complexity Bounds to the MixedInteger Setting
Mixedinteger mathematical programs are among the most commonly used mod...
read it

Submodular Maximization through the Lens of Linear Programming
The simplex algorithm for linear programming is based on the fact that a...
read it
Rico Zenklusen
is this you? claim profile