Publications
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.
- Chain-Constrained Spanning Trees
(with Neil Olver)
Mathematical Programming, Series B, 167(2):293-314, 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.