Title :
Inapproximability - some history and some open problems
Author_Institution :
R. Inst. of Technol., Stockholm, Sweden
Abstract :
The purpose of this talk is to give an overview of the status of some problems in approximability.
Keywords :
approximation theory; computability; computational complexity; optimisation; probability; theorem proving; Max-3Sat; NP-complete problem; inapproximability problem; optimization problem; polynomial time approximation algorithm; probability; proof system; satisfiability; Approximation algorithms; Computational complexity; History; NP-complete problem; Optimized production technology; Polynomials;
Conference_Titel :
Computational Complexity, 2003. Proceedings. 18th IEEE Annual Conference on
Print_ISBN :
0-7695-1879-6
DOI :
10.1109/CCC.2003.1214426
