68 citations · 142 across the 43 of their papers we have counts for
4 papers · 1 filter
Congruency-Constrained TU Problems Beyond the Bimodular Case
Martin Nägele, Richard Santiago, Rico Zenklusen
A long-standing open question in Integer Programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important specia…
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…