68 citations · 142 across the 43 of their papers we have counts for
43 papers · 1 filter
Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases
Chandra Chekuri, Lars Rohwedder, Neta Singer +2
Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function over m…
Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
Lars Rohwedder, Rico Zenklusen
Finding policies for Markov Decision Processes (MDPs) is a central problem in areas such as Reinforcement Learning and Operations Research. Here, we have to repeatedly choose an ac…
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…
Ghost Value Augmentation for -Edge-Connectivity
D Ellis Hershkowitz, Nathan Klein, Rico Zenklusen
We give a poly-time algorithm for the -edge-connected spanning subgraph (-ECSS) problem that returns a solution of cost no greater than the cheapest -ECSS on the same…
Single-Source Unsplittable Flows in Planar Graphs
Vera Traub, Laura Vargas Koch, Rico Zenklusen
The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to different terminals with unrelated demands, each terminal being served through a single…
Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid
Richard Santiago, Ivan Sergeev, Rico Zenklusen
The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an -competitive algorithm for the Matroid Secretary Problem (M…
Advances on Strictly -Modular IPs
Martin Nägele, Christian Nöbel, Richard Santiago +1
There has been significant work recently on integer programs (IPs) with a constraint marix with bounded subdeterminants.…
A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
Martin Nägele, Rico Zenklusen
Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms. Especially in the context of the Traveling Salesman Proble…
A Simple Combinatorial Algorithm for Robust Matroid Center
Georg Anegg, Laura Vargas Koch, Rico Zenklusen
Recent progress on robust clustering led to constant-factor approximations for Robust Matroid Center. After a first combinatorial -approximation that is based on a matroid inter…
A -Approximation Algorithm for Weighted Connectivity Augmentation
Vera Traub, Rico Zenklusen
Connectivity augmentation problems are among the most elementary questions in Network Design. Many of these problems admit natural -approximation algorithms, often through vario…
Techniques for Generalized Colorful -Center Problems
Georg Anegg, Laura Vargas Koch, Rico Zenklusen
Fair clustering enjoyed a surge of interest recently. One appealing way of integrating fairness aspects into classical clustering problems is by introducing multiple covering const…
Better-Than--Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation
Federica Cecchetto, Vera Traub, 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 pro…
Submodular Maximization Subject to Matroid Intersection on the Fly
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson +1
Despite a surge of interest in submodular maximization in the data stream model, there remain significant gaps in our knowledge about what can be achieved in this setting, especial…
Local Search for Weighted Tree Augmentation and Steiner Tree
Vera Traub, Rico Zenklusen
We present a technique that allows for improving on some relative greedy procedures by well-chosen (non-oblivious) local search algorithms. Relative greedy procedures are a particu…
Streaming Submodular Maximization under Matroid Constraints
Moran Feldman, Paul Liu, Ashkan Norouzi-Fard +2
Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniqu…
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 . This is the first algorithm beating the longstanding f…
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches
Federica Cecchetto, Vera Traub, Rico Zenklusen
We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by on…
Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture
Georg Anegg, Haris Angelidakis, Rico Zenklusen
A well-known conjecture of Füredi, Kahn, and Seymour (1993) on non-uniform hypergraph matching states that for any hypergraph with edge weights , there exists a matching suc…
A Technique for Obtaining True Approximations for -Center with Covering Constraints
Georg Anegg, Haris Angelidakis, Adam Kurpisz +1
There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the -Center problem in this s…
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson +1
We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studi…