Accueil des participants

Carpooling in Social Networks

Claire Mathieu (ENS, Collége de France)

Slides of the presentation

We consider the online carpool fairness problem of [Fagin and Williams, 1983] in which an online algorithm is presented with a sequence of pairs drawn from a group of n potential drivers. The online algorithm must select one driver from each pair, with the objective of partitioning the driving burden as fairly as possible for all drivers. The unfairness of an online algorithm is a measure of the worst-case deviation between the number of times a person has driven and the number of times they would have driven if life was completely fair.
We introduce a version of the problem in which drivers only carpool with their neighbors in a given social network graph; this is a generalization of the original problem, which corresponds to the social network of the complete graph. We show that for graphs of degree d, the unfairness of deterministic algorithms against adversarial sequences is exactly d/2.
For random sequences of edges from planar graph social networks we give a [deterministic] algorithm with logarithmic unfairness (holds more generally for any bounded-genus graph). This does not follow from previous random sequence results in the original model, as we show that restricting the random sequences to sparse social network graphs may increase the unfairness.
A very natural class of randomized online algorithms are so-called static algorithms that preserve the same state distribution over time. Surprisingly, we show that any such algorithm has unfairness $\Theta^{\sqrt{d}}$ against oblivious adversaries. This shows that the local random greedy algorithm of [Ajtai et al, 1996] is close to optimal amongst the class of static algorithms. A natural (non-static) algorithm is global random greedy (which acts greedily and breaks ties at random). We improve the lower bound on the competitive ratio from $\Omega (log^{1/3}(d))$ to $\Omega(log d)$. We also show that the competitive ratio of global random greedy against adaptive adversaries is $\Omega(d)$.
This is joint work with: Amos Fiat, Anna R. Karlin, Elias Koutsoupias, ​and Rotem Zach​.

Traffic Routing: Efficiency, Equilibrium, and Dynamics

Panayotis Mertikopoulos (CNRS, LIG)

Transparents de la présentation

Traffic routing in congested networks is a notoriously difficult problem. Even in its convex incarnations, it suffers from the curse of dimensionality (for instance, in the number of paths in the network), limited information at the decision-maker end (be it the network controller or an individual user), delays and asynchronicities, etc. Nevertheless, empirical studies in real-world networks have shown that the gap between optimality and equilibrium (that is, what the network's users would unilaterally choose for themselves) is surprisingly small, under both light and heavy traffic. This talk will focus on whether these observations can be justified theoretically and what kind of algorithmic schemes can be used to overcome the challenges cited above.

Pause café

New results in distributed optimization and consensus learning

Kevin Scaman (Huawei, Noah's Ark Lab)

The training of machine learning methods on large-scale datasets often requires the use of distributed computing platforms, both to parallelize computation and allow the storage of the whole dataset across multiple machines. In such a context, a slow communication between machines may downgrade the performance of inference or optimization algorithms. In this presentation, I will show how the ideas of optimization theory can be extended to understand the fundamental limitations of distributed algorithms when machines are bound to communicate across a network of limited bandwidth, and how to derive optimal distributed optimization algorithms. More specifically, I will provide optimal convergence rates for the distributed optimization of strongly convex and smooth functions in two settings (centralized and decentralized architectures), along with algorithms meeting these optimal rates.

Pause dejeuner

L'optimisation mathématique au service de la transition énergétique.

Sandrine Charousset (EDF)

To contribute to the European objectives of reducing pollutant emissions, the European energy system will evolve significantly in the coming years. The main changes will come from massive insertion of intermittent renewable energies, which will only be possible by using new levers of flexibility, adaptating transmission and distribution networks, and creating new market mechanisms... In this presentation we will give an overview of these changes, and describe the impact they will have on the formalization of the associated optimization problems that are opening up new areas of research for the academic and industrial community.

Optimiser les "rotations équipages" d’une compagnie aérienne

Frédéric Meunier (ENPC, CERMICS)

Transparents de la présentation

Le personnel est l'une des sources principales des coûts d’exploitation d’une compagnie aérienne. Optimiser l’affectation des équipages aux vols est donc crucial pour la rentabilité d’une telle entreprise. Cette affectation consiste à construire des itinéraires pour les équipages, appelés rotations équipages, sur le réseau formé par les vols programmés sur un horizon d'une semaine.
Ce problème est cependant d’une complexité redoutable car, d’une part, l’espace des solutions est gigantesque et, d’autre part, la réglementation et les conventions collectives rendent difficile la modélisation mathématique des rotations équipages. En nous appuyant sur de nouveaux algorithmes de plus courts chemins développés par Axel Parmentier dans sa thèse, nous démontrons que l’approche usuelle par génération de colonnes peut passer à l’échelle : nous résolvons à l'optimalité les instances réelles d’Air France, qui peuvent mettre en jeu des réseaux de l’ordre de 3000 vols.
Enfin, nous montrons également comment il est possible d’optimiser simultanément les itinéraires des avions sur le même réseau, ce qui permet, en raison de certaines contraintes techniques liantes, une réduction additionnelle des coûts.
Travail joint avec Axel Parmentier.

Pause café

Machine learning for Wireless Networks: Challenges and opportunities

Merouane Debbah (Huawei)

Transparents de la présentation

Mobile cellular networks are becoming increasingly complex to manage while classical deployment/optimization techniques are cost-ineffective and thus seen as stopgaps. This is all the more difficult considering the extreme constraints of 5G networks in terms of data rate (more than 10 Gb/s), massive connectivity (more than 1000000 devices per km2), latency (under 1ms) and energy efficiency (a reduction by a factor of 100 with respect to 4G network). Unfortunately, the development of adequate solutions is severely limited by the scarcity of the actual ressources (energy, bandwidth and space). Recently, the community has turned to a new ressource known as Artificial Intelligence at all layers of the network to exploit the increasing computing power afforded by the improvement in Moore’s law in combination with the availability of huge data in 5G networks. This is an important paradigm shift which considers the increasing data flood/huge number of nodes as an opportunity rather than a curse. In this talk, we will discuss through various examples how the recent advances in big data algorithms can provide an efficient framework for the design of 5G Intelligent Networks.