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.

Approximation algorithms for buy-at-bulk geometric network design

På svenska

Author

  • 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.

Department/s

  • Computer Science

Publishing year

2011

Language

English

Pages

1949-1969

Publication/Series

Algorithms and data structures / Lecture notes in computer science

Volume

5664

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

11th International Symposium, WADS 2009

Conference date

2009-08-21 - 2009-08-23

Conference place

Banff, Canada

Status

Published

Project

  • VR 2008-4649

ISBN/ISSN/Other

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