4th Colloquium of Research Area KL

Date: October 10, 2014
Venue:  Seminar room 1st floor, Arithmeum, Lennéstr. 2, Bonn


15:45 Coffee and Tee (Lounge 2nd floor, Arithmeum, Lennéstr. 2)
16:15 Marek Karpinski: Approximation of fragile optimization problems
17:00 Coffee break
17:30 Nicolai Hähnle: Short paths in polyhedral graphs
  After the Colloquium there will be the opportunity to have dinner together


Marek Karpinski: Approximation of fragile optimization problems

We introduce a new method for designing efficient approximation schemes for the class of fragile dense minimization and ranking problems and some extensions thereof. As an application of this method we construct also the best up to now subexponential deterministic exact algorithms for those problems, in particular, an almost optimal algorithm (under the ETH hypothesis) for the problem of Feedback Arc Set Tournament (FAST) which complexity status was open for some time now.  (Joint work with W. Schudy)

Nicolai Hähnle: Short paths in polyhedral graphs

The Simplex method solves linear optimization problems by performing a walk on the graph given by the 1-skeleton of the polyhedron of feasible solutions. Despite the negative results about its theoretical worst-case running time, it remains one of the algorithms of choice for applications (next to interior point methods) due to its performance in practice. How far can we close this gap between theory and practice? There are two parts to this question: We ask whether short paths in the graph of polyhedra exist at all; and we ask whether such paths can be found by an efficient algorithm. I will recall some important results (occasionally with surprisingly simple proofs) from the history of these question. Then I will focus on polyhedra with wide normal cones, which naturally occur in combinatorial optimization problems. For such polyhedra, polynomial upper bounds on the lengths of paths have recently been found using a variety of interesting techniques (results are due to Brunsch and
Röglin; and in joint work with Bonifas, Di Summa, Eisenbrand, and Niemeier, and with Dadush).