Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
(2003) 14th International Symposium, ISAAC 2003 In Lecture Notes in Computer Science (Algorithms and Computation) 2906. p.544553 Abstract
 In this paper we present two novel generic schemes for approximation algorithms for optimization NPhard graph problems constrained to partial ktrees. Our first scheme yields deterministic polynomialtime algorithms achieving typically an approximation factor of k/log(1is an element of)n, where k = polylog(n). The second scheme yields randomized polynomialtime 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 polynomialtime approximation guarantees for the classical maximum independent set problem in partial trees.
Please use this url to cite or link to this publication:
http://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
 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
 16113349
 03029743
 ISBN
 9783540206958
 DOI
 10.1007/b94771
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 7a06b36c9bbd404baf2c8854af5871b2 (old id 289580)
 date added to LUP
 20070828 10:33:59
 date last changed
 20180529 10:02:24
@inproceedings{7a06b36c9bbd404baf2c8854af5871b2, abstract = {In this paper we present two novel generic schemes for approximation algorithms for optimization NPhard graph problems constrained to partial ktrees. Our first scheme yields deterministic polynomialtime algorithms achieving typically an approximation factor of k/log(1is an element of)n, where k = polylog(n). The second scheme yields randomized polynomialtime 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 polynomialtime 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 = {9783540206958}, issn = {16113349}, language = {eng}, pages = {544553}, 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}, }