Advanced

Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

Czumaj, A; Lingas, Andrzej LU and Nilsson, J (2003) 14th International Symposium, ISAAC 2003 In Lecture Notes in Computer Science (Algorithms and Computation) 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Lecture Notes in Computer Science (Algorithms and Computation)
volume
2906
pages
544 - 553
publisher
Springer
conference name
14th International Symposium, ISAAC 2003
external identifiers
  • wos:000188242500056
  • scopus:35248840531
ISSN
1611-3349
0302-9743
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
2007-08-28 10:33:59
date last changed
2018-05-29 10:02:24
@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         = {1611-3349},
  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},
  volume       = {2906},
  year         = {2003},
}