Improved approximation algorithms for minimum power covering problems
From MaRDI portal
Publication:5919677
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
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