Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
; and
organization
publishing date
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}},
}