Home
Research
Teaching
Name: Michael Lampis

Research interests:

I am generally interested in the field of theoretical computer science and more specifically in algorithm design and analysis. Favorite topics include approximation algorithms and fixed-parameter tractability.


Research projects and grants:

I am or have been the Principal Investigator of the following projects.

  1. Project GRAPA (Graph Algorithms for Parameterized Approximation). Bilateral project with Japan, under the PHC Sakura Program. PI of Japanese team: Yota Otachi. Duration: Jan 2017-Dec 2018 (two years). Total budget: 12,000 Euros + 1,000,000 Yen.
  2. Project FAPA (Frontiers in Parameterized Approximation). Project funded under the JCJC program of the CNRS. Duration: Jan 2015-Dec 2015 (one year). Total budget: 6,000 Euros.

In addition, I am (or have been) a member of the following research projects.

  1. Project MultiFAC (Multiple Facility Location). PSL funded project in collaboration with the ENS. Duration: Jan 2017-Dec 2018 (two years). Total budget: 80,000 Euros. PI: Vangelis Paschos.
  2. Project Stability versus Optimality in Dynamic Environment Agorithmics. PGMO funded project in collaboration with LIP6. Duration: Jan 2017-Dec 2017 (one year). Total budget: 6,000 Euros. PI: Bruno Escoffier.
  3. Project APPEAR (Approximation Algorithms for the Efficient Allocation of Resources). Project funded under the JCJC program of the CNRS. Duration: Jan 2016-Dec 2016 (one year). Total budget: 12,000 Euros. PI: Julien Lesca.

Student Supervision:

PhD students

  1. Ioannis Katsikarelis. Starting date: Sep 2015. Jointly supervised with Vangelis Paschos. Thesis topic: Parameterized Approximation Algorithms.
  2. Louis Dublois. Starting date: Sep 2017. Jointly supervised with Vangelis Paschos. Thesis topic: Sub-Exponential Approximation Algorithms.

Master's students

  1. Hacene Kerkache. Mar 2016-Sep 2016. Master's thesis topic: The computational complexity of games and puzzles.

