approximation algorithms | Algorithms at UNSW

Approximation algorithms cope with computationally intractable problems by producing solutions that are guaranteed to be not too far from optimal. Constant-factor approximation algorithms find solutions within a constant factor of the optimal solution. Approximation schemes allow to adjust the approximation factor arbitrarily close to 1 at the expense of slower running times.

A compendium of NP optimization problems

selected papers

SODA

Sayan Bandyapadhyay, Katie Clinch, William Lochet, Daniel Lokshtanov, Saket Saurabh, and Jie Xue

PTASes for Euclidean TSP with Unit Disk and Unit Square Neighborhoods

In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, 2025

DOI Bib

@inproceedings{BandyapadhyayCL25,
  author = {Bandyapadhyay, Sayan and Clinch, Katie and Lochet, William and Lokshtanov, Daniel and Saurabh, Saket and Xue, Jie},
  editor = {Azar, Yossi and Panigrahi, Debmalya},
  title = {PTASes for Euclidean {TSP} with Unit Disk and Unit Square Neighborhoods},
  booktitle = {Proceedings of the 2025 Annual {ACM-SIAM} Symposium on Discrete Algorithms,
                    {SODA} 2025, New Orleans, LA, USA, January 12-15, 2025},
  pages = {2326--2356},
  publisher = {{SIAM}},
  year = {2025},
  url = {https://doi.org/10.1137/1.9781611978322.78},
  doi = {10.1137/1.9781611978322.78},
  timestamp = {Tue, 28 Jan 2025 14:38:41 +0100},
  biburl = {https://dblp.org/rec/conf/soda/BandyapadhyayCL25.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

arXiv

Siddharth Barman, and Mashbat Suzuki

Compatibility of Fairness and Nash Welfare under Subadditive Valuations

CoRR, 2024

DOI arXiv Bib

@article{BarmanS24,
  author = {Barman, Siddharth and Suzuki, Mashbat},
  title = {Compatibility of Fairness and Nash Welfare under Subadditive Valuations},
  journal = {CoRR},
  volume = {abs/2407.12461},
  year = {2024},
  doi = {10.48550/ARXIV.2407.12461},
  eprinttype = {arXiv},
  eprint = {2407.12461}
}

STACS

Haris Aziz, and Bart Keijzer

Shapley meets Shapley

In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, 2014

DOI arXiv Bib

@inproceedings{AzizK14,
  author = {Aziz, Haris and de Keijzer, Bart},
  editor = {Mayr, Ernst W. and Portier, Natacha},
  title = {Shapley meets Shapley},
  booktitle = {31st International Symposium on Theoretical Aspects of Computer Science
                    {(STACS} 2014), {STACS} 2014, March 5-8, 2014, Lyon, France},
  series = {LIPIcs},
  volume = {25},
  pages = {99--111},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2014},
  url = {https://doi.org/10.4230/LIPIcs.STACS.2014.99},
  doi = {10.4230/LIPICS.STACS.2014.99}
}