Nos tutelles

CNRS Dauphine PSL *

Rechercher





Accueil > PERSONNES

Membres

publié le , mis à jour le

retour a la liste des membres

Michail Lampis

Email : michail.lampis@dauphine.fr

Tel : 0144054050
Bureau : P622
Site Personnel: http://www.lamsade.dauphine.fr/~mlampis
Pole : Optimisation combinatoire algorithmique
Status : Maitre de conférence
Domaines de Recherche : Algorithmes, Approximation, Complexité Paramétrée

Encadrement de these de doctorat :


voir toutes les theses


Publications DFIS


24 Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse (, and ), In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) (Nicolas Ollinger, Heribert Vollmer, ed.), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, . [bibtex]

23 Time-Approximation Trade-offs for Inapproximable Problems (, and ), In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) (Nicolas Ollinger, Heribert Vollmer, ed.), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, . [bibtex]

22 Upper Domination : Complexity and Approximation (, , , , , , , , and ), In Combinatorial Algorithms. 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings (Veli Mäkinen, Simon J. Puglisi, Leena Salmela, ed.), Springer, . [bibtex]

21 Algorithmic Aspects of Upper Domination: A Parameterized Perspective (, , , , , , , , and ), In Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings (Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri, ed.), Springer, . [bibtex]

20 Parameterized Power Vertex Cover (, , and ), In Graph-Theoretic Concepts in Computer Science 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers (Pinar Heggernes, ed.), Springer Berlin Heidelberg, . [bibtex]

19 New inapproximability bounds for TSP (, and ), In Journal of Computer and System Sciences, volume 81, . [bibtex] [doi]

18 Scrabble is PSPACE-Complete (, and ), In Journal of Information Processing, volume 23, . [bibtex] [doi]

17 Parameterized Algorithms for Parity Games (, , , and ), In Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II (Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella, ed.), Springer, . [bibtex]

16 Complexity and Approximability of Parameterized MAX-CSPs (, , , and ), In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) (Thore Husfeldt, Iyad Kanj, ed.), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, . [bibtex]

15 The Computational Complexity of the Game of Set and Its Theoretical Applications ( and ), In LATIN 2014: Theoretical Informatics 11th Latin American Symposium, Montevideo, Uruguay, March 31–April 4, 2014. Proceedings (Alberto Pardo, Alfredo Viola, ed.), Springer Berlin Heidelberg, . [bibtex]

14 Parameterized Edge Hamiltonicity (, , and ), In Graph-Theoretic Concepts in Computer Science 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers (Dieter Kratsch, Ioan Todinca, ed.), Springer International Publishing, . [bibtex]

13 Parameterized Approximation Schemes Using Graph Widths (), In Automata, Languages, and Programming 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I (Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias, ed.), Springer Berlin Heidelberg, . [bibtex]

12 Model Checking Lower Bounds for Simple Graphs (), In Logical Methods in Computer Science, volume 10, . [bibtex] [doi]

11 Improved Inapproximability for TSP (), In Theory of Computing, volume 10, . [bibtex] [doi]

10 Parameterized maximum path coloring (), In Theoretical Computer Science, volume 511, . [bibtex] [doi]

9 Model Checking Lower Bounds for Simple Graphs (), In Automata, Languages, and Programming 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I (Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, David Peleg, ed.), Springer Berlin Heidelberg, . [bibtex]

8 New Inapproximability Bounds for TSP (, and ), In Algorithms and Computation 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings (Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam, ed.), Springer Berlin Heidelberg, . [bibtex]

7 Parameterized Algorithms for Modular-Width (, and ), In Parameterized and Exact Computation 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers (Gregory Gutin, Stefan Szeider, ed.), Springer International Publishing, . [bibtex]

6 Online maximum directed cut ( and ), In Journal of Combinatorial Optimization, volume 24, . [bibtex] [doi]

5 Parameterized Modal Satisfiability (, and ), In Algorithmica, volume 64, . [bibtex] [doi]

4 Algorithmic Meta-theorems for Restrictions of Treewidth (), In Algorithmica, volume 64, . [bibtex] [doi]

3 Ordered coloring of grids and related graphs (, , , and ), In Theoretical Computer Science, volume 444, . [bibtex] [doi]

2 Scrabble Is PSPACE-Complete (, and ), In Fun with Algorithms 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings (Evangelos Kranakis, Danny Krizanc, Flaminia Luccio, ed.), Springer Berlin Heidelberg, . [bibtex]

1 Improved Inapproximability for TSP (), In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings (Anupam Gupta, Klaus Jansen, José Rolim, Rocco Servedio, ed.), Springer Berlin Heidelberg, . [bibtex]

Publications HAL