The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

På svenska

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2003

Language

English

Pages

544-553

Publication/Series

Lecture Notes in Computer Science (Algorithms and Computation)

Volume

2906

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

14th International Symposium, ISAAC 2003

Conference date

2003-12-15 - 2003-12-17

Conference place

Kyoto, Japan

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 978-3-540-20695-8