# Tag: Plateau seminar

## Amortized Averaging Algorithms for Approximate Consensus

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

## Lire un programme ou l'exécuter : quelle différence ?

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

## Game theory applied to Protection against SIS Epidemics in Networks

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

## The Graph-Bin Packing Problem

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

## Algorithms for Spectrum Allocation in Wireless Networks.

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

## On the Path to Independence

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

## Classification from strategic data: a game-theoretic perspective

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

« Page 2 / 2