Publications and work in progress

Preprints and work in progress

  • A 2-Approximation for the Maximum Satisfying Bisection Problem
    (with Bernard Ries)
    Submitted.
  • Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding
    (with Chandra Chekuri and Jan Vondrák)
    Submitted.
  • Stable Routing and Unique-max Coloring on Trees
    (with Nicolai Hähnle and Laura Sanità)
    Submitted.
  • A Shortest Path Problem with Adaptability
    (with David Adjiashvili)
    Submitted.
  • 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)
    Submitted.
  • A Flow Model Based on Polylinking Systems
    (with Michel Goemans and Satoru Iwata)
    Submitted.

Accepted for publication

  • Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
    (with Chandra Chekuri and Jan Vondrák)
    Accepted to FOCS 2010.
  • Optimization with More than One Budget
    (with Fabrizio Grandoni)
    Accepted to ESA 2010.
  • High-Confidence Estimation of Small s-t Reliabilities in Acyclic Networks
    (with Marco Laumanns)
    To appear in Networks.

2010

  • Matching Interdiction
    Discrete Applied Mathematics, 158: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)
    To appear in Proceedings of the 25th Mini-EURO Conference on Uncertainty and Robustness in Planning and Decision Making (URPDM), 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)
    Proceedings of Operations Research, Augsburg, Germany, September 3-5, 2008.
  • A Simple Proof for a Characterization of Sign-Central Signature Matrices using Linear Duality
    Proceedings of Operations Research, Augsburg, Germany, September 3-5, 2008.

2007

  • Monte-Carlo Estimation of s-t Reliability in Acyclic Networks
    (with Marco Laumanns)
    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 [pdf]
    PhD Thesis, No 18109, ETH Zurich 2008.
  • Solving and Approximating Large Scale 3D Reconstruction Problems by Minimum s-t Cuts [pdf, poster jpg (small)]
    Master thesis, EPFL Lausanne, 2005.