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