加载中…
In the - ( -) problem we are given a graph with activation costs for every edge , a source-sink pair , and an integer . The goal is to compute an edge set of internally node disjoint -paths of minimum activation cost . The problem admits an easy -approximation algorithm. Alqahtani and Erlebach [CIAC, pages 1-12, 2013] claimed that Activation 2-DP admits a -approximation algorithm. Their proof has an error, and we will show that the approximation ratio of their algorithm is at least . We will then give a different algorithm with approximation ratio .

生成讲解博客的中文版本

生成AI智能校验的中文版本