Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.22
URN: urn:nbn:de:0030-drops-161823
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16182/
Dvořák, Zdeněk
Approximation Metatheorems for Classes with Bounded Expansion
| pdf-format: |
|
Abstract
We give a number of approximation metatheorems for monotone maximization problems expressible in the first-order logic, in substantially more general settings than previously known. We obtain- a constant-factor approximation algorithm in any class of graphs with bounded expansion,
- a QPTAS in any class with strongly sublinear separators, and
- a PTAS in any fractionally treewidth-fragile class (which includes all common classes with strongly sublinear separators).
Moreover, our tools also give an exact subexponential-time algorithm in any class with strongly sublinear separators.
BibTeX - Entry
@InProceedings{dvorak:LIPIcs.SWAT.2022.22,
author = {Dvo\v{r}\'{a}k, Zden\v{e}k},
title = {{Approximation Metatheorems for Classes with Bounded Expansion}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {22:1--22:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-236-5},
ISSN = {1868-8969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16182},
URN = {urn:nbn:de:0030-drops-161823},
doi = {10.4230/LIPIcs.SWAT.2022.22},
annote = {Keywords: bounded expansion, approximation, meta-algorithms}
}
| Keywords: | bounded expansion, approximation, meta-algorithms | |
| Seminar: | 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 22.06.2022 |
