ABSTRACT
The time complexity analysis of such polynomial time approximation scheme (PTAS) is based on the fact that the number of possible subsets, or solutions that are considered, is exponential in the size of these subsets. This chapter presents the technique of applying exhaustive enumeration to a modified instance. It discusses approximations obtained using linear programming relaxation for a given optimization problem. Any optimization problem can be solved optimally in polynomial, or even constant time, if the input size is some constant. The shifting technique that is applied to geometric problems is based on selecting the best solution over a set of feasible solutions. The layered graph approach was used to develop PTASs for several scheduling problems. Wu et al. applied enumeration on a compacted instance while developing a PTAS for minimum routing cost spanning trees. L. Golubchik et al. apply enumeration to a structured instance in solving the problem of data placement on disks.
