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


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.

Milan Hladík: Convex underestimators in global optimization solving

Convex underestimators are used in global optimization to bound the objective function from below and to enclose the feasible set or its part. We focus particularly on the classical alpha-BB method, which constructs an underestimators on the interval domain by incorporating an additional quadratic term. The important step here to achieve convexity of the underestimator is to estimate the eigenvalues of an interval enclosure of the Hessian matrix. This is usually done by the scaled Gerschgorin method. In our talk, we will discuss optimality of the scaling as well as a linear parametric form enclosure of the Hessian matrices.