Combinatorial Optimization

Many real world applications are naturally formulated as combinatorial optimization problems, i.e. problems of finding the best solution(s) out of a finite set. Various methods have been developed to tackle such problems: integer programming, fixed-parameter tractable and exact algorithms, approximation algorithms and combinatorial algorithms, among others. D1 works on applying these methods to various problems from different areas, ranging from bioinformatics to geometry, to scheduling, and several others.

Research Area

We work on several fronts:

  • Approximation algorithms:

    One of the most basic methods to deal with NP-hard optimization problems is to design polynomial-time algorithms that find a solution which is provably not far from the optimum. Formally, we say that an algorithm is an x-approximation algorithm for a certain optimization problem, if for any instance of the problem, the algorithm runs in time polynomial in the size of the instance, and outputs a solution whose objective value is within a factor of x times the optimum. Our work spans different areas, including graph problems, scheduling, computational economics, computational geometry, etc.

  • Parameterized algorithms:

    The NP-hardness of optimization problems can often be traced back to the presence of certain structures in the instance. We measure computational complexity with respect to the size of these structures, denoted by a parameter k, and design algorithms that solve such parameterized optimization problems in time f(k) times a polynomial in the input size, for some computable function f, or that sparsify them in polynomial time to have size polynomial in k (so-called polynomial kernelization algorithms). Application areas for our techniques are broad and include graph theory and computational geometry.

  • Combinatorial algorithms:

    Here the aim is to develop combinatorial algorithms that find optimal or near-optimal solutions for combinatorial optimization problems arising in different applications. Examples include: network flow problems, finding stable matchings and cycle bases in graphs, enumerating minimal transversals of hypergraphs, etc.

  • Algorithm Engineering:

    Complementing our theoretical results above, we also work on the development, implementation and experimental evaluation of algorithms for combinatorial optimization problems, arising from real life applications. In particular, we work on problems from bioinformatics, hypergraph transversal enumeration, discrepancy theory, randomized rounding and its applications in a number of combinatorial optimization problems, scheduling and parallel implementations of a number of standard algorithms, such as convex hull algorithms and Quicksort.

Sample Publications

  • A. Adamaszek, A. Wiese. A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices. SODA 2014.
  • A. Anagnostopoulos, F. Grandoni, S. Leonardi, A. Wiese. A Mazing 2+ε Approximation for Unsplittable Flow on a Path. SODA 2014.
  • S. Kratsch, G. Philip, S. Ray. Point Line Cover: The Easy Kernel is Essentially Tight. SODA 2014.
  • A. Adamaszek, A. Wiese. Approximation Schemes for Maximum Weight Independent Set of Rectangles. FOCS 2013.
  • P. Chalermsook, B. Laekhanukit and D. Nanongkai. Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses, FOCS 2013.
  • A. Antoniadis, C.-C. Huang, S. Ott, J. Verschae. How to Pack Your Items When You Have to Buy Your Knapsack, MFCS 2013.
  • M. Pilipczuk, M. Pilipczuk, P. Sankowski, E.J. van Leeuwen. Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs. STACS 2013. pp 353--364.
  • C. Croitoru, T. Kötzing. A normal form for argumentation frameworks. TAFA 2013.
  • A. Karrenbauer, D. Wöll. Blinking Molecule Tracking. SEA 2013, pp 308-319.
  • L. Becchetti, V. Bonifaci, M. Dirnberger, A. Karrenbauer, K. Mehlhorn. Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds. ICALP 2013, pp 472-483.
  • N. Megow and J. Verschae. Dual techniques for scheduling on a machine with varying speed. ICALP 2013, LNCS 7965, pp 745–756.
  • E. Günther, O. Maurer, N. Megow, and A. Wiese. A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio. SODA 2013, pp 118-128.
  • S. Gaspers, M. Mnich. Feedback Vertex Sets in Tournaments. Journal of Graph Theory 72(1), pp. 72-89, 2013.
  • N. Megow, R.H. Möhring, and J. Schulz. Decision Support and Optimization in Shutdown and Turnaround Scheduling. INFORMS Journal on Computing 23(2): 189-204, 2011.
  • D. Hermelin, M. Mnich, E.J. van Leeuwen, G.J. Woeginger. Domination When the Stars Are Out. ICALP 2011, pp 462-473.

Software Projects

    • LEDA - Library of Efficient Data Types and Algorithms

      We contribute modules to LEDA like, e.g., an improved general matching algorithm and a heuristic improvement for the weighted bipartite matching algorithm. The heuristic significantly improves the running time of LEDA's bipartite weighted matching algorithm in practice.