Rico Zenklusen

Laura Vargas Koch

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness.

[BibT_eX]

[DOI]

J. ACM, August, 2023

Ghost Value Augmentation for k-ECSS and k-ECSM.

[BibT_eX]

[DOI]

D. Ellis Hershkowitz

Nathan Klein

CoRR, 2023

Advances on Strictly Δ-Modular IPs.

[BibT_eX]

[DOI]

CoRR, 2023

A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information.

[BibT_eX]

[DOI]

Richard Santiago

Ivan Sergeev

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

A Simple Combinatorial Algorithm for Robust Matroid Center.

[BibT_eX]

[DOI]

Georg Anegg

Laura Vargas Koch

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid.

[BibT_eX]

[DOI]

Richard Santiago

Ivan Sergeev

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Advances on Strictly $\varDelta $-Modular IPs.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

2022

Reducing Path TSP to TSP.

[BibT_eX]

[DOI]

Jens Vygen

SIAM J. Comput., June, 2022

A Framework for the Secretary Problem on the Intersection of Matroids.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint.

[BibT_eX]

[DOI]

Simon Bruggmann

Math. Program., 2022

A technique for obtaining true approximations for k-center with covering constraints.

[BibT_eX]

[DOI]

Math. Program., 2022

Better-Than-4/3-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation.

[BibT_eX]

[DOI]

Federica Cecchetto

CoRR, 2022

Local Search for Weighted Tree Augmentation and Steiner Tree.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Congruency-Constrained TU Problems Beyond the Bimodular Case.

[BibT_eX]

[DOI]

Richard Santiago

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Fair and Fast k-Center Clustering for Data Summarization.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Streaming Submodular Maximization Under Matroid Constraints.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Submodular Maximization Subject to Matroid Intersection on the Fly.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Techniques for Generalized Colorful k-Center Problems.

[BibT_eX]

[DOI]

Georg Anegg

Laura Vargas Koch

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Online Contention Resolution Schemes with Applications to Bayesian Selection Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Streaming Submodular Maximization with Matroid and Matching Constraints.

[BibT_eX]

[DOI]

CoRR, 2021

Bridging the gap between tree and connectivity augmentation: unified and stronger approaches.

[BibT_eX]

[DOI]

Federica Cecchetto

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture.

[BibT_eX]

[DOI]

Georg Anegg

Haris Angelidakis

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

A Better-Than-2 Approximation for Weighted Tree Augmentation.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

A new contraction technique with applications to congruency-constrained cuts.

[BibT_eX]

[DOI]

Math. Program., 2020

Approximate multi-matroid intersection via iterative refinement.

[BibT_eX]

[DOI]

Math. Program., 2020

2019

Firefighting on Trees Beyond Integrality Gaps.

[BibT_eX]

[DOI]

David Adjiashvili

Andrea Baggio

ACM Trans. Algorithms, 2019

An Improved Analysis of Local Search for Max-Sum Diversification.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Math. Oper. Res., 2019

Submodular Maximization Through the Lens of Linear Programming.

[BibT_eX]

[DOI]

Simon Bruggmann

Math. Oper. Res., 2019

Submodular Minimization Under Congruency Constraints.

[BibT_eX]

[DOI]

Benny Sudakov

Comb., 2019

A 1.5-Approximation for Path TSP.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants.

[BibT_eX]

[DOI]

Christoph Glanzer

Robert Weismantel

SIAM J. Discret. Math., 2018

Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem.

[BibT_eX]

[DOI]

Robert Hildebrand

SIAM J. Discret. Math., 2018

The Submodular Secretary Problem Goes Linear.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

k-Trails: recognition, complexity, and approximations.

[BibT_eX]

[DOI]

Mohit Singh

Math. Program., 2018

Chain-constrained spanning trees.

[BibT_eX]

[DOI]

Neil Olver

Math. Program., 2018

Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix.

[BibT_eX]

[DOI]

Math. Program., 2018

A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem.

[BibT_eX]

[DOI]

Math. Oper. Res., 2018

Improved approximation for tree augmentation: saving by rewiring.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Christos Kalaitzis

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting.

[BibT_eX]

[DOI]

Stefan Weltge

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Hardness and approximation for network flow interdiction.

[BibT_eX]

[DOI]

Networks, 2017

Matroids Are Immune to Braess' Paradox.

[BibT_eX]

[DOI]

Math. Oper. Res., 2017

Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives.

[BibT_eX]

[DOI]

Math. Oper. Res., 2017

Extension complexities of Cartesian products involving a pyramid.

[BibT_eX]

[DOI]

Hans Raj Tiwary

Stefan Weltge

Inf. Process. Lett., 2017

A strongly polynomial algorithm for bimodular integer linear programming.

[BibT_eX]

[DOI]

Stephan Artmann

