QQ客服 官方微博 反馈留言

	From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
	Chalermsook, Parinya1,2; Cygan, Marek; Kortsarz, Guy3; Laekhanukit, Bundit4,5; Manurangsi, Pasin6; Nanongkai, Danupon7; Trevisan, Luca6,8
	2017
关键词	Fixed Parameter Tractability Hardness of Approximation Clique Set Cover Dominating Set
DOI	10.1109/FOCS.2017.74
页码	743-754
英文摘要	We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = omega(1))?
会议录出版者	IEEE
会议录出版地	345 E 47TH ST, NEW YORK, NY 10017 USA
语种	英语
WOS研究方向	Computer Science ; Engineering
WOS记录号	WOS:000417425300065
内容类型	会议论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/3352]
专题	上海财经大学
作者单位	1.Aalto Univ, CS, Espoo, Finland; 2.Univ Warsaw, Informat Inst, Warsaw, Poland; 3.Rutgers Univ Camden, CS, Camden, NJ USA; 4.Weizmann Inst Sci, Math & CS, Rehovot, Israel; 5.Shanghai Univ Finance & Econ, ITCS, Shanghai, Peoples R China; 6.Univ Calif Berkeley, EECS, Berkeley, CA USA; 7.KTH Royal Inst Technol, CSC, Stockholm, Sweden; 8.Univ Calif Berkeley, Simons Inst Theory Comp, Berkeley, CA USA
推荐引用方式 GB/T 7714	Chalermsook, Parinya,Cygan, Marek,Kortsarz, Guy,et al. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More[C]. 见:.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。