Lieu 2014/15: Salle 445 au LRI, Université Paris-Sud 11, Bât 650 Ada Lovelace, Rue Noetzlin, 91190 Gif-sur-Yvette. Comment venir ?

Organisé toutes les deux semaines en moyenne depuis octobre 2011, ce séminaire réunit les chercheurs et enseignants‐chercheurs du domaines de l'algorithmique présents sur le plateau de Saclay. Les interventions des chercheurs locaux ou extérieurs offrent l'occasion de faire connaître les résultats des équipes participantes et donnent lieu à des échanges entre elles. D'abord abrité au LRI (2011/12), le séminaire a ensuite été accueilli au LIX (2012/13) puis à Supélec (2013/14). Le séminaire porte sur l'ensemble des thématiques du domaine de l'algorithmique, et notamment (liste non exhaustive) :

  • l’algorithmique de la théorie de calculabilité,
  • la théorie de la complexité
  • la théorie algorithmique des jeux,
  • l’optimisation discrète
  • l’algorithmique distribuée
...jusqu’à l’algorithmique appliquée à des problèmes industriels.

Ce séminaire est financé par le LABEX DigiCosme -Paris-Saclay : DIGITAL Worlds: distributed data, programs and architectures

 

25 Juin 2015, mi-journée du séminaire algorithmique du plateau de Saclay, salle 455

