A note on two source location problems

Guy Kortsarz, Zeev Nutov

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

We consider Source Location (SL) problems: given a capacitated network G = (V, E), cost c (v) and a demand d (v) for every v ∈ V, choose a min-cost S ⊆ V so that λ (v, S) ≥ d (v) holds for every v ∈ V, where λ (v, S) is the maximum flow value from v to S. In the directed variant, we have demands din (v) and dout (v) and we require λ (S, v) ≥ din (v) and λ (v, S) ≥ dout (v). Undirected SL is (weakly) NP-hard on stars with r (v) = 0 for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected SL admit a (ln D + 1)-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected SL on trees with running time O (| V | Δ3), where Δ = maxv ∈ V d (v). This algorithm is used to derive a linear time algorithm for undirected SL with Δ ≤ 3. We also consider the Single Assignment Source Location (SASL) where every v ∈ V should be assigned to a single node s (v) ∈ S. While the undirected SASL is in P, we give a (ln | V | + 1)-approximation algorithm for the directed case, and show that this is tight, unless P = NP.

Original languageEnglish (US)
Pages (from-to)520-525
Number of pages6
JournalJournal of Discrete Algorithms
Volume6
Issue number3
DOIs
StatePublished - Sep 1 2008

Fingerprint

Location Problem
Approximation algorithms
Approximation Algorithms
Costs
Assignment
Maximum Flow
Linear-time Algorithm
Stars
Star
NP-complete problem
Choose
Vertex of a graph

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Approximation
  • Flow
  • Location
  • Source

Cite this

Kortsarz, Guy ; Nutov, Zeev. / A note on two source location problems. In: Journal of Discrete Algorithms. 2008 ; Vol. 6, No. 3. pp. 520-525.
@article{eec123c3337d4e7a822b7a871b895ddf,
title = "A note on two source location problems",
abstract = "We consider Source Location (SL) problems: given a capacitated network G = (V, E), cost c (v) and a demand d (v) for every v ∈ V, choose a min-cost S ⊆ V so that λ (v, S) ≥ d (v) holds for every v ∈ V, where λ (v, S) is the maximum flow value from v to S. In the directed variant, we have demands din (v) and dout (v) and we require λ (S, v) ≥ din (v) and λ (v, S) ≥ dout (v). Undirected SL is (weakly) NP-hard on stars with r (v) = 0 for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected SL admit a (ln D + 1)-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected SL on trees with running time O (| V | Δ3), where Δ = maxv ∈ V d (v). This algorithm is used to derive a linear time algorithm for undirected SL with Δ ≤ 3. We also consider the Single Assignment Source Location (SASL) where every v ∈ V should be assigned to a single node s (v) ∈ S. While the undirected SASL is in P, we give a (ln | V | + 1)-approximation algorithm for the directed case, and show that this is tight, unless P = NP.",
keywords = "Approximation, Flow, Location, Source",
author = "Guy Kortsarz and Zeev Nutov",
year = "2008",
month = "9",
day = "1",
doi = "10.1016/j.jda.2006.12.010",
language = "English (US)",
volume = "6",
pages = "520--525",
journal = "Journal of Discrete Algorithms",
issn = "1570-8667",
publisher = "Elsevier",
number = "3",

}

A note on two source location problems. / Kortsarz, Guy; Nutov, Zeev.

In: Journal of Discrete Algorithms, Vol. 6, No. 3, 01.09.2008, p. 520-525.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A note on two source location problems

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2008/9/1

Y1 - 2008/9/1

N2 - We consider Source Location (SL) problems: given a capacitated network G = (V, E), cost c (v) and a demand d (v) for every v ∈ V, choose a min-cost S ⊆ V so that λ (v, S) ≥ d (v) holds for every v ∈ V, where λ (v, S) is the maximum flow value from v to S. In the directed variant, we have demands din (v) and dout (v) and we require λ (S, v) ≥ din (v) and λ (v, S) ≥ dout (v). Undirected SL is (weakly) NP-hard on stars with r (v) = 0 for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected SL admit a (ln D + 1)-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected SL on trees with running time O (| V | Δ3), where Δ = maxv ∈ V d (v). This algorithm is used to derive a linear time algorithm for undirected SL with Δ ≤ 3. We also consider the Single Assignment Source Location (SASL) where every v ∈ V should be assigned to a single node s (v) ∈ S. While the undirected SASL is in P, we give a (ln | V | + 1)-approximation algorithm for the directed case, and show that this is tight, unless P = NP.

AB - We consider Source Location (SL) problems: given a capacitated network G = (V, E), cost c (v) and a demand d (v) for every v ∈ V, choose a min-cost S ⊆ V so that λ (v, S) ≥ d (v) holds for every v ∈ V, where λ (v, S) is the maximum flow value from v to S. In the directed variant, we have demands din (v) and dout (v) and we require λ (S, v) ≥ din (v) and λ (v, S) ≥ dout (v). Undirected SL is (weakly) NP-hard on stars with r (v) = 0 for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected SL admit a (ln D + 1)-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected SL on trees with running time O (| V | Δ3), where Δ = maxv ∈ V d (v). This algorithm is used to derive a linear time algorithm for undirected SL with Δ ≤ 3. We also consider the Single Assignment Source Location (SASL) where every v ∈ V should be assigned to a single node s (v) ∈ S. While the undirected SASL is in P, we give a (ln | V | + 1)-approximation algorithm for the directed case, and show that this is tight, unless P = NP.

KW - Approximation

KW - Flow

KW - Location

KW - Source

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

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

U2 - 10.1016/j.jda.2006.12.010

DO - 10.1016/j.jda.2006.12.010

M3 - Article

AN - SCOPUS:47549106704

VL - 6

SP - 520

EP - 525

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

SN - 1570-8667

IS - 3

ER -