A logarithmic approximation algorithm for the activation edge-multicover problem

DOI10.1016/J.TCS.2026.115945MaRDI QIDQ7266628zbMATH OpenFDO

Authors Zeev Nutov, Avner Huri, Guy Kortsarz

Publication date 15 June 2026

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

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115945

zbMATH Keywords

approximation algorithmminimum poweractivation problemedge multicover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A 4+ approximation for k-connected subgraphs
• An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
• An application of submodular flows
• An approximation algorithm for the fault tolerant metric facility location problem
• Approximating Steiner networks with node-weights
• Approximating activation edge-cover and facility location problems
• Approximating minimum power covers of intersecting families and directed edge-connectivity problems
• Approximating minimum power edge-multi-covers
• Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
• Approximating minimum-cost edge-covers of crossing biset-families
• Approximating minimum-power degree and connectivity problems
• Approximating node connectivity problems via set covers
• Approximation algorithms for connected dominating sets
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Ecken vom Grad n in minimalen n-fach zusammenhängenden Graphen
• Fault-tolerant facility location
• Fault-tolerant facility location: a randomized dependent LP-rounding algorithm
• Improved Approximation Algorithms for Uniform Connectivity Problems
• On minimum power connectivity problems
• On rooted node-connectivity problems
• Paths, Trees, and Flowers
• Power consumption in packet radio networks
• Power optimization for connectivity problems
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• Survivable network design problems in wireless networks
• The node-weighted steiner tree problem

This page was built for publication: A logarithmic approximation algorithm for the activation edge-multicover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7266628)