Primal-dual approximation algorithms for integral flow and multicut in trees |
| |
Authors: | N Garg V V Vazirani M Yannakakis |
| |
Affiliation: | (1) Department of Computer Science and Engineering, Indian Institute of Technology, New Delhi, India;(2) AT&T Bell Laboratories, 07974 Murray Hill, NJ, USA |
| |
Abstract: | We study the maximum integral multicommodity flow problem and the minimum multicut problem restricted to trees. This restriction
is quite rich and contains as special cases classical optimization problems such as matching and vertex cover for general
graphs. It is shown that both the maximum integral multicommodity flow and the minimum multicut problem are NP-hard and MAX
SNP-hard on trees, although the maximum integral flow can be computed in polynomial time if the edges have unit capacity.
We present an efficient algorithm that computes a multicut and integral flow such that the weight of the multicut is at most
twice the value of the flow. This gives a 2-approximation algorithm for minimum multicut and a 1/2-approximation algorithm
for maximum integral multicommodity flow in trees. |
| |
Keywords: | Integral multicommodity flow Multicut Approximation algorithm MAX SNP-hard |
本文献已被 SpringerLink 等数据库收录! |