Approximating minimum power edge-multi-covers

Nachshon Cohen, Zeev Nutov

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


Given an undirected graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider the following fundamental problem that arises in wireless network design. Given a graph G=(V,E) with edge costs and lower degree bounds {r(v):v∈V}, the Min-Power Edge-Multicover problem is to find a minimum-power subgraph J of G such that the degree of every node v in J is at least r(v). Let k=maxv∈Vr(v). For k=Ω(logn), the previous best approximation ratio for the problem was O(logn), even for uniform costs (Kortsarz et al. 2011). Our main result improves this ratio to O(logk) for general costs, and to O(1) for uniform costs. This also implies ratios O(logk) for the Min-Power k-Outconnected Subgraph and Ologklognn-k for the Min-Power k-Connected Subgraph problems; the latter is the currently best known ratio for the min-cost version of the problem when n≤k(k-1)2. In addition, for small values of k, we improve the previously best ratio k+1 to k+1/2.

שפה מקוריתאנגלית
עמודים (מ-עד)563-578
מספר עמודים16
כתב עתJournal of Combinatorial Optimization
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 אוק׳ 2015

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

Publisher Copyright:
© 2013, Springer Science+Business Media New York.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating minimum power edge-multi-covers'. יחד הם יוצרים טביעת אצבע ייחודית.

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