May 4, 2017
Keynote LIG
–
May 4, 2017
Bâtiment IMAG (amphitheater)
Saint-Martin-d'Hères, 38400
France
-
News
- Journée au vert POLARIS 2022/05/23
- DATAMOVE/POLARIS picnic 2021/06/22
- DATAMOVE/POLARIS BBQ 2019 2019/06/14
- POLARIS Bootcamp (May 2019) 2019/05/24
- slides of Andras Gyorgy 2016/01/15
Next seminars
Events
Events in May–June 2017
MMonday TTuesday WWednesday TThursday FFriday SSaturday SSunday May
1May 1, 20172May 2, 20173May 3, 2017Keynote LIG–
May 4, 2017Bâtiment IMAG (amphitheater)Saint-Martin-d'Hères, 38400France5May 5, 20176May 6, 20177May 7, 20178May 8, 20179May 9, 201710May 10, 2017Almost acyclic simple stochastic games by Pierre Coucheney (Univ. Versailles)–
May 11, 2017A simple stochastic game is a 2 players zero-sum game played on a
graph. The game consists in moving a pebble on the graph. Players
control the direction taken by the pebble on disjoint sets of
vertices, and the direction of the other vertices is randomly
determined. The goal of the player called MAX (resp. MIN) is to
make the pebble reach a sink with the highest (resp. lowest)
possible value.Computing the optimal strategies of this game is one of the few
problems in NP and coNP which is not known to be in P. This
problem is also interesting for worst case stochastic
optimization, since Markov decision process with an adversary can
be reduced to it. However, there are instances for which the game
can be solved in polynomial time. This is the case if the graph
is acyclic. In this talk, I will show that several classes of
graph closed to acyclic graphs are tractable. I will also present
algorithmic questions related to similar reachability problem on
rotor graph, which is also known to be in NP and coNP but not in P.Bâtiment IMAG (442)12May 12, 201713May 13, 201714May 14, 201715May 15, 201716May 16, 201717May 17, 2017Versions parallèles et distribuées de l'algorithme de meilleure réponse.–
May 18, 2017Dans cet exposé, nous calculons la complexité moyenne de l'algorithme de meilleure réponse dans des jeux de potentiel. Contrairement au cas le pire (complexité exponentielle), la complexité moyenne est linéaire en le nombre de joueurs. On montre aussi que l'algorithme de meilleure réponse est optimal parmi tous ceux qui reposent sur une information locale. Nous étudions aussi les versions distribuées de la dynamique de meilleure réponse. Nous montrons d’abord que la sélection du prochain joueur selon une suite IID donne un temps de convergence moyen à une constante multiplicative de celui d’une suite optimale. De plus, une telle suite IID peut être implémentée de manière distribuée nous permettant de proposer un algorithme distribué avec un coût en temps d’exécution global minimal. Ensuite nous montrons comment utiliser la structure des interactions entre joueurs pour, en permettant aux joueurs non associés d’agir simultanément, améliorer le temps d’exécution. Dans un contexte centralisé, les joueurs peuvent être groupés selon une coloration du graphe d’interaction permettant à la complexité d’être proportionnelle au nombre chromatique de ce graphe au lieu du nombre de joueurs. Enfin, cette structure peut aussi être exploitée dans le contexte distribué pour des algorithmes plus efficaces.
Bâtiment IMAG (442)19May 19, 201720May 20, 201721May 21, 201722May 22, 201723May 23, 201724May 24, 201725May 25, 201726May 26, 201727May 27, 201728May 28, 201729May 29, 201730May 30, 201731May 31, 2017June
Keynote LIG (Antoine Cornuéjols)–
June 1, 2017Bâtiment IMAG (amphitheater)Saint-Martin-d'Hères, 38400France2June 2, 20173June 3, 20174June 4, 20175June 5, 20176June 6, 20177June 7, 2017LIG Day in AutransN/A
June 8, 20179June 9, 201710June 10, 201711June 11, 201712June 12, 201713June 13, 201714June 14, 2017Coalition games on interaction graphs by Nicolas Bousquet (Gscop)–
June 15, 2017We consider cooperative games where the viability of a coalition is determined by whether or not its members have the ability to communicate amongst themselves. This necessary condition for viability was proposed by Myerson and is modeled via an interaction graph; a coalition S of vertices is then viable if and only if the induced graph S is connected.
The non-emptiness of the core of a coalition game can be tested by a well-known covering LP. Moreover, the integrality gap of its dual packing LP defines exactly the multiplicative least-core and the relative cost of stability of the coalition game. This gap is upper bounded by the packing-covering ratio which is known to be at most the treewidth of the interaction graph plus one.
We examine the packing-covering ratio and integrality gaps of graphical coalition games in more detail. First we introduce a new graph parameter, called the vinewidth (a parameter derived from the treewidth), which characterizes the worst packing-covering ratio. Then we will show that this new parameter correctly evaluates both primal and dual integrality gaps.
Joint work with Zhentao Li and Adrian Vetta.
Bâtiment IMAG (442)16June 16, 201717June 17, 201718June 18, 201719June 19, 201720June 20, 201721June 21, 2017Malcom Egan Seminar : "Mechanism design in on-demand transport"–
June 22, 2017Abstract: Uber is one of several recent companies adopting a business model that lies in stark contrast with the standard approach used by taxi services. Underlying Uber's business model is a new architecture--based on a market mechanism--which governs how commuters, drivers, and the company interact with each other. In this talk, we develop a new general model for on-demand transport networks with self-interested passengers and drivers. With this model, we introduce market mechanisms to allocate and price journeys, as well as the market formation subproblem. By analysis and simulation, we characterize the performance of the mechanisms and discuss insights using data obtained from a real on-demand transport provider.
Malcolm Egan received the B.E. degree in electrical engineering from the University of Queensland, Brisbane, Australia, in 2009 and the Ph.D. in electrical engineering from the University of Sydney, Sydney, Australia, in 2014. In the years 2014-2016, he was a Postdoctoral Researcher in the Department of Computer Science, Czech Technical University in Prague, Czech Republic and in the Laboratoire de Mathématiques, Université Blaise Pascal, Clermont-Ferrand, France. He is now a Postdoctoral Researcher in CITI Lab, INSA-Lyon, INRIA, Université de Lyon. His research interests include optimization theory, mechanism design, information theory and statistical signal processing, as well as their applications.
Bâtiment IMAG (442)23June 23, 201724June 24, 201725June 25, 201726June 26, 201727June 27, 201728June 28, 2017A stochastic approach for optimizing green energy consumption in distributed clouds by Fanny Dufossé (Inria)–
June 29, 2017A stochastic approach for optimizing green energy consumption in distributed clouds
The energy drawn by Cloud data centers is reaching worrying levels, thus inciting providers to install on-site green energy producers, such as photovoltaic panels. Considering distributed Clouds, workload managers need to geographically allocate virtual machines according to the green production in order not to waste energy. In this paper, we propose SAGITTA: a Stochastic Approach for Green consumption In disTributed daTA centers. We show that compared to the optimal solution, SAGITTA consumes 4% more brown energy, and wastes only 3.14% of the available green energy, while a traditional round-robin solution consumes 14.4% more energy overall than optimum, and wastes 28.83% of the available green energy.
Bâtiment IMAG (442)30June 30, 2017July
1July 1, 20172July 2, 2017Meta
