Title: | Parameterized complexity and polynomial-time approximation schemes |

Author: | Huang, Xiuzhen |

Abstract: | According to the theory of NPcompleteness , many problems that have important realworld applications are NPhard . This excludes the possibility of solving them in polynomial time unless P=NP . A number of approaches have been proposed in dealing with NPhard problems , among them are approximation algorithms and parameterized algorithms . The study of approximation algorithms tries to & #64257 ;nd good enough solutions instead of optimal solutions in polynomial time , while parameterized algorithms try to give exact solutions when a natural parameter is small . In this thesis , we study the structural properties of parameterized computation and approximation algorithms for NP optimization problems . In particular , we investigate the relationship between parameterized complexity and polynomialtime approximation scheme (PTAS ) for NP optimization problems . We give nice characterizations for two important subclasses in PTAS : Fully Polynomial Time Approximation Scheme (FPTAS ) and Effcient Polynomial Time Approximation Scheme (EPTAS ) , using the theory of parameterized complexity . Our characterization of the class FPTAS has its advantages over the former characterizations , and our characterization of EPTAS is the & #64257 ;rst systematic investigation of this new but important approximation class . We develop new techniques to derive strong computational lower bounds for certain parameterized problems based on the theory of parameterized complexity . For example , we prove that unless an unlikely collapse occurs in parameterized complexity theory , the clique problem could not be solved in time O (f (k )no (k ) ) for any function f . This lower bound matches the upper bound of the trivial algorithm that simply enumerates and checks all subsets of k vertices in the given graph of n vertices . We then extend our techniques to derive computational lower bounds for PTAS and EPTAS algorithms of NP optimization problems . We prove that certain NP optimization problems with known PTAS algorithms have no PTAS algorithms of running time O (f (1 /Epsilon )no (1 /Epsilon ) ) for any function f . Therefore , for these NP optimization problems , although theoretically they can be approximated in polynomial time to an arbitrarily small error bound Epsilon , they have no practically effective approximation algorithms for small error bound Epsilon . To our knowledge , this is the & #64257 ;rst time such lower bound results have been derived for PTAS algorithms . This seems to open a new direction for the study of computational lower bounds on the approximability of NP optimization problems . |

URI: | http : / /hdl .handle .net /1969 .1 /1446 |

Date: | 2005-02-17 |

Files | Size | Format | View |
---|---|---|---|

etd-tamu-2004C-CPSC-Huang.pdf | 582.1Kb | application/pdf |
View/ |