ven. 12 février 2016 -- Thomas Nowak (LRI)

We introduce a new class of distributed algorithms for the approximate consensus problem in dynamic rooted networks, which we call amortized averaging algorithms. They are deduced from ordinary averaging algorithms by adding a value-gathering phase before each value update. This allows their decision time to drop from being exponential in ...

ven. 22 janvier 2016 -- Mathieu Hoyrup (LORIA)

Que peut-on savoir d'une fonction si elle nous est présentée : - sous forme d'un programme calculant cette fonction, - sous forme d'une boîte noire permettant de connaître les valeurs de cette fonction sur toutes les entrées.

Disposer d'un programme donne au moins autant d'information qu'avoir accès ...

ven. 15 janvier 2016 -- Eitan Altman (INRIA)

Defining an optimal protection strategy against viruses, spam propagation or any other kind of contamination process is an important feature for designing new networks and architectures. In this work, we consider decentralized optimal protection strategies when a virus is propagating over a network through a SIS epidemic process. We assume ...

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 ...