Approximating activation edge-cover and facility location problems
From MaRDI portal
Publication:2166781
DOI10.1016/j.tcs.2022.07.026OpenAlexW2905594734MaRDI QIDQ2166781
Guy Kortsarz, Eli Shalom, Zeev Nutov
Publication date: 25 August 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1812.09880
approximation algorithmfacility locationminimum poweractivation edge-covergeneralized min-covering problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
- Power optimization for connectivity problems
- Approximating minimum-power edge-covers and 2,3-connectivity
- Approximation algorithms for combinatorial problems
- On the Lambert \(w\) function
- An analysis of the greedy algorithm for the submodular set covering problem
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- One for the price of two: a unified approach for approximating covering problems
- Packing-Based Approximation Algorithm for the k-Set Cover Problem
- A threshold of ln n for approximating set cover
- A Greedy Heuristic for the Set-Covering Problem
- A Tight Analysis of the Greedy Algorithm for Set Cover
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Tighter Bounds for Graph Steiner Tree Approximation
- Paths, Trees, and Flowers
- Steiner Tree Approximation via Iterative Randomized Rounding
- Matroids and integrality gaps for hypergraphic steiner tree relaxations
- Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search
- Improved approximation algorithms for minimum power covering problems
