Hauptinhalt

Topinformationen

Timeframe

Begin: 2016-08-02 09:00
End: 2016-08-05 13:30

FRICO 2016: Program

Besides the talks of our participants, there are the following highlights.

Invited Talk

The FRICO 2016 starts Tuesday, August 2,
at 9am with our invited talk by

Prof. Dr. Jens Vygen

Research Institute for Discrete Mathematics
University of Bonn
http://www.or.uni-bonn.de/~vygen/

Invited Talk 1: Approximation Algorithms for Traveling Salesmen

For the famous traveling salesman problem (TSP), Christofides’ 1976 algorithm with approximation ratio 3/2 is still the best we know, and the 4/3 conjecture is still completely open. But recently there has been progress on interesting variants. We will review the state of the art and open problems. In particular, we focus on approximation algorithms for the the s-t-path TSP, in which start and end of the tour are given and not identical.

Invited Talk 2: Resource Sharing, Routing, Chip Design

Chip design is one of the most fascinating application areas of mathematics. One important task is routing. Interconnecting millions of sets of pins by wires is challenging because of the huge instance sizes and limited resources. The graphs can have billions of vertices; moreover, even the simplest special cases of the routing problem are NP-hard. We show how to model the routing problem by min-max resource sharing and present a simple combinatorial fully polynomial approximation scheme which is both faster and more general than all previous algorithms. Using this we compute overall routing solutions that are far superior to those computed by industrial routing tools.

Industry Day

The Industry Day starts on Thursday, August 4, after lunch where practitioners from the industry will highlight various applications of Combinatorial Optimization.