Improved approximation algorithms for minimum power covering problems

DOI10.1016/j.tcs.2019.07.010zbMath1435.68404OpenAlexW2902886251WikidataQ127534638 ScholiaQ127534638MaRDI QIDQ5919677

Zeev Nutov, Gruia Călinescu, Guy Kortsarz

Publication date: 18 October 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.07.010

zbMATH Keywords

graph theorycomplexity of algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating minimum power edge-multi-covers
• Power optimization for connectivity problems
• On minimum power connectivity problems
• Approximating minimum power covers of intersecting families and directed edge-connectivity problems
• Approximating minimum-power edge-covers and 2,3-connectivity
• The ellipsoid method and its consequences in combinatorial optimization
• Power assignment for \(k\)-connectivity in wireless ad hoc networks
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Energy-efficient wireless network design
• Approximate Max-Min Resource Sharing for Structured Concave Optimization
• Approximating the Generalized Terminal Backup Problem via Half-Integral Multiflow Relaxation
• On Min-Power Steiner Tree
• The Generalized Terminal Backup Problem
• Terminal Backup, 3D Matching, and Covering Cubic Graphs
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Paths, Trees, and Flowers
• Steiner Tree Approximation via Iterative Randomized Rounding
• Matroids and integrality gaps for hypergraphic steiner tree relaxations
• Algorithms - ESA 2003

This page was built for publication: Improved approximation algorithms for minimum power covering problems