Ven 08 avril 2016 -- Chien-Chung Huang (Gothenburg)

Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A\cup B, E) where each vertex u \in A\cup B ranks its neighbors in an order of preference, perhaps involving ties. A matching M is said to be stable if there is ...

Ven 18 mars 2016 -- Nguyen Kim Thang (IBISC)

In the setting of prophet inequalities and secretary problem, one observes a sequence of random objects and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The objective is to maximize the reward while observing the objects in an online manner ...

Ven 11 mars 2016 -- Hugo Férée (Université de Lille)

L'analyse récursive est un domaine qui s'attache à comprendre la notion de calcul sur des ensembles non dénombrables comme les nombres réels ou les fonctions réelles par exemple. Il permet entre autres de définir une notion de complexité sur de tels ensembles, mais les classes de complexité associées ...

Ven 26 février 2016 -- Benjamin Hellouin (Universidad Andrés Bello (Santiago))

Simulating universal computation in a given system has multiple uses: characterising the power of a model of computation, demonstrating the impossibility to predict the long-term behaviour or the properties of a physical model, forcing the system to adopt a given, computationally complex behaviour... The technical details of these simulations, corresponding ...

Ven 19 février 2016 -- Matthias Függer (Max-Planck-Institut)

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

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