DocumentCode :
2074381
Title :
Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique
Author :
Khot, Subhash
Author_Institution :
Georgia Inst. of Technol., Atlanta, GA, USA
fYear :
2004
fDate :
17-19 Oct. 2004
Firstpage :
136
Lastpage :
145
Abstract :
Assuming that NP
Keywords :
computational complexity; graph theory; polynomials; PTAS; bipartite clique; densest subgraph; graph min-bisection; minimum distance of code problem; polynomial; quasirandom PCP; query pattern; Approximation algorithms; Artificial intelligence; Binary codes; Bipartite graph; Computer science; Linear code; Polynomials; Vectors;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on
ISSN :
0272-5428
Print_ISBN :
0-7695-2228-9
Type :
conf
DOI :
10.1109/FOCS.2004.59
Filename :
1366233
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2074381
بازگشت