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.
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
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.
The Industry Day starts on Thursday, August 4, after lunch where practitioners from the industry will highlight various applications of Combinatorial Optimization.
Best Talk Award
Shortly before the end of the FRICO, the best talk is elected by the participants and awarded.
Some social events are planned and there is time for social activities after sessions are finished each day (about 5pm).
On Monday, August 1, before the FRICO there will be a welcome dinner to get to know each other.