Home
Research
Teaching
Links
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.

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: 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
  2. Title: Treewidth with a Quantifier Alternation Revisited
    Author(s): Michael Lampis and Valia Mitsou
    Conference: IPEC 2017
    Links: draft
  3. Title: On the Parameterized Complexity of Red-Blue Points Separation
    Author(s): Edouard Bonnet, Panos Giannopoulos, and Michael Lampis
    Conference: IPEC 2017
    Links: draft
  4. 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)
  5. 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
  6. Title: Parameterized Power Vertex Cover
    Author(s): Eric Angel, Evripidis Bampis, Bruno Escoffier, Michael Lampis
    Conference: WG 2016
    Links: draft, slides
  7. 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
  8. Title: Time-Approximation Trade-offs for Inapproximable Problems.
    Author(s): Edouard Bonnet, Michael Lampis and Vangelis Paschos
    Conference: STACS 2016
    Links: draft, slides (slides by Edouard Bonnet)
  9. Title: Complexity and Approximability for Parameterized CSPs
    Author(s): Holger Dell, Eunjung Kim, Michael Lampis, Valia Mitsou, Tobias Moemke
    Conference: IPEC 2015
    Journal: Algorithmica (2017)
    Links: draft
  10. Title: Parameterized Algorithms for Parity Games
    Author(s): Jakub Gajarsky, Michael Lampis, Kazuhisa Makino, Valia Mitsou, Sebastian Ordyniak
    Conference: MFCS 2015
    Links: draft
  11. Title: Parameterized Approximation Schemes Using Graph Widths
    Author(s): Michael Lampis
    Conference: ICALP 2014
    Links: draft, slides
  12. Title: Parameterized Edge Hamiltonicity
    Author(s): Michael Lampis, Kazuhisa Makino, Valia Mitsou and Yushi Uno
    Conference: WG 2014
    Journal: DAM (2017)
    Links: draft
  13. 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
  14. Title: New Inapproximability Bounds for TSP
    Author(s): Marek Karpinski, Michael Lampis and Richard Schmied
    Conference: ISAAC 2013
    Journal: JCSS (2015)
    Links: draft, slides
  15. Title: Parameterized Algorithms for Modular-Width
    Author(s): Jakub Gajarsky, Michael Lampis and Sebastian Ordyniak
    Conference: IPEC 2013
    Links: draft
  16. 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
  17. Title: Improved Inapproximability for TSP
    Author(s): Michael Lampis
    Conference: APPROX 2012
    Journal: Theory of Computing (2014)
    Links: draft, online, slides
  18. 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
  19. Title: A kernel of order 2k-clogk for Vertex Cover
    Author(s): Michael Lampis
    Journal:        Information Processing Letters (2011)
    Links: draft
  20. Title: Parameterized Maximum Path Coloring
    Author(s): Michael Lampis
    Conference: IPEC 2011
    Journal: Theoretical Computer Science (2013)
    Links: draft, slides
  21. Title: Algorithmic Meta-Theorems for Restrictions of Treewidth
    Author(s): Michael Lampis
    Conference: ESA 2010
    Journal: Algorithmica (2012)
    Links: draft, slides
  22. Title: Parameterized Modal Satisfiability
    Author(s): Antonis Achilleos, Michael Lampis and Valia Mitsou
    Conference: ICALP 2010
    Journal: Algorithmica (2012)
    Links: draft
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. Title: Periodic Metro Scheduling
    Author(s): Evangelos Bampas, Georgia Kaouri, Michael Lampis and Aris Pagourtzis
    Conference: ATMOS 2006
    Links: online
  29. 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 JGA 2017, FAW 2017, CIAC 2017, ISAAC 2015
    • I have been an external reviewer for the following conferences: 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 (x12), Discrete Applied Mathematics (x2), Journal of Computer and System Sciences (x2), SIAM Journal on Discrete Mathematics (x2), ACM Transactions on Algorithms, Logical Methods in Computer Science, Discrete Optimization (x2), Information Processing Letters

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)