research
∙
08/04/2023
Single-Source Unsplittable Flows in Planar Graphs
The single-source unsplittable flow (SSUF) problem asks to send flow fro...
share
research
∙
05/09/2023
Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid
The Matroid Secretary Conjecture is a notorious open problem in online o...
research
∙
02/14/2023
Advances on Strictly Δ-Modular IPs
There has been significant work recently on integer programs (IPs) min{c...
research
∙
01/23/2023
A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
Short spanning trees subject to additional constraints are important bui...
research
∙
11/28/2022
Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information
Random order online contention resolution schemes (ROCRS) are structured...
research
∙
11/07/2022
A Simple Combinatorial Algorithm for Robust Matroid Center
Recent progress on robust clustering led to constant-factor approximatio...
research
∙
09/16/2022
A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation
Connectivity augmentation problems are among the most elementary questio...
research
∙
07/06/2022
Techniques for Generalized Colorful k-Center Problems
Fair clustering enjoyed a surge of interest recently. One appealing way ...
research
∙
04/14/2022
Better-Than-4/3-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation
The Connectivity Augmentation Problem (CAP) together with a well-known s...
research
∙
04/11/2022
Submodular Maximization Subject to Matroid Intersection on the Fly
Despite a surge of interest in submodular maximization in the data strea...
research
∙
09/07/2021
Congruency-Constrained TU Problems Beyond the Bimodular Case
A long-standing open question in Integer Programming is whether integer ...
research
∙
07/15/2021
Local Search for Weighted Tree Augmentation and Steiner Tree
We present a technique that allows for improving on some relative greedy...
research
∙
07/15/2021
Streaming Submodular Maximization with Matroid and Matching Constraints
Recent progress in (semi-)streaming algorithms for monotone submodular f...
research
∙
04/14/2021
A Better-Than-2 Approximation for Weighted Tree Augmentation
We present an approximation algorithm for Weighted Tree Augmentation wit...
research
∙
11/30/2020
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches
We consider the Connectivity Augmentation Problem (CAP), a classical pro...
research
∙
09/01/2020
Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture
A well-known conjecture of Füredi, Kahn, and Seymour (1993) on non-unifo...
research
∙
07/08/2020
A Technique for Obtaining True Approximations for k-Center with Covering Constraints
There has been a recent surge of interest in incorporating fairness aspe...
research
∙
03/30/2020
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
We consider the classical problem of maximizing a monotone submodular fu...
research
∙
07/24/2019
Reducing Path TSP to TSP
We present a black-box reduction from the path version of the Traveling ...
research
∙
05/21/2019
An Optimal Monotone Contention Resolution Scheme for Bipartite Matchings via a Polyhedral Viewpoint
Relaxation and rounding approaches became a standard and extremely versa...
research
∙
11/22/2018
Approximate Multi-Matroid Intersection via Iterative Refinement
We introduce a new iterative rounding technique to round a point in a ma...
research
∙
05/10/2018
A 1.5-Approximation for Path TSP
We present a 1.5-approximation for the Metric Path Traveling Salesman Pr...
research
∙
04/06/2018
Improved Approximation for Tree Augmentation: Saving by Rewiring
The Tree Augmentation Problem (TAP) is a fundamental network design prob...
research
∙
12/06/2017
Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting
Mixed-integer mathematical programs are among the most commonly used mod...
research
∙
11/30/2017
