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.


Conference Publications:
  1. Michael Lampis, "Model Checking Lower Bounds for Simple Graphs". In ICALP 2013, Track A. (draft,slides)
  2. Michael Lampis, "Improved Inapproximability for TSP". In APPROX 2012. (draft, slides)
  3. Michael Lampis, Valia Mitsou and Karolina Soltys. "Scrabble is PSPACE-complete". In FUN with Algorithms 2012. (draft)
  4. Michael Lampis, "Parameterized Maximum Path Coloring", In IPEC 2011. (draft, slides)
  5. Michael Lampis. "Algorithmic Meta-Theorems for Restrictions of Treewidth", In ESA 2010.(draft, slides)
  6. Antonis Achilleos, Michael Lampis and Valia Mitsou. "Parameterized Modal Satisfiability". In ICALP 2010, Track B.(draft)
  7. Amotz Bar-Noy and Michael Lampis. "Online Maximum Directed Cut". In ISAAC 2009, Hawaii USA. (draft, slides)
  8. Amotz Bar-Noy, Panagiotis Cheilaris, Michael Lampis, Valia Mitsou and Stathis Zachos. "Ordered Coloring for Grids and Related Graphs". In SIROCCO 2009, Piran, Slovenia. (draft)
  9. Michael Lampis, Georgia Kaouri and Valia Mitsou. "On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures". In ISAAC 2008, Gold Coast, Australia. (draft, slides)
  10. Michael Lampis and Valia Mitsou. "The Ferry Cover Problem". In proceedings of FUN with Algorithms 2007 (slides, Electronic Edition).
  11. Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis. "Periodic Metro Scheduling". In ATMOS 2006 (Electronic Edition)
  12. Michael Lampis, Kyriakos G. Ginis, Nikolaos S. Papaspyrou. "Quantum Data and Control Made Easier". Workshop for Quantum Programming Languages, Oxford 2006. (Electronic Edition)

Journal publications:
  1. Michael Lampis, "Parameterized Maximum Path Coloring", to appear in Theoretical Computer Science (draft).
  2. Amotz Bar-Noy, Panagiotis Cheilaris, Michael Lampis, Valia Mitsou and Stathis Zachos. "Ordered Coloring for Grids and Related Graphs", Theoretical Computer Science (2012) special issue for SIROCCO 2009.
  3. Michael Lampis, "Algorithmic Meta-Theorems for Restrictions of Treewidth". Algorithmica 64(1): 19-37 (2012) special issue for IPEC 2010. (draft)
  4. Antonis Achilleos, Michael Lampis and Valia Mitsou. "Parameterized Modal Satisfiability". Algorithmica 64(1): 38-55 (2012) special issue for IPEC 2010. (draft)
  5. Amotz Bar-Noy and Michael Lampis. "Online Maximum Directed Cut". Journal of Combinatorial Optimization 24(1): 52-64 (2012) special issue for ISAAC 2009.
  6. Michael Lampis, "A kernel of order 2k-clogk for Vertex Cover". Information Processing Letters 111(23-24): 1089-1091 (2011) (draft)
  7. Gregory Gutin, Eun Jung Kim, Michael Lampis and Valia Mitsou. "Vertex Cover Problem Parameterized Above and Below Tight Bounds", Theory of Computing Systems 48(2):402-410 (2011). (draft)
  8. Michael Lampis, Georgia Kaouri and Valia Mitsou. "On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures", Discrete Optimization 8(1):129-138 (2011), Special issue on Parameterized Complexity (draft)
  9. Michael Lampis and Valia Mitsou. "The Ferry Cover Problem". Theory of Computing Systems, February 2009. (Electronic Edition).
  10. Michael Lampis, Kyriakos G. Ginis, Michalis A. Papakyriakou, Nikolaos S. Papaspyrou. "Quantum Data and Control Made Easier". Electr. Notes Theor. Comput. Sci. 210: 85-105 (2008) (Electronic Edition).

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

Other Talks:
  • 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)