exponential time algorithms | Algorithms at UNSW

In exponential time algorithms, we design and analyse algorithms for computationally intractable (typically NP-hard) problems. The aim is to reduce the running time to a moderately exponential function.

selected papers

J. ACM

Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh

Exact Algorithms via Monotone Local Search

Journal of the ACM, 2019

DOI arXiv Bib

@article{FominGLS19,
  author = {Fomin, Fedor V. and Gaspers, Serge and Lokshtanov, Daniel and Saurabh, Saket},
  title = {Exact Algorithms via Monotone Local Search},
  journal = {Journal of the {ACM}},
  volume = {66},
  number = {2},
  pages = {8:1--8:23},
  year = {2019},
  url = {https://doi.org/10.1145/3284176},
  doi = {10.1145/3284176}
}

ICALP

Serge Gaspers, and Edward J. Lee

Exact Algorithms via Multivariate Subroutines

In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, 2017

DOI arXiv Bib

@inproceedings{GaspersL17,
  author = {Gaspers, Serge and Lee, Edward J.},
  editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  title = {Exact Algorithms via Multivariate Subroutines},
  booktitle = {44th International Colloquium on Automata, Languages, and Programming,
                    {ICALP} 2017, July 10-14, 2017, Warsaw, Poland},
  series = {LIPIcs},
  volume = {80},
  pages = {69:1--69:13},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2017},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.69},
  doi = {10.4230/LIPICS.ICALP.2017.69}
}

JCSS

Serge Gaspers, and Gregory B. Sorkin

A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between

J. Comput. Syst. Sci., 2012

DOI arXiv Bib

@article{GaspersS12,
  author = {Gaspers, Serge and Sorkin, Gregory B.},
  title = {A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything
                    in between},
  journal = {J. Comput. Syst. Sci.},
  volume = {78},
  number = {1},
  pages = {305--335},
  year = {2012},
  url = {https://doi.org/10.1016/j.jcss.2011.05.010},
  doi = {10.1016/J.JCSS.2011.05.010}
}