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.

Approximation algorithms for buy-at-bulk geometric network design

In English

Författare

  • Artur Czumaj
  • Jurek Czyzowicz
  • Leszek Gasieniec
  • Jesper Jansson
  • Andrzej Lingas
  • Pawel Zylinski

Summary, in English

The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper we consider the geometric version of the problem, where all points in a Euclidean space are candidates for network nodes. We present the first general approach for geometric versions of basic variants of the buy-at-bulk network design problem. It enables us to obtain quasi-polynomial-time approximation schemes for basic variants of the buy-at-bulk geometric network design problem with polynomial total demand. Then, for instances with few sinks and low capacity links, we design very fast polynomial-time low-constant approximations algorithms.

Avdelning/ar

  • Computer Science

Publiceringsår

2011

Språk

Engelska

Sidor

1949-1969

Publikation/Tidskrift/Serie

Algorithms and data structures / Lecture notes in computer science

Volym

5664

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Conference name

11th International Symposium, WADS 2009

Conference date

2009-08-21 - 2009-08-23

Conference place

Banff, Canada

Status

Published

Projekt

  • VR 2008-4649

ISBN/ISSN/Övrigt

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 3-642-03366-0