A Better-Than-Greedy Algorithm for k-Set Multicover

详细信息    查看全文

• 作者：Toshihiro Fujito ; Hidekazu Kurahashi
• 刊名：Lecture Notes in Computer Science
• 出版年：2006
• 出版时间：2006
• 年：2006
• 卷：3879
• 期：1
• 页码：pp.176-189
• 全文大小：258 KB
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

The set multicover (MC) problem is a natural extension of the set cover problem s.t. each element requires to be covered a prescribed number of times (instead of just once as in set cover). The k-set multicover (k-MC) problem is a variant in which every subset is of size at most k. Due to the multiple coverage requirement, two versions of MC have been studied; the one in which each subset can be chosen only once (constrained MC) and the other in which each subset can be chosen any number of times (unconstrained MC). For both versions the best approximation algorithm known so far is the classical greedy heuristic, whose performance ratio is H(k), where H(k)= ∑_i=1k_{i=1}^{k} (1/i). It is no hard, however, to come up with a natural modification of the greedy algorithm such that the resulting performance is never worse, but could also be strictly better. This paper will verify that this is indeed the case by showing that such a modification leads to an improved performance ratio of H(k)–1/6 for both versions of k-MC.