Robert Weismantel

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations.

[BibT_eX]

[DOI]

Robert Hildebrand

Robert Weismantel

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Local Search for Max-Sum Diversification.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Refuting a conjecture of Goemans on bounded degree spanning trees.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2016

Online Contention Resolution Schemes.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Max-Sum Diversity Via Convex Programming.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Congestion games viewed from M-convexity.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2015

Bulk-Robust combinatorial optimization.

[BibT_eX]

[DOI]

David Adjiashvili

Sebastian Stiller

Math. Program., 2015

Approximate dynamic programming for stochastic linear control problems on compact state spaces.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., 2015

An O(1)-Approximation for Minimum Spanning Tree Interdiction.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes.

[BibT_eX]

[DOI]

Chandra Chekuri

Jan Vondrák

SIAM J. Comput., 2014

Connectivity interdiction.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2014

New approaches to multi-objective optimization.

[BibT_eX]

[DOI]

Math. Program., 2014

A Simple Order-Oblivious O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem.

[BibT_eX]

[DOI]

CoRR, 2014

Time-Expanded Packings.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Stable Routing and Unique-Max Coloring on Trees.

[BibT_eX]

[DOI]

Nicolai Hähnle

Laura Sanità

SIAM J. Discret. Math., 2013

Network design with a discrete set of traffic matrices.

[BibT_eX]

[DOI]

Gianpaolo Oriolo

Laura Sanità

Oper. Res. Lett., 2013

An adaptive routing approach for personal rapid transit.

[BibT_eX]

[DOI]

Kaspar Schüpbach

Math. Methods Oper. Res., 2013

Advances on Matroid Secretary Problems: Free Order Model and Laminar Case.

[BibT_eX]

[DOI]

Patrick Jaillet

José A. Soto

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

2012

A flow model based on polylinking system.

[BibT_eX]

[DOI]

Michel X. Goemans

Satoru Iwata

Math. Program., 2012

A note on chromatic properties of threshold graphs.

[BibT_eX]

[DOI]

Bernard Ries

Dominique de Werra

Discret. Math., 2012

Bisections above Tight Lower Bounds.

[BibT_eX]

[DOI]

Matthias Mnich

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Matroids and integrality gaps for hypergraphic steiner tree relaxations.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Matroidal degree-bounded minimum spanning trees.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

A New Resource-Constrained Multicommodity Flow Model for Conflict-Free Train Routing and Scheduling.

[BibT_eX]

[DOI]

Transp. Sci., 2011

High-confidence estimation of small s-t reliabilities in directed acyclic networks.

[BibT_eX]

[DOI]

Marco Laumanns

Networks, 2011

A 2-approximation for the maximum satisfying bisection problem.

[BibT_eX]

[DOI]

Bernard Ries

Eur. J. Oper. Res., 2011

Stochastic convergence of random search methods to fixed size Pareto front approximations.

[BibT_eX]

[DOI]

Marco Laumanns

Eur. J. Oper. Res., 2011

An s-t connection problem with adaptability.

[BibT_eX]

[DOI]

David Adjiashvili

Discret. Appl. Math., 2011

Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding.

[BibT_eX]

[DOI]

Chandra Chekuri

Jan Vondrák

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Approximation Algorithms for Conflict-Free Vehicle Routing.

[BibT_eX]

[DOI]

Kaspar Schüpbach

Proceedings of the Algorithms - ESA 2011, 2011

2010

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid.

[BibT_eX]

[DOI]

Marie-Christine Costa

Discret. Math., 2010

Matching interdiction.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2010

Network flow interdiction on planar graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2010

Optimization with More than One Budget

[BibT_eX]

[DOI]

Fabrizio Grandoni

CoRR, 2010

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures.

[BibT_eX]

[DOI]

Chandra Chekuri

Jan Vondrák

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Approximation Schemes for Multi-Budgeted Independence Systems.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Proceedings of the Algorithms, 2010

2009

A tight bound on the collection of edges in MSTs of induced subgraphs.

[BibT_eX]

[DOI]

Gregory B. Sorkin

Angelika Steger

J. Comb. Theory, Ser. B, 2009

Repair strategies for minimising the risk of cascading failures in electricity networks.

[BibT_eX]

[DOI]

Int. J. Crit. Infrastructures, 2009

Blockers and transversals.

[BibT_eX]

[DOI]

Marie-Christine Costa

Cédric Bentz

Discret. Math., 2009

An algorithmic framework for wireless information flow.

[BibT_eX]

[DOI]

Michel X. Goemans

Satoru Iwata

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008

Extensions to Network Flow Interdiction on Planar Graphs

[BibT_eX]

[DOI]

CoRR, 2008

2007

Estimation of Small s-t Reliabilities in Acyclic Networks

[BibT_eX]

[DOI]

Marco Laumanns