文摘
We propose two graph problems: the k Most Beneficial New Edges (kMBNE), and the k Most Lethal Existing Edges (kMLEE). First, we prove that kMBNE and kMLEE are inapproximable. It is hard to find even an approximate solution (with constant approximation ratio), let alone find the exact solution. For both kMBNE and kMLEE, we develop polynomial-time heuristic algorithms that give high-quality solutions on real flow graphs. Moreover, we propose several pruning and optimization techniques to speedup our proposed algorithms.