Rico Zenklusen - Publications

Publications and work in progress

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
(with Chandra Chekuri and Jan Vondrák)
Submitted. Long version of a STOC 2011 paper.
Stable Routing and Unique-max Coloring on Trees
(with Nicolai Hähnle and Laura Sanità)
Submitted.
An Adaptive Routing Approach for Personal Rapid Transit
(with Kaspar Schüpbach)
Submitted.
Approximate Parametric Dynamic Programming and Applications in Inventory Management
(with Apostolos Fertis, Marco Laumanns and Stefan Wörner)
Submitted. Long version of a MSOM 2010 paper.
A Note on Chromatic Properties of Threshold Graphs
(with Bernard Ries and Dominique de Werra)
Submitted.

Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations
(with Michel Goemans, Neil Olver and Thomas Rothvoß)
Accepted to the 44th ACM Symposium on Theory of Computing (STOC), 2012.
A Flow Model Based on Polylinking Systems
(with Michel Goemans and Satoru Iwata)
To appear in Mathematical Programming, Series A.

Matroidal Degree-Bounded Minimum Spanning Trees
In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 1512-1521, 2012.

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-288, 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.

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.

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.

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.

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.

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.