A 1.5-pproximation algorithms for activating 2 disjoint $st$-paths

July 24, 2023 Β· Declared Dead Β· πŸ› arXiv.org

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Zeev Nutov, Dawod Kahba arXiv ID 2307.12646 Category cs.DS: Data Structures & Algorithms Citations 1 Venue arXiv.org Last Checked 4 months ago
Abstract
In the $Activation$ $k$ $Disjoint$ $st$-$Paths$ ($Activation$ $k$-$DP$) problem we are given a graph $G=(V,E)$ with activation costs $\{c_{uv}^u,c_{uv}^v\}$ for every edge $uv \in E$, a source-sink pair $s,t \in V$, and an integer $k$. The goal is to compute an edge set $F \subseteq E$ of $k$ internally node disjoint $st$-paths of minimum activation cost $\displaystyle \sum_{v \in V}\max_{uv \in E}c_{uv}^v$. The problem admits an easy $2$-approximation algorithm. Alqahtani and Erlebach [CIAC, pages 1-12, 2013] claimed that Activation 2-DP admits a $1.5$-approximation algorithm. Their proof has an error, and we will show that the approximation ratio of their algorithm is at least $2$. We will then give a different algorithm with approximation ratio $1.5$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted