Title :
P-complete problems and approximate solutions
Author :
Sahni, Sartaj ; Gonzales, Teofilo
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;
Conference_Titel :
Switching and Automata Theory, 1974., IEEE Conference Record of 15th Annual Symposium on
Conference_Location :
USA
DOI :
10.1109/SWAT.1974.22