ven. 11 décembre 2015 -- Zsolt Tuza (University of Pannonia)

We introduce and study a very general graph-theoretical decision & optimization problem, which includes many fundamental problems as its subproblems. Some of the notable ones are Chromatic number, Subgraph isomorphism, 3-partition, and Bin packing from which the problem's name has been coined. The algorithmic scenarios include the offline as well ...

ven. 04 décembre 2015 -- Martin Hoefer (Max-Planck Institut für Informatik, Saarbrücken, Germany)

Scarcity of the frequency spectrum is a major problem in wireless networks, but it is often due to the static allocation rules implemented by regulators. From an algorithmic perspective, flexible allocation of spectrum gives rise to a variety of interesting new optimization problems, most prominently variants of independent set and ...

ven. 04 décembre 2015 -- Erik Jan van Leeuwen (Max-Planck Institut für Informatik, Saarbrücken, Germany)

The Independent Set problem is a fundamental and well-studied graph problem, and asks to find a largest set of pairwise nonadjacent vertices of a graph. Although Independent Set is known to be NP-hard or worse for many graph classes, surprisingly, the complexity of Independent Set on graphs that exclude a ...

ven. 16 octobre 2015 -- Patrick Loiseau (EURECOM)

Statistical learning methods developed in the last decades have proved very useful for many applications. However, most algorithms were developed under the assumption that the data is independent from the algorithm. This is no longer true in applications where data is generated or provided by (human) strategic agents. As more ...