Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

In English

Författare

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.

Avdelning/ar

  • Computer Science

Publiceringsår

2003

Språk

Engelska

Sidor

544-553

Publikation/Tidskrift/Serie

Lecture Notes in Computer Science (Algorithms and Computation)

Volym

2906

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Conference name

14th International Symposium, ISAAC 2003

Conference date

2003-12-15 - 2003-12-17

Conference place

Kyoto, Japan

Status

Published

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

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