Parameterized complexity and polynomial-time approximation schemes

Show full item record

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

Citation

Parameterized complexity and polynomial-time approximation schemes. Available electronically from http : / /hdl .handle .net /1969 .1 /1446 .

Files in this item

Files Size Format View
etd-tamu-2004C-CPSC-Huang.pdf 582.1Kb application/pdf View/Open

This item appears in the following Collection(s)

Show full item record

Search DSpace

Advanced Search

Browse