Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2208.09373 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909134224359424 |
|---|---|
| author | Nutov, Zeev |
| author_facet | Nutov, Zeev |
| contents | In minimum power network design problems we are given an undirected graph $G=(V,E)$ with edge costs $\{c_e:e \in E\}$. The goal is to find an edge set $F\subseteq E$ that satisfies a prescribed property of minimum power $p_c(F)=\sum_{v \in V} \max \{c_e: e \in F \mbox{ is incident to } v\}$. 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 $2\sqrt{2k}$-approximation algorithm for general costs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_09373 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths Nutov, Zeev Data Structures and Algorithms In minimum power network design problems we are given an undirected graph $G=(V,E)$ with edge costs $\{c_e:e \in E\}$. The goal is to find an edge set $F\subseteq E$ that satisfies a prescribed property of minimum power $p_c(F)=\sum_{v \in V} \max \{c_e: e \in F \mbox{ is incident to } v\}$. 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 $2\sqrt{2k}$-approximation algorithm for general costs. |
| title | An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2208.09373 |