Approximation Algorithms for the Capacitated Min-Max and Minimum Graph Cover Problems
摘要
In this paper we obtain improved approximation algorithms for the Capacitated Min-Max Graph Cover Problems and the first constant-factor approximation algorithms for the Capacitated Minimum Graph Cover Problems. These problems are capacitated extension of the well-known min-max and minimum graph cover problems. We introduce several new ideas to bring down the approximation ratios for the Capacitated Min-Max Graph Cover Problems. For the Capacitated Minimum Graph Cover Problems, the constant-factor approximation algorithms are achieved by an approximation-preserving reduction to the corresponding uncapacitated problems.