Monday, February 7, 2011
(HU) Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room: Humboldt-Kabinett
Lecture - 14:15
Abstract:
The notion of "important separators" and bounding the number of such
separators turned out to be a very useful technique in the design of
fixed-parameter tractable algorithms for multi(way) cut problems. For
example, the recent breakthrough result of Chen et al. on the Directed
Feedback Vertex Set problem can be also explained using this notion. In
my talk, I will overview combinatorial and algorithmic results that can
be obtained by studying such separators.
Colloquium - 16:00
Abstract:
In practical applications of Combinatorial Optimization, one is often confronted with the existence of several different objectives, which usually contradict each other. Consider for example a transportation problem, where one would like to minimize at the same time the transportation cost, the time until all transports are completed, and the CO2 emissions caused by the transports. Obviously, in most cases there won't exist a solution optimizing all objectives at once.
This problem is tackled in the area of Multicriteria Optimization, where the notion of Pareto optimal solutions is introduced. These are solutions that can not be improved in any objective without worsening another. The drawback of this concept is that in general there are too many of them to compute them all. A straight forward approach yielding only one solution is scalarization, where a weighted sum of the different objective functions is minimized. This, however, might lead to very biased solutions, even though good balanced solutions exist.
In this talk, we introduce the concept of Compromise Solutions, which is suitable for finding single balanced solutions, thus avoiding both disadvantages of the above methods. We present some interesting properties of Compromise Solutions, a connection to the approximation of the set of Pareto optimal solutions, as well as some minor results on specific Combinatorial Optimization Problems.