Approximation algorithms for buy-at-bulk geometric network design

Artur Czumaj; Jurek Czyzowicz; Leszek Ga̧sieniec; Jesper Andreas Jansson; Andrzej Lingas; Pawel Zylinski

doi:10.1142/S0129054111009148

Approximation algorithms for buy-at-bulk geometric network design

Artur Czumaj, Jurek Czyzowicz, Leszek Ga̧sieniec, Jesper Andreas Jansson, Andrzej Lingas, Pawel Zylinski

Research output: Journal article publication › Journal article › Academic research › peer-review

1 Citation (Scopus)

Abstract

The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper, we consider geometric versions of the problem, where all points in a Euclidean space are candidates for network nodes, and present the first general approach for solving them. 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 a single sink and low capacity links, we design fast polynomial-time, low-constant approximation algorithms.

Original language	English
Pages (from-to)	1949-1969
Number of pages	21
Journal	International Journal of Foundations of Computer Science
Volume	22
Issue number	8
DOIs	https://doi.org/10.1142/S0129054111009148
Publication status	Published - 1 Dec 2011
Externally published	Yes

Keywords

approximation algorithm
belt decomposition
buy-at-bulk
dynamic programming
Geometric networks
Hanan grid
quasi-polynomial- time approximation scheme (QPTAS)

ASJC Scopus subject areas

Computer Science (miscellaneous)

More information

10.1142/S0129054111009148

Cite this

@article{0413628beb844251be3c64e02c211014,

title = "Approximation algorithms for buy-at-bulk geometric network design",

abstract = "The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper, we consider geometric versions of the problem, where all points in a Euclidean space are candidates for network nodes, and present the first general approach for solving them. 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 a single sink and low capacity links, we design fast polynomial-time, low-constant approximation algorithms.",

keywords = "approximation algorithm, belt decomposition, buy-at-bulk, dynamic programming, Geometric networks, Hanan grid, quasi-polynomial- time approximation scheme (QPTAS)",

author = "Artur Czumaj and Jurek Czyzowicz and Leszek G{\c a}sieniec and Jansson, {Jesper Andreas} and Andrzej Lingas and Pawel Zylinski",

year = "2011",

month = dec,

day = "1",

doi = "10.1142/S0129054111009148",

language = "English",

volume = "22",

pages = "1949--1969",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "8",

}

TY - JOUR

T1 - Approximation algorithms for buy-at-bulk geometric network design

AU - Czumaj, Artur

AU - Czyzowicz, Jurek

AU - Ga̧sieniec, Leszek

AU - Jansson, Jesper Andreas

AU - Lingas, Andrzej

AU - Zylinski, Pawel

PY - 2011/12/1

Y1 - 2011/12/1

N2 - The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper, we consider geometric versions of the problem, where all points in a Euclidean space are candidates for network nodes, and present the first general approach for solving them. 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 a single sink and low capacity links, we design fast polynomial-time, low-constant approximation algorithms.

AB - The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper, we consider geometric versions of the problem, where all points in a Euclidean space are candidates for network nodes, and present the first general approach for solving them. 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 a single sink and low capacity links, we design fast polynomial-time, low-constant approximation algorithms.

KW - approximation algorithm

KW - belt decomposition

KW - buy-at-bulk

KW - dynamic programming

KW - Geometric networks

KW - Hanan grid

KW - quasi-polynomial- time approximation scheme (QPTAS)

UR - http://www.scopus.com/inward/record.url?scp=84855762919&partnerID=8YFLogxK

U2 - 10.1142/S0129054111009148

DO - 10.1142/S0129054111009148

M3 - Journal article

SN - 0129-0541

VL - 22

SP - 1949

EP - 1969

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 8

ER -

Approximation algorithms for buy-at-bulk geometric network design

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this