Browsing by Subject "approximation"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Parameterized complexity and polynomial-time approximation schemes(Texas A&M University, 2005-02-17) Huang, XiuzhenAccording 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 find 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 first 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 first 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.Item Studies in Interpolation and Approximation of Multivariate Bandlimited Functions(2012-10-19) Bailey, Benjamin AaronThe focus of this dissertation is the interpolation and approximation of multivariate bandlimited functions via sampled (function) values. The first set of results investigates polynomial interpolation in connection with multivariate bandlimited functions. To this end, the concept of a uniformly invertible Riesz basis is developed (with examples), and is used to construct Lagrangian polynomial interpolants for particular classes of sampled square-summable data. These interpolants are used to derive two asymptotic recovery and approximation formulas. The first recovery formula is theoretically straightforward, with global convergence in the appropriate metrics; however, it becomes computationally complicated in the limit. This complexity is sidestepped in the second recovery formula, at the cost of requiring a more local form of convergence. The second set of results uses oversampling of data to establish a multivariate recovery formula. Under additional restrictions on the sampling sites and the frequency band, this formula demonstrates a certain stability with respect to sampling errors. Computational simplifications of this formula are also given.