A note on two source location problems

Guy Kortsarz, Zeev Nutov

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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.

שפה מקוריתאנגלית
עמודים (מ-עד)520-525
מספר עמודים6
כתב עתJournal of Discrete Algorithms
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ספט׳ 2008

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A note on two source location problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי