5th workshop of the Center of Modern Computer Science
5. seminář Centra moderní informatiky
The fifth workshop of the Center of Modern Computer Science will take place on Tuesday April 22, 2014 in a meeting room next to refectory on the first floor of Mala Strana building.
Centrum moderní informatiky zve na pátý seminář. Přednášky juniorů centra se konají v průběhu programu v úterý 22. 4. 2014 v malé aule u refektáře v budově MFF UK na Malé Straně.
| 15:00 - 15:45 | Bartosz Walczak: On-line approach to off-line graph coloring problems |
|---|---|
| 15:45 - 16:10 | Robert Šámal: Unique vector coloring |
| 16:10 - 16:35 | Martin Pilát: Evolutionary multi-objective optimization - current challenges |
| 16:35 - 17:10 | Milan Hladík: Convex underestimators in global optimization solving |
Abstracts
Bartosz Walczak: On-line approach to off-line graph coloring problems
The on-line graph coloring problem is modeled by a game between two players: Presenter, who constructs a graph of some fixed class presenting new vertices one by one, and Algorithm, who colors each vertex right after it is presented without the possibility of changing the color afterwards. The goal of Algorithm is to use as few colors as possible, while Presenter tries to force Algorithm to use many colors. Any game of this kind gives rise to a new class of graphs, called game graphs, each of which "encodes" some strategy of Presenter in the game. The chromatic number of such a game graph is equal to the number of colors that Algorithm is forced to use playing against the corresponding strategy. It turns out that game graphs of appropriately defined games can be characterized as intersection graphs of geometric objects. This allows us, for many classes of geometric intersection graphs, to provide lower and upper bounds on their maximum possible chromatic number by analyzing the corresponding on-line coloring games. I will present a survey of results obtained with this method and a detailed example of its application for constructing triangle-free geometric intersection graphs with large chromatic number.
Robert Šámal: Unique vector coloring
Strict vector coloring is one formulation of an optimization program for Lovász theta function: assign vectors to vertices so that adjacent vertices obtain vectors with large angle in-between. We study when this assignment is unique. We find analog of a classical result on uniqueness of coloring of graph products and generalize it. We use recent result of Laurent and Varvitsiotis on universal rigidity, and ad-hoc exploration of properties of eigenspaces of Kneser graphs. In the process we prove product conjecture for vector coloring and also the fact, that the fraction between strict and nonstrict vector coloring can be arbitrary large.
Martin Pilát: Evolutionary multi-objective optimization - current challenges
In the talk we introduce the main ideas of evolutionary multi-objective optimization. We will discuss the advantages and disadvantages of this approach compared to classical multi-objective optimization methods and show some challenges which multi-objective optimization can provide for different fields. For example, one of the most important indicators used in multi-objective optimization is the hypervolume indicator. The computation of this indicator is a #P-hard problem from computational geometry (it is a special case of the Klee's measure problem). Furthermore, multi-objective evolutionary algorithms often require large number of objective function evaluations. This limits their usefulness for solving real-life complex tasks with difficult objective functions. One of the ways to somehow reduce this problem uses ideas from machine learning and regression analysis.