13H30 : Pierre Coucheney (PRISM, Université de Versailles) Finding optimal strategies of almost acyclic simple stochastic games
14H20 : Gena Hahn (Université de Montréal) A biased survey of cops-and robbers games
15H10 : pause café.
15H30 : Nguyen Kim Thang (IBISC, University Evry Val d'Essonne) Lagragian Duality in Online Scheduling
16H20 : Stefan Mengel (LIX, Ecole Polytechnique) A Strongly Exponential Separation of DNNFs from CNF Formulas

22 mai 15

à 2h30, salle 445 : Elèves de deuxième année, cycle-ingénieur Supélec (MM. Belaube, de Méric de Bellefon, Bergé, Cavarec, Chabrillac, Couronné, Doutre, Dufoulon, Lundy, Salaün), Métaheuristique basée sur le recuit quantique .

10 avril 15

à 2h30, salle 435 : Bernadette Charron-Bost, Approximate Consensus in Highly Dynamic Networks .

27 mars 15

à 2h30, salle 435 : Devan Sohier, Marches aléatoires dans les réseaux dynamiques : auto-stabilisation et mécanismes probabiliste.

27 février 15

à 2h30, salle 435 : Benjamin Hellouin, Mesures limites dans les automates cellulaires.

13 février 15

à 2h30, salle 435 (salle des thèses) : Hirotaka Ono, Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation.

8 decembre 14 (attention, exceptionellement lundi)

à 2h30, salle 445 : Volker Turau, Self-stabilizing local k-placement of replicas with minimal variance.

27 novembre 14

à 2h30, salle 445 : Gerry Siegemund, Self-Stabilizing algorithms in the context of wireless sensor networks.
Slides

7 novembre 14

à 2h30, salle 475 : Marvin Künnemann, Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic.

17 octobre 14

à 2h30, salle 445 : Dieter Kratsch, Minimal Dominating Sets in Graphs: Enumeration, Combinatorial Bounds and Graph Classes .

19 septembre 14

à 2h30, salle 445 : Thomas Sauerwald, Load Balancing by Randomized Rounding .

12 septembre 14

à 2h30, salle 445 : Guillaume Aupy, Checkpointing algorithms and fault prediction .

13 juin 14

à 2h30, l'amphithéâtre F3.06 : Hubie Chen, The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity.

4 avr 14

à 2h30, l'amphithéâtre F3.05 : Nabil Mustafa, QPTAS for Geometric Set-Cover Problems via Optimal Separators.

21 mar 14

à 2h30, l'amphithéâtre F3.06 : Marcello Mamino, On the computing power of semialgebraic functions.

7 mar 14

à 2h30, l'amphithéâtre F3.06 : Dimitri Watel, Problème de l'arborescence de Steiner : limitation du nombre de noeuds de branchement.

21 fev 14

à 2h30, l'amphithéâtre F3.06 : Frantisek Franek (McMaster), How many double squares can a string contain?

14 fev 14

à 2h30, l'amphithéâtre F3.06 : Benjamin Doerr (LIX), Tight Analysis of Randomized Rumor Spreading in Complete Graphs.

7 fev 14

à 2h30, l'amphithéâtre F3.06 : Adrian Tanasa, Polynôme de Tutte pour les graphes et les madroïdes - lien avec les théories quantiques des champs et preuve d'universalité

17 jan 14

à 2h30, l'amphithéâtre F3.06 : Alexandre Maurer (LIP6), Tolerating Byzantine failures in sparse networks

6 dec 13

à 2h30, l'amphithéâtre F3.06 : Jérome Leroux, Acceleration for Vector Addition Systems

22 nov 13

à 2h30, l'amphithéâtre F3.06 : Stefan Mengel, Structural tractability of counting solutions to conjunctive queries

18 oct 13

à 2h30, l'amphithéâtre F3.06 : Alexis Lamiable, Coloration multiple et valuée sur des graphes d'interférence radio

4 oct 13

à 2h30, l'amphithéâtre F3.06 : Mikael Rabbie, On trustful population protocols

21 juin 13

à 2h30 : Emmanuel Hainry, Complexité d'ordre supérieur, de l'Analyse Récursive aux Basic Feasible Functionals

7 juin 13

à 2h30 : Menelaos Karavelas, Qualitative Symbolic Perturbations

17 mai 13

à 2h30 Pierre Fraigniaud : Impact des identifiants sur la calculabilité distribuée

26 avr 13

à 2h30 Xavier Goaoc : De l'optimisation combinatoire aux théorèmes du nerf

19 avr 13

à 2h30 Bernadette Charron-Bost : Orientation and Connectivity Based Criteria for Asymptotic Consensus

5 avr 13

à 2h30 Florian Richoux : An efficient parallel local search algorithm

29 mar 13

à 2h30 Christoph Dürr : Contraintes d'ordre pour ordonnancement à une machine avec coût polynomial

22 mar 13

à 2h30 Meghyn Bienvenu : Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP

22 fev 13

à 2h30 Moritz Müller : Graph invariants in proof complexity.

08 fev 13

à 1h30 Carola Dörr née Winzen : Query Complexity and Mastermind

01 fev 13

à 2h30 Bruno Escoffier : Algorithmes approches non polynomiaux

14 dec 12

à 2h30 Barnaby Martin : Distance Constraint Satisfaction Problems

30 nov 12

à 2h30 Giorgio Lucarelli, LIP 6 : On preemptive and non-preemptive speed-scaling scheduling

16 nov 12

à 2h30 Johan Thapper : Linear programming and the complexity of finite-valued CSPs

9 nov 12

à 2h30 Monique Laurent : Matrix Completions Attention, lieu exceptionnel : PUIO (petit amphi): plan d'accès

vendredi 26 oct 12

à 2h00 Nicolas M. Thiéry, Nathann Cohen : Les rencontres Sage en région parisienne Attention, lieu exceptionnel : Bâtiment 650/PCRI, salle 445, Laboratoire de Recherche en Informatique, Orsay Comment venir ?

vendredi 19 oct 12

à 2h30 Thomas Nowak : The Transience of Long Walks

vendredi 5 oct 12

à 2h30 Jin Akiyama : Tessellations, Reversibilities and Decompositions of Polyhedra

vendredi 29 june 12

à 2h30 Periklis Papkonstantinou : Time-space tradeoffs for width-parameterized SAT

vendredi 8 june 12

à 12h00 - 15h00 : Barbecue au lac de l'École Polytechnique !

vendredi 1 june 12

à 02h30 Yannis Tollis : Weak Dominance and Overloaded Orthogonal Drawings. Le séminaire sera exceptionnellement dans la salle 455.

vendredi 25 mai 12

à 02h00 Mathieu Liedloff : Un algorithme exponentiel pour l'étiquetage L(2,1) de graphes

vendredi 25 mai 12

à 03h00 Petru Valicov : A new algorithm for the Orthogonal Packing Problem

vendredi 4 mai 12

à 02h30 Johan Thapper : A new graph parameter and its relation to approximation properties of graph H-colouring

vendredi 13 avr 12

à 02h30 Pavol Hell : Finite obstructions to graph partitions

vendredi 30 mar 12

à 02h30 Pablo Arrighi : The physical Church-Turing thesis and the principles of quantum theory

vendredi 16 mar 12

à 02h30 Pierre Couchner : Apprentissage d'équilibre dans les jeux de potentiel bruités

vendredi 17 fev 12

à 02h30 Daniele Gardy : Arbres enrichis

vendredi 3 fev 12

à 02h30 Nathann Cohen : Une preuve courte d'un résultat de choisissabilité dans les graphes planaires

vendredi 20 jan 12

à 02h30 Amaury Pouly : Computing with analog models: On the complexity of solving differential equations.

vendredi 6 jan 12

à 02h30 David Auger : Codes identifiants dans les graphes

mardi 6 dec 11

à 02h30 Arash Rafiey : Homomorphism Problems and Approximation Algorithms

mardi 22 nov 11

à 02h30 Sylvain Peyronnet : Approximation et vérification

mardi 8 nov 11

à 02h30 Yann Strozecki : Complexite d'énumeration : méthodes logiques et algébrique
Slides

mardi 18 oct 11

à 02h30 Florent Madelaine : La complexité des problèmes de contraintes
Slides

  Une méthode simple pour s'inscrire / se désinscrire est d'y cliquer jusqu'à obtention de l'effet désiré.

  Alternativement, vous pouvez envoyer des mails à sympa@lix.polytechnique.fr avec comme sujet
SUBSCRIBE sem-algo-saclay@lix.polytechnique.fr Prénom Nom
ou
UNSUBSCRIBE sem-algo-saclay@lix.polytechnique.fr
pour vous inscrire ou vous désinscrire respectivement.