The approximation algorithms for a class of multiple-choice problem

详细信息    查看全文

• 作者：Yin Wang^a ; ^{Yinaywang@stu.xjtu.edu.cn} ; Yinfeng Xu^a ; ^b
• 关键词：Color-spanning objects ; Computational geometry ; Approximation algorithm ; The smallest enclosing problem
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：22 November 2016
• 年：2016
• 卷：654
• 期：Complete
• 页码：164-174
• 全文大小：973 K
• 卷排序：654

文摘

A 2-approximate for SECSC is proposed without FCVD. Comparing using FCVD, ours is a good approximate for MDCS and much better in RdRd. Even when d=3d=3 or the demands of each color are more than 1, the worst time cost is still O(n2)O(n2). We find a 6-factor algorithm for PSPCHCS with time of O(n2+nmlog⁡n)O(n2+nmlog⁡n), which is better than previous results.