conditional hardness of approximating satisfiable max 3csp-q

ISCAS OpenIR > 2009年期刊/会议论文

	conditional hardness of approximating satisfiable max 3csp-q
	Tang Linqing
	2009
会议名称	20th International Symposium on Algorithms and Computations (ISAAC 2009)
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
页码	923-932
会议日期	DEC 16-18,
会议地点	Honolulu, HI
收录类别	istp,ei
出版地	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
出版者	ALGORITHMS AND COMPUTATION, PROCEEDINGS
ISSN	0302-9743
ISBN	978-3-642-10630-9
部门归属	Tang, Linqing Chinese Acad Sci, State Key Lab Comp Sci, Inst Software, Beijing 100080, Peoples R China.
摘要	In this article, we study the approximability of satisfiable Max 3CSP-q for q > 3 be a prime. We give a (1/q + 1/q(2) - 1/q(3)) + epsilon-hardness result for approximate Max 3CSP-q even on satisfiable instances, conditioned on Khots d-to-1 Conjecture, for any finite constant integer d < q/2.
关键词	Computer Operating Procedures Hardness
主办者	Univ Hawaii, Univ Texas Dallas
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/8202
专题	2009年期刊/会议论文
推荐引用方式 GB/T 7714	Tang Linqing. conditional hardness of approximating satisfiable max 3csp-q[C]. HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY:ALGORITHMS AND COMPUTATION, PROCEEDINGS,2009:923-932.