DocumentCode :
2203322
Title :
P-complete problems and approximate solutions
Author :
Sahni, Sartaj ; Gonzales, Teofilo
fYear :
1974
fDate :
14-16 Oct. 1974
Firstpage :
28
Lastpage :
32
Abstract :
We study the class of P-Complete problems and show the following: i) for any constant ε ≫0 there is a P-complete problem for which an ε-approximate solution can be found in linear time ii) there exist P-Complete problems for which linear time approximate solutions that get closer and closer to the optimal (with increasing problem size) can be found iii) there exist P-Complete problems for which the approximation problems are also P-Complete.
Keywords :
Approximation algorithms; Computer science; Ear; Polynomials; Terminology; Traveling salesman problems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Switching and Automata Theory, 1974., IEEE Conference Record of 15th Annual Symposium on
Conference_Location :
USA
ISSN :
0272-4847
Type :
conf
DOI :
10.1109/SWAT.1974.22
Filename :
4569755
Link To Document :
بازگشت