optimisation | Algorithms at UNSW

We focus on several areas in discrete optimisation. Our work includes algorithms for graph coloring, constraint satisfaction, global constraints, scheduling, and Satisfiability.

selected papers

Algorithmica

Serge Gaspers, and Edward J. Lee

Faster Graph Coloring in Polynomial Space

Algorithmica, 2023

DOI arXiv Bib

@article{GaspersL23,
  author = {Gaspers, Serge and Lee, Edward J.},
  title = {Faster Graph Coloring in Polynomial Space},
  journal = {Algorithmica},
  volume = {85},
  number = {2},
  pages = {584--609},
  year = {2023},
  url = {https://doi.org/10.1007/s00453-022-01034-7},
  doi = {10.1007/S00453-022-01034-7}
}

Handbook SAT

Armin Biere, Marijn Heule, Hans Maaren, and Toby Walsh

Handbook of Satisfiability - Second Edition

2021

DOI Bib

@book{BiereHMW21,
  editor = {Biere, Armin and Heule, Marijn and van Maaren, Hans and Walsh, Toby},
  title = {Handbook of Satisfiability - Second Edition},
  series = {Frontiers in Artificial Intelligence and Applications},
  volume = {336},
  publisher = {{IOS} Press},
  year = {2021},
  url = {https://doi.org/10.3233/FAIA336},
  doi = {10.3233/FAIA336},
  isbn = {978-1-64368-160-3}
}

JCSS

Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, and Stanislav Zivný

Backdoors into heterogeneous classes of SAT and CSP

Journal of Computer and System Sciences, 2017

DOI arXiv Bib

@article{GaspersMOSZ17,
  author = {Gaspers, Serge and Misra, Neeldhara and Ordyniak, Sebastian and Szeider, Stefan and Zivn{\'{y}}, Stanislav},
  title = {Backdoors into heterogeneous classes of {SAT} and {CSP}},
  journal = {Journal of Computer and System Sciences},
  volume = {85},
  pages = {38--56},
  year = {2017},
  url = {https://doi.org/10.1016/j.jcss.2016.10.007},
  doi = {10.1016/J.JCSS.2016.10.007}
}

IPEC

Serge Gaspers, Christos H. Papadimitriou, Sigve Hortemo Sæther, and Jan Arne Telle

On Satisfiability Problems with a Linear Structure

In 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, 2016

DOI arXiv Bib

@inproceedings{GaspersPST16,
  author = {Gaspers, Serge and Papadimitriou, Christos H. and S{\ae}ther, Sigve Hortemo and Telle, Jan Arne},
  editor = {Guo, Jiong and Hermelin, Danny},
  title = {On Satisfiability Problems with a Linear Structure},
  booktitle = {11th International Symposium on Parameterized and Exact Computation,
                    {IPEC} 2016, August 24-26, 2016, Aarhus, Denmark},
  series = {LIPIcs},
  volume = {63},
  pages = {14:1--14:14},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2016},
  url = {https://doi.org/10.4230/LIPIcs.IPEC.2016.14},
  doi = {10.4230/LIPICS.IPEC.2016.14}
}

IJCAI

Geoffrey Chu, Serge Gaspers, Nina Narodytska, Andreas Schutt, and Toby Walsh

On the Complexity of Global Scheduling Constraints under Structural Restrictions

In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, 2013

URL Bib

@inproceedings{ChuGNSW13,
  author = {Chu, Geoffrey and Gaspers, Serge and Narodytska, Nina and Schutt, Andreas and Walsh, Toby},
  editor = {Rossi, Francesca},
  title = {On the Complexity of Global Scheduling Constraints under Structural
                    Restrictions},
  booktitle = {{IJCAI} 2013, Proceedings of the 23rd International Joint Conference
                    on Artificial Intelligence, Beijing, China, August 3-9, 2013},
  pages = {503--509},
  publisher = {{IJCAI/AAAI}},
  year = {2013},
  url = {http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6878}
}

Handbook CSP

Francesca Rossi, Peter Beek, and Toby Walsh

Handbook of Constraint Programming

2006

URL Bib

@book{RossiBW06,
  editor = {Rossi, Francesca and van Beek, Peter and Walsh, Toby},
  title = {Handbook of Constraint Programming},
  series = {Foundations of Artificial Intelligence},
  volume = {2},
  publisher = {Elsevier},
  year = {2006},
  url = {https://www.sciencedirect.com/science/bookseries/15746526/2},
  isbn = {978-0-444-52726-4},
  timestamp = {Tue, 23 Jan 2024 13:25:47 +0100},
  biburl = {https://dblp.org/rec/reference/fai/2.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}