An O(k)-approximation algorithm for minimum power k edge disjoint st-paths

DOI10.1007/978-3-031-36978-0_23MaRDI QIDQ6149053zbMATH OpenOpenAlexFDO

Authors Zeev Nutov

Publication date 12 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.09373

zbMATH Keywords

edge disjoint \(st\)-pathsminimum powerwireless networks

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Abstract: In minimum power network design problems we are given an undirected graph $G=(V,E)$ with edge costs $c_e:einE$. The goal is to find an edge set $FsubseteqE$ that satisfies a prescribed property of minimum power $p_c(F)=su{m}_{vinV}max{c}_e:einFmboxisincidenttov$. In the Min-Power $k$ Edge Disjoint $st$-Paths problem $F$ should contains $k$ edge disjoint $st$-paths. The problem admits a $k$-approximation algorithm, and it was an open question whether it admits approximation ratio sublinear in $k$ even for unit costs. We give a $4sqrt2k$-approximation algorithm for general costs.

Recommendations

• A \(2\sqrt{2k}\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths
• On Minimum Power Connectivity Problems
• On minimum power connectivity problems
• Power Optimization for Connectivity Problems
• Power optimization for connectivity problems

Cites work

• Algorithmic Aspects of Minimum Energy Edge-Disjoint Paths in Wireless Networks
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Approximating minimum power covers of intersecting families and directed edge-connectivity problems
• Approximating Steiner networks with node-weights
• Approximation algorithms for disjoint st-paths with minimum activation cost
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Minimum activation cost node-disjoint paths in graphs with bounded treewidth
• On fixed cost k-flow problems
• On minimum power connectivity problems
• Power consumption in packet radio networks
• Power optimization for connectivity problems
• Survivable network activation problems
• Survivable network design problems in wireless networks

Cited in

(1)

• A \(2\sqrt{2k}\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths

This page was built for publication: An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths

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