Highly Resource-limited Distributed Systems
In this talk I would like to advocate the study of non-classical distributed systems whose computing nodes can perform only simple computations under highly restricted communication mechanisms and memory capabilities.
I will present two problems, we are currently working on, one from chip design and one from biology, showing that ...
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 ...
Choosing k best arms in adversarial bandit setting: application to inter-cell Interference Coordination
This talk address to Multi-Armed Bandit problem for Distributed Inter-Cell Interference Coordination. In order to achieve high data rates in future wireless packet switched cellular networks, aggressive frequency reuse is inevitable due to the scarcity of the radio resources. While intra-cell interference is mostly mitigated and can be ignored, inter-cell ...
Locating pairs of vertices on Hamiltonian cycles
We first introduce some of our recent results that generalises Dirac's theorem in Hamiltonian graph theory. Then we will focus on the following conjecture of Enomoto that states that, if \(G\) is a graph of order \(n\) with minimum degree \(delta(G)geq frac{n}{2}+1\), then for ...
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 25 / 25