Minimum Cost Source Location Problems with Flow Requirements

by: Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige

LATIN 2006: Theoretical Informatics (2006), pp. 769-780.

View FullText article

Springer (DOI)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

NeilInCanadia

Find related articles with these CiteULike tags

source_location

Abstract

In this paper, we consider source location problems and their generalizations with three connectivity requirements λ, κ and . We show that the source location problem with edge-connectivity requirement λ in undirected networks is strongly NP-hard, and that no source location problems with three connectivity requirements in undirected/directed networks are approximable within a ratio of , unless NP has an -time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+ln D)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions.

@incollection{citeulike:1777362, abstract = {In this paper, we consider source location problems and their generalizations with three connectivity requirements λ, κ and . We show that the source location problem with edge-connectivity requirement λ in undirected networks is strongly NP-hard, and that no source location problems with three connectivity requirements in undirected/directed networks are approximable within a ratio of , unless NP has an -time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+ln D)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions.}, author = {Sakashita, Mariko and Makino, Kazuhisa and Fujishige, Satoru }, citeulike-article-id = {1777362}, doi = {10.1007/11682462\_70}, journal = {LATIN 2006: Theoretical Informatics}, keywords = {source\_location}, pages = {769--780}, posted-at = {2007-10-17 03:03:24}, priority = {2}, title = {Minimum Cost Source Location Problems with Flow Requirements}, url = {http://dx.doi.org/10.1007/11682462\_70}, year = {2006} }

RIS record

TY - CHAP ID - citeulike:1777362 L3 - citeulike-article-id:1777362 TI - Minimum Cost Source Location Problems with Flow Requirements JF - LATIN 2006: Theoretical Informatics SP - 769 EP - 780 N2 - In this paper, we consider source location problems and their generalizations with three connectivity requirements λ, κ and . We show that the source location problem with edge-connectivity requirement λ in undirected networks is strongly NP-hard, and that no source location problems with three connectivity requirements in undirected/directed networks are approximable within a ratio of , unless NP has an -time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+ln D)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions. KW - source_location AU - Sakashita, Mariko AU - Makino, Kazuhisa AU - Fujishige, Satoru PY - 2006/// UR - http://dx.doi.org/10.1007/11682462_70 ER -

RIS BibTeX