Improved approximation algorithms for minimum power covering problems

Gruia Calinescu, Guy Kortsarz, 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 two network design problems under the power minimization criteria. In both problems we are given a graph G=(V,E) with edge costs and a set T⊆V of terminals. The goal is to find a minimum power edge subset F⊆E such that the graph H=(V,F) satisfies some prescribed requirements. In the Min-Power Edge-Cover problem, H should contain an edge incident to every terminal. Using the Iterative Randomized Rounding (IRR) method, we give an algorithm with expected approximation ratio 1.41; the ratio is reduced to 73/60 < 1.217 when T is an independent set in G. In the case of unit costs we also achieve ratio 73/60, and in addition give a simple efficient combinatorial algorithm with ratio 5/ 4. For all these NP-hard problems the previous best known ratio was 3/ 2. In the related Min-Power Terminal Backup problem, H should contain a path from every t∈T to some node in T\{t}. We obtain ratio 3/ 2 for this NP-hard problem, improving the trivial ratio of 2.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفApproximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers
المحررونLeah Epstein, Thomas Erlebach
ناشرSpringer Verlag
الصفحات134-148
عدد الصفحات15
رقم المعيار الدولي للكتب (المطبوع)9783030046927
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2018
الحدث16th Workshop on Approximation and Online Algorithms, WAOA 2018 - Helsinki, فنلندا
المدة: ٢٣ أغسطس ٢٠١٨٢٤ أغسطس ٢٠١٨

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

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

!!Conference

!!Conference16th Workshop on Approximation and Online Algorithms, WAOA 2018
الدولة/الإقليمفنلندا
المدينةHelsinki
المدة٢٣/٠٨/١٨٢٤/٠٨/١٨

ملاحظة ببليوغرافية

Funding Information:
Partially supported by NSF grant number 1540547. Gruia and Zeev thank Neil Olver for many useful discussions. Also, Gruia and Zeev acknowledge the support of the Hausdorff Trimester Program for Combinatorial Optimization (held at the Hausdorff Research Institute for Mathematics, University of Bonn).

Funding Information:
Partially supported by NSF grant number 1540547.

Funding Information:
Acknowledgment. Gruia and Zeev thank Neil Olver for many useful discussions. Also, Gruia and Zeev acknowledge the support of the Hausdorff Trimester Program for Combinatorial Optimization (held at the Hausdorff Research Institute for Mathematics, University of Bonn).

Publisher Copyright:
© Springer Nature Switzerland AG 2018.

بصمة

أدرس بدقة موضوعات البحث “Improved approximation algorithms for minimum power covering problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا