Approximating source location and star survivable network problems

Guy Kortsarz, Zeev Nutov

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

In Source Location (SL) problems the goal is to select a minimum cost source set S ⊆ V such that the connectivity (or flow) ψ(S, v) from S to any node v is at least the demand dv of v. In many SL problems ψ(S, v) = dv if v ∈ S, so the demand of nodes selected to S is completely satisfied. In a variant suggested recently by Fukunaga [7], every node v selected to S gets a “bonus” pv ≤ dv, and ψ(S, v) = pv + κ(S \ {v}, v) if v ∈ S and ψ(S, v) = κ(S, v) otherwise, where κ(S, v) is the maximum number of internally disjoint (S, v)-paths. While the approximability of many SL problems was seemingly settled to Θ(ln d(V )) in [20], for his variant on undirected graphs Fukunaga achieved ratio O(k ln k), where k = maxvV dv is the maximum demand. We improve this by achieving ratio min{p ln k, k} · O(ln k) for a more general version with node capacities, where p = maxv∈V pv is the maximum bonus. In particular, for the most natural case p = 1 we improve the ratio from O(k ln k) to O(ln2 k). To derive these results, we consider a particular case of the Survivable Network (SN) problem when all edges of positive cost form a star. We obtain ratio O(min{ln n, ln2 k}) for this variant, improving over the best ratio known for the general case O(k3 ln n) of Chuzhoy and Khanna [3]. In addition, we show that directed SL with unit costs is Ω(log n)-hard to approximate even for 0, 1 demands, while SL with uniform demands can be solved in polynomial time. Finally, we obtain a logarithmic ratio for a generalization of SL where we also have edge-costs and flow-cost bounds {bv: v ∈ V }, and require that the minimum cost of a flow of value dv from S to every node v is at most bv.

שפה מקוריתאנגלית
כותר פרסום המארחGraph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015, Revised Papers
עורכיםErnst W. Mayr
מוציא לאורSpringer Verlag
עמודים203-218
מספר עמודים16
מסת"ב (מודפס)9783662531730
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2016
אירוע41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 - Garching, גרמניה
משך הזמן: 17 יוני 201519 יוני 2015

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך9224 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015
מדינה/אזורגרמניה
עירGarching
תקופה17/06/1519/06/15

הערה ביבליוגרפית

Publisher Copyright:
© Springer International Publishing Switzerland 2016.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating source location and star survivable network problems'. יחד הם יוצרים טביעת אצבע ייחודית.

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