Approximating minimum-power degree and connectivity problems

Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


Power optimization is a central issue in wireless network design. Given a (possibly directed) graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider several fundamental undirected network design problems under the power minimization criteria. Given a graph with edge costs and degree requirements {r(v):v ∈ V}, the Minimum-Power Edge-Multi-Cover ( ) problem is to find a minimum-power subgraph of so that the degree of every node v is at least r(v). We give an O(logn)-approximation algorithms for , improving the previous ratio O(log4 n) of [11]. This is used to derive an O(logn + α)-approximation algorithm for the undirected Minimum-Power k -Connected Subgraph ( ) problem, where is the best known ratio for the min-cost variant of the problem (currently, = O(In k) for n ≥ 2k2 and otherwise). Surprisingly, it shows that the min-power and the min-cost versions of the k -Connected Subgraph problem are equivalent with respect to approximation, unless the min-cost variant admits an o(logn)-approximation, which seems to be out of reach at the moment. We also improve the best known approximation ratios for small requirements. Specifically, we give a 3/2-approximation algorithm for with r(v) ∈ {0,1}, improving over the 2-approximation by [11], and a -approximation for the minimum-power 2-Connected and 2-Edge-Connected Subgraph problems, improving the 4-approximation by [4]. Finally, we give a 4 r max -approximation algorithm for the undirected Minimum-Power Steiner Network ( ) problem: find a minimum-power subgraph that contains r(u,v) pairwise edge-disjoint paths for every pair u,v of nodes.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفLATIN 2008
العنوان الفرعي لمنشور المضيفTheoretical Informatics - 8th Latin American Symposium, Proceedings
ناشرSpringer Verlag
عدد الصفحات13
رقم المعيار الدولي للكتب (المطبوع)3540787720, 9783540787723
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2008
الحدث8th Latin American Theoretical INformatics Symposium, LATIN 2008 - Buzios, البرازيل
المدة: ٧ أبريل ٢٠٠٨١١ أبريل ٢٠٠٨

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت4957 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference8th Latin American Theoretical INformatics Symposium, LATIN 2008


أدرس بدقة موضوعات البحث “Approximating minimum-power degree and connectivity problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا