Improved approximation algorithms for minimum power covering problems

Gruia Calinescu, Guy Kortsarz, Zeev Nutov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers
EditorsLeah Epstein, Thomas Erlebach
PublisherSpringer Verlag
Pages134-148
Number of pages15
ISBN (Print)9783030046927
DOIs
StatePublished - Jan 1 2018
Event16th Workshop on Approximation and Online Algorithms, WAOA 2018 - Helsinki, Finland
Duration: Aug 23 2018Aug 24 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11312 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other16th Workshop on Approximation and Online Algorithms, WAOA 2018
CountryFinland
CityHelsinki
Period8/23/188/24/18

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Approximation algorithms
  • Edge-cover
  • Iterative randomized rounding
  • Minimum power
  • Terminal backup

Fingerprint Dive into the research topics of 'Improved approximation algorithms for minimum power covering problems'. Together they form a unique fingerprint.

  • Cite this

    Calinescu, G., Kortsarz, G., & Nutov, Z. (2018). Improved approximation algorithms for minimum power covering problems. In L. Epstein, & T. Erlebach (Eds.), Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers (pp. 134-148). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11312 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-04693-4_9