Peer-reviewed Publications:
Below is a list of publications, including drafts. For papers published in an open access journal, you can also find link to the "official" version (which is usually better than the draft).
  1. Title: Finer Tight Bounds for Coloring on Clique-width
    Author(s): Michael Lampis
    Conference: ICALP 2018
    Links: draft
  2. Title: New Results on Directed Edge Dominating Set
    Author(s): Remy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis
    Conference: MFCS 2018
    Links: draft
  3. Title: Parameterized Orientable Deletion
    Author(s): Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora
    Conference: SWAT 2018
    Links: draft
  4. Title: Multistage Matchings
    Author(s): Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos
    Conference: SWAT 2018
    Links: draft
  5. Title: Structurally Parameterized d-Scattered Set
    Author(s): Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos
    Conference: WG 2018
    Links: draft
  6. Title: How Bad is the Freedom to Flood-It?
    Author(s): Remy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, and Yota Otachi
    Conference: FUN 2018
    Links: draft
  7. Title: QBF as an Alternative to Courcelle's Theorem
    Author(s): Michael Lampis, Stefan Mengel, and Valia Mitsou
    Conference: SAT 2018
    Links: draft
  8. Title: Parameterized (Approximate) Defective Coloring
    Author(s): Remy Belmonte, Michael Lampis, and Valia Mitsou
    Conference: STACS 2018
    Links: draft
  9. Title: Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center
    Author(s): Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos
    Conference: ISAAC 2017
    Links: draft
  10. Title: Treewidth with a Quantifier Alternation Revisited
    Author(s): Michael Lampis and Valia Mitsou
    Conference: IPEC 2017
    Links: draft
  11. Title: On the Parameterized Complexity of Red-Blue Points Separation
    Author(s): Edouard Bonnet, Panos Giannopoulos, and Michael Lampis
    Conference: IPEC 2017
    Links: draft
  12. Title: Defective Coloring on Classes of Perfect Graphs
    Author(s): Rémy Belmonte, Michael Lampis, Valia Mitsou
    Conference: WG 2017
    Links: draft, slides (slides by Valia Mitsou)
  13. Title: The Many Facets of Upper Domination
    Author(s): Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jerome Monnot, Vangelis Th. Paschos
    Conference: IWOCA 2016 (approximation part) and AAIM 2016 (parameterized part)
    Journal: TCS 2017 (merged paper)
    Links: draft
  14. Title: Parameterized Power Vertex Cover
    Author(s): Eric Angel, Evripidis Bampis, Bruno Escoffier, Michael Lampis
    Conference: WG 2016
    Links: draft, slides
  15. Title: Sub-Exponential Approximation Schemes for CSPs: From Dense to Almost-Sparse.
    Author(s): Dimitris Fotakis, Michael Lampis and Vangelis Paschos
    Conference: STACS 2016
    Links: draft, slides
  16. Title: Time-Approximation Trade-offs for Inapproximable Problems.
    Author(s): Edouard Bonnet, Michael Lampis and Vangelis Paschos
    Conference: STACS 2016
    Journal: JCSS (2018)
    Links: draft, slides (slides by Edouard Bonnet)
  17. Title: Complexity and Approximability for Parameterized CSPs
    Author(s): Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, Tobias Moemke
    Conference: IPEC 2015
    Journal: Algorithmica (2017)
    Links: draft
  18. Title: Parameterized Algorithms for Parity Games
    Author(s): Jakub Gajarsky, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak
    Conference: MFCS 2015
    Links: draft
  19. Title: Parameterized Approximation Schemes Using Graph Widths
    Author(s): Michael Lampis
    Conference: ICALP 2014
    Links: draft, slides
  20. Title: Parameterized Edge Hamiltonicity
    Author(s): Michael Lampis, Kazuhisa Makino, Valia Mitsou and Yushi Uno
    Conference: WG 2014
    Journal: DAM (2017)
    Links: draft
  21. Title: The Computational Complexity of the Game of Set and its Theoretical Applications
    Author(s): Michael Lampis and Valia Mitsou
    Conference: LATIN 2014
    Links: draft
  22. Title: New Inapproximability Bounds for TSP
    Author(s): Marek Karpinski, Michael Lampis and Richard Schmied
    Conference: ISAAC 2013
    Journal: JCSS (2015)
    Links: draft, slides
  23. Title: Parameterized Algorithms for Modular-Width
    Author(s): Jakub Gajarsky, Michael Lampis and Sebastian Ordyniak
    Conference: IPEC 2013
    Links: draft
  24. Title: Model Checking Lower Bounds for Simple Graphs
    Author(s): Michael Lampis
    Conference: ICALP 2013
    Journal: Logical Methods in Computer Science (2014)
    Links: draft, online, slides
  25. Title: Improved Inapproximability for TSP
    Author(s): Michael Lampis
    Conference: APPROX 2012
    Journal: Theory of Computing (2014)
    Links: draft, online, slides
  26. Title: Scrabble is PSPACE-complete
    Author(s): Michael Lampis, Valia Mitsou and Karolina Soltys
    Conference: FUN with Algorithms 2012
    Journal: Journal of Information Processing (2015)
    Links: draft
  27. Title: A kernel of order 2k-clogk for Vertex Cover
    Author(s): Michael Lampis
    Journal:        Information Processing Letters (2011)
    Links: draft
  28. Title: Parameterized Maximum Path Coloring
    Author(s): Michael Lampis
    Conference: IPEC 2011
    Journal: Theoretical Computer Science (2013)
    Links: draft, slides
  29. Title: Algorithmic Meta-Theorems for Restrictions of Treewidth
    Author(s): Michael Lampis
    Conference: ESA 2010
    Journal: Algorithmica (2012)
    Links: draft, slides
  30. Title: Parameterized Modal Satisfiability
    Author(s): Antonis Achilleos, Michael Lampis and Valia Mitsou
    Conference: ICALP 2010
    Journal: Algorithmica (2012)
    Links: draft
  31. Title: Vertex Cover Problem Parameterized Above and Below Tight Bounds
    Author(s): Gregory Gutin, Eun Jung Kim, Michael Lampis and Valia Mitsou
    Journal:        Theory of Computing Systems (2011)
    Links: draft
  32. Title: Online Maximum Directed Cut
    Author(s): Amotz Bar-Noy and Michael Lampis
    Conference: ISAAC 2009
    Journal: Journal of Combinatorial Optimization (2012)
    Links: draft, slides
  33. Title: Ordered Coloring for Grids and Related Graphs
    Author(s): Amotz Bar-Noy, Panagiotis Cheilaris, Michael Lampis, Valia Mitsou and Stathis Zachos
    Conference: SIROCCO 2009
    Journal: Theoretical Computer Science (2012)
    Links: draft
  34. Title: On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
    Author(s): Michael Lampis, Georgia Kaouri and Valia Mitsou
    Conference: ISAAC 2008
    Journal: Discrete Optimization (2011)
    Links: draft, slides
  35. Title: The Ferry Cover Problem
    Author(s): Michael Lampis and Valia Mitsou
    Conference: FUN with Algorithms 2007
    Journal: Theory of Computing Systems (2009)
    Links: slides
  36. Title: Periodic Metro Scheduling
    Author(s): Evangelos Bampas, Georgia Kaouri, Michael Lampis and Aris Pagourtzis
    Conference: ATMOS 2006
    Links: online
  37. Title: Quantum Data and Control Made Easier
    Author(s): Michael Lampis, Kyriakos G. Ginis, Michalis A. Papakyriakou and Nikolaos S. Papaspyrou
    Conference: QPL 2006
    Journal: Electronic Notes on Theoretical Computer Science (2008)
    Links: draft

Community Service:
  • Conferences
    • I have served (or I am currently serving) on the PC of
    • I have been an external reviewer for the following conferences: ESA 2018, MFCS 2018, ICALP 2018, WG 2018, SWAT 2018, SAT 2018, STACS 2018, LATIN 2018, IWOCA 2018, ESA 2017, IPEC 2017, WG 2017, COCOON 2017, FCT 2017, EUROCOMB 2017, ISAAC 2016, IPEC 2016, WAOA 2016, ESA 2016, MFCS 2016, ICALP 2016, SODA 2016, ISCO 2016, IWOCA 2016, ICALP 2015, IPEC 2015, SoCG 2015, STACS 2015, WADS 2015, ESA 2014, ISAAC 2014, SODA 2014, WG 2014, CCC 2013, CIAC 2013, FAW-AAIM 2013, FCT 2013, WADS 2013, ESA 2012, SWAT 2012, TAMC 2012, MFCS 2011, ICALP 2011, IPEC 2010, WG 2010, APPROX 2010, SIROCCO 2010, IWPEC 2009, WAOA 2008, CiE 2008
  • Journals
    • I have been an external reviewer for the following journals: Theoretical Computer Science (x14), Discrete Applied Mathematics (x2), Journal of Computer and System Sciences (x2), SIAM Journal on Discrete Mathematics (x3), ACM Transactions on Algorithms (x3), Logical Methods in Computer Science, Discrete Optimization (x2), Information Processing Letters, Journal of Discrete Algorithms

Dissertation:
  • Structural Parameterizations of Hard Graph Problems (full text). September 2011, Graduate Center, CUNY. Advisor: Amotz Bar-Noy.

Other Talks:
  • Invited Keynote: ACAC 2016, Athens, Aug 2016. "Trading Time for Approximation" (slides)
  • KAIST, South Korea, May 13th 2014. "Parameterized Approximation Schemes Using Graph Widths" (slides)
  • New York University, May 3rd 2013. "Baby steps towards TSP inapproximability" (slides)
  • Masaryk University, Brno, March 11th 2013. "Model Checking Lower Bounds for Simple Graphs" (slides)
  • University of Bonn, January 22nd 2013. "Improved Inapproximability for TSP: The Role of Bounded Occurrence CSPs" (slides)
  • New York Colloquium on Algorithms and Complexity, CUNY Graduate Center, November 17th 2011. "The Landscape of Structural Graph Parameters" (slides).
  • Royal Holloway University of London, Computer Science Department Algorithms Seminar, July 13th 2010. "Algorithmic Meta-Theorems for Restrictions of Treewidth" (slides).
  • Royal Holloway University of London, Computer Science Department Algorithms Seminar, June 1st 2009. "On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures" (Based on joint work with Georgia Kaouri and Valia Mitsou)
  • Athens Colloquium on Algorithms and Complexity (ACAC) 2006: "On the Relation Between Vehicle Scheduling and Path Coloring", August 22nd, 2006 (Based on joint work with Evangelos Bampas, Georgia Kaouri, Aris Pagourtzis) (Slides)