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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Approximation Algorithms for the Capacitated Min-Max and Minimum Graph Cover Problems

  • Jiafeng Xiong,
  • Zhaohui Liu,
  • Wei Yu

摘要

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.