Rico Zenklusen - Publications

Publications

2018

Improved Approximation for Tree Augmentation: Saving by Rewiring
(with Fabrizio Grandoni and Christos Kalaitzis)
In: Proceedings of the 50th ACM Symposium on Theory of Computing (STOC), 2018.
Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting
(with Alfonso Cevallos and Stefan Weltge)
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 788-807, 2018.
Submodular Minimization Under Congruency Constraints
(with Martin Nägele and Benny Sudakov)
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 849-866, 2018.
A Framework for the Secretary Problem on the Intersection of Matroids
(with Moran Feldman and Ola Svensson)
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 735-752, 2018.
The Submodular Secretary Problem Goes Linear
(with Moran Feldman)
SIAM Journal on Computing, 47(2):330-366, 2018. Long version of a FOCS 2015 paper.
A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
(with Moran Feldman and Ola Svensson)
Mathematics of Operations Research 43(2):638-650, 2018. Long version of a SODA 2015 paper.
Chain-Constrained Spanning Trees
(with Neil Olver)
Mathematical Programming, Series B, 167(2):293-314, 2018. Long version of an IPCO 2013 paper.
Mixed Integer Formulations of Integer Programs and the Affine Tu-dimension of a Matrix
(with Jörg Bader, Robert Hildebrand, and Robert Weismantel)
Mathematical Programming, Series A, 169(2):565-584, 2018.
Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem
(with Steve Chestnut and Robert Hildebrand)
SIAM Journal on Discrete Mathematics, 32(1):352-371, 2018.

2017

A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming
(with Stephan Artmann and Robert Weismantel)
In: Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), 1206-1219, 2017.
Firefighting on Trees Beyond Integrality Gaps
(with David Adjiashvili and Andrea Baggio)
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2364-2383, 2017.
Local Search for Max-Sum Diversification
(with Alfonso Cevallos and Fritz Eisenbrand)
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 130-142, 2017.
Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations
(with Robert Hildebrand and Robert Weismantel)
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2342-2350, 2017.
Interdicting Structured Combinatorial Optimization Problems with 0,1-Objectives
(with Steve Chestnut)
Mathematics of Operations Research, 42(1):144-166, 2017.
Matroids are Immune to Braess' Paradox
(with Satoru Fujishige, Michel Goemans, Tobias Harks, and Britta Peis)
Mathematics of Operations Research, 42(3):745-761, 2017.
Hardness and Approximation for Network Flow Interdiction
(with Steve Chestnut)
Networks, 69(4):378-387, 2017.
Extension complexities of Cartesian products involving a pyramid
(with Hans Tiwary and Stefan Weltge)
Information Processing Letters, 128:11-13, 2017.

2016

Online Contention Resolution Schemes
(with Moran Feldman and Ola Svensson)
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 1014-1033, 2016.
Max-Sum Diversity via Convex Programming
(with Alfonso Cevallos and Eisenbrand Friedrich)
In: Proceedings of the 32nd International Symposium on Computational Geometry (SoCG), 26:1-26:14, 2016.
k-Trails: Recognition, Complexity, and Approximations
(with Mohit Singh)
In: Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO), 114-125, 2016.
Refuting a Conjecture of Goemans on Bounded Degree Spanning Trees
(with Steve Chestnut and Martin Nägele)
Operations Research Letters, 44(6):766-771, 2016.

2015

An O(1)-Approximation for Minimum Spanning Tree Interdiction
In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 709-728, 2015.
The Submodular Secretary Problem Goes Linear
(with Moran Feldman)
In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 486-505, 2015.
A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
(with Moran Feldman and Ola Svensson)
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 1189-1201, 2015.
Bulk-Robust Combinatorial Optimization
(with David Adjiashvili and Sebastian Stiller)
Mathematical Programming, Series A, 149(1-2):361-339, 2015.
Congestion Games Viewed from M-Convexity
(with Satoru Fujishige, Michel Goemans, Tobias Harks and Britta Peis)
Operations Research Letters, 43(3):329-333, 2015.
Approximate Dynamic Programming for Stochastic Linear Control Problems on Compact State Spaces
(with Stefan Wörner, Marco Laumanns, and Apostolos Fertis)
European Journal on Operational Research, 241:85-98, 2015.

2014

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
(with Chandra Chekuri and Jan Vondrák)
SIAM Journal on Computing, 43(6):1831-1879, 2014. Long version of a STOC 2011 paper.
New Approaches to Multi-Objective Optimization
(with Fabrizio Grandoni, R. Ravi, and Mohit Singh)
Mathematical Programming, Series A, 146(1):525-554, 2014.
Time-Expanded Packings
(with David Adjiashvili, Sandro Bosio, and Robert Weismantel)
In: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, Track A (ICALP 2014), 64-76, 2014.
Connectivity Interdiction
Operations Research Letters, 42(6-7):450-454, 2014.

2013

Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
(with Patrick Jaillet and José Soto)
In: Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO), 254-265, 2013.
Chain-Constrained Spanning Trees
(with Neil Olver)
In: Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO), 324-335, 2013.
Stable Routing and Unique-Max Coloring on Trees
(with Nicolai Hähnle and Laura Sanità)
SIAM Journal on Discrete Mathematics, 27(1):109-125, 2013.
Network Design with a Discrete Set of Traffic Matrices
(with Gianpaolo Oriolo and Laura Sanità)
Operations Research Letters, 41(4):390-396, 2013.
An Adaptive Routing Approach for Personal Rapid Transit
(with Kaspar Schüpbach)
Mathematical Methods of Operations Research, 77(3):371-380, 2013.

2012

A Flow Model Based on Polylinking Systems
(with Michel Goemans and Satoru Iwata)
Mathematical Programming, Series A, 135(1-2):1-23, October 2012.
Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations
(with Michel Goemans, Neil Olver, and Thomas Rothvoß)
In: Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), 1161-1175, 2012.
Matroidal Degree-Bounded Minimum Spanning Trees
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 1512-1521, 2012.
Bisections Above Tight Lower Bounds
(with Matthias Mnich)
Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2012.
A Note on Chromatic Properties of Threshold Graphs
(with Bernard Ries and Dominique de Werra)
Discrete Mathematics, 312:1838-1843, 2012.

2011

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
(with Chandra Chekuri and Jan Vondrák)
In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), 783-792, 2011.
Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding
(with Chandra Chekuri and Jan Vondrák)
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 1080-1097, 2011.
Approximation Algorithms for Conflict-Free Vehicle Routing
(with Kaspar Schüpbach)
In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA), 640-651, 2011.
A New Resource-constrained Multi-commodity Flow Model for Conflict-free Train Routing and Scheduling
(with Gabrio Caimi, Fabian Chudak, Martin Fuchsberger, and Marco Laumanns)
Transportation Science, 45(2):212-227, 2011.
High-Confidence Estimation of Small s-t Reliabilities in Acyclic Networks
(with Marco Laumanns)
Networks, 57(4):376-388, 2011.
A 2-Approximation for the Maximum Satisfying Bisection Problem
(with Bernard Ries)
European Journal of Operational Research, 210(2):169-175, 2011.
Stochastic Convergence of Random Search Methods to Fixed Size Pareto Front Approximations
(with Marco Laumanns)
European Journal of Operational Research, 213(2):414-421, 2011.
An s-t Connection Problem with Adaptability
(with David Adjiashvili)
Discrete Applied Mathematics, 159(8):695-705, 2011.

2010

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
(with Chandra Chekuri and Jan Vondrák)
In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 575-584, 2010.
Approximation Schemes for Multi-Budgeted Independence Systems
(with Fabrizio Grandoni)
In: Proceedings of the 18th Annual European Symposium on Algorithms (ESA), 536-548, 2010.
Matching Interdiction
Discrete Applied Mathematics, 158(15):1676-1690, 2010.
Network Flow Interdiction on Planar Graphs
Discrete Applied Mathematics, 158(13):1441-1455, 2010.
Blockers and Transversals in Some Subclasses of Bipartite Graphs
(with Cédric Bentz, Marie-Christine Costa, Christophe Picouleau, Bernard Ries, and Dominique de Werra)
Discrete Mathematics, 310(1):132-146, 2010.
Robust Adaptive Resource Allocation in Container Terminals
(with Maarten Hendriks, Marco Laumanns, Erjen Lefeber, Kaspar Schüpbach, and Jan Tijmen Udding)
In: Proceedings of the 25th Mini-EURO Conference on Uncertainty and Robustness in Planning and Decision Making (URPDM), 2010.
Approximate Parametric Dynamic Programming in Inventory Management
(with Stefan Wörner, Marco Laumanns, Eleni Pratsini, and Apostolos Fertis)
In: Proceedings of the Annual Conference of the INFORMS Manufacturing and Service Operations Management Society (MSOM), 2010.

2009

An Algorithmic Framework for Wireless Information Flow
(with Michel Goemans and Satoru Iwata)
Forty-Seventh Annual Allerton Conference on Communication, Control, and Computing, Urbana-Champaign, USA, September 30-October 2, 2009.
Computational Complexity of Impact Size Estimation for Spreading Processes on Networks
(with Marco Laumanns)
European Physics Journal, Series B, 71(4):481-487, 2009.
Blockers and Transversals
(with Cédric Bentz, Marie-Christine Costa, Christophe Picouleau, Bernard Ries, and Dominique de Werra)
Discrete Mathematics, 309(13):4306-4314, 2009.
A Tight Bound on the Collection of Edges in MSTs of Induced Subgraphs
(with Gregory Sorkin and Angelika Steger)
Journal of Combinatorial Theory, Series B, 99:428-435, 2009.
Repair Strategies for Minimizing the Risk of Cascading Failures in Electricity Networks
(with Christian Balderer, Michael Guarisco, and Marco Laumanns)
International Journal on Critical Infrastructures, 5(1/2):51-71, 2009.

2008

Computational Complexity of High-Confidence Estimation of Large Spreadings and Expected Spreading Sizes in Agent-Based Spreading Models
(with Marco Laumanns)
In: Proceedings of Operations Research, Augsburg, Germany, September 3-5, 2008.
A Simple Proof for a Characterization of Sign-Central Signature Matrices using Linear Duality
In: Proceedings of Operations Research, Augsburg, Germany, September 3-5, 2008.

2007

Monte-Carlo Estimation of s-t Reliability in Acyclic Networks
(with Marco Laumanns)
In: Proceedings of the European Conference on Complex Systems (ECCS 2007), Dresden, Germany, October 1-5, 2007.

Doctoral Dissertation and Master's Thesis

Combinatorial Methods for Analyzing Network Security and Reliability
PhD Thesis, No 18109, ETH Zurich 2008.
Solving and Approximating Large Scale 3D Reconstruction Problems by Minimum s-t Cuts
Master's Thesis, EPFL Lausanne, 2005.