Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
(2003) 14th International Symposium, ISAAC 2003 2906. p.544-553- Abstract
- In this paper we present two novel generic schemes for approximation algorithms for optimization NP-hard graph problems constrained to partial k-trees. Our first scheme yields deterministic polynomial-time algorithms achieving typically an approximation factor of k/log(1-is an element of)n, where k = polylog(n). The second scheme yields randomized polynomial-time algorithms achieving an approximation factor of k/logn for k = Omega(logn). Both our approximation methods lead to the best known approximation guarantees for some basic optimization problems. In particular, we obtain best known polynomial-time approximation guarantees for the classical maximum independent set problem in partial trees.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/289580
- author
- Czumaj, A ; Lingas, Andrzej LU and Nilsson, J
- organization
- publishing date
- 2003
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Lecture Notes in Computer Science (Algorithms and Computation)
- volume
- 2906
- pages
- 544 - 553
- publisher
- Springer
- conference name
- 14th International Symposium, ISAAC 2003
- conference location
- Kyoto, Japan
- conference dates
- 2003-12-15 - 2003-12-17
- external identifiers
-
- wos:000188242500056
- scopus:35248840531
- ISSN
- 0302-9743
- 1611-3349
- ISBN
- 978-3-540-20695-8
- DOI
- 10.1007/b94771
- project
- VR 2002-4049
- language
- English
- LU publication?
- yes
- id
- 7a06b36c-9bbd-404b-af2c-8854af5871b2 (old id 289580)
- date added to LUP
- 2016-04-01 11:57:41
- date last changed
- 2024-01-08 02:58:42
@inproceedings{7a06b36c-9bbd-404b-af2c-8854af5871b2, abstract = {{In this paper we present two novel generic schemes for approximation algorithms for optimization NP-hard graph problems constrained to partial k-trees. Our first scheme yields deterministic polynomial-time algorithms achieving typically an approximation factor of k/log(1-is an element of)n, where k = polylog(n). The second scheme yields randomized polynomial-time algorithms achieving an approximation factor of k/logn for k = Omega(logn). Both our approximation methods lead to the best known approximation guarantees for some basic optimization problems. In particular, we obtain best known polynomial-time approximation guarantees for the classical maximum independent set problem in partial trees.}}, author = {{Czumaj, A and Lingas, Andrzej and Nilsson, J}}, booktitle = {{Lecture Notes in Computer Science (Algorithms and Computation)}}, isbn = {{978-3-540-20695-8}}, issn = {{0302-9743}}, language = {{eng}}, pages = {{544--553}}, publisher = {{Springer}}, title = {{Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth}}, url = {{http://dx.doi.org/10.1007/b94771}}, doi = {{10.1007/b94771}}, volume = {{2906}}, year = {{2003}}, }