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.