• Polynomial time approximation...

Result: Polynomial time approximation schemes and parameterized complexity

Title:
Polynomial time approximation schemes and parameterized complexity
Authors:
JIANER CHEN, XIUZHEN HUANG, KANJ, Iyad A, GE XIA
Source:
29th symposium on mathematical foundations of computer science MFCS 2004Discrete applied mathematics. 155(2):180-193
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 26 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Optimisation. Problèmes de recherche, Optimization. Search problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme approximation, Approximation algorithm, Algoritmo aproximación, Classe complexité, Complexity class, Clase complejidad, Combinatoire, Combinatorics, Combinatoria, Complexité temps, Time complexity, Complejidad tiempo, Informatique théorique, Computer theory, Informática teórica, Méthode optimisation, Optimization method, Método optimización, Algorithme temps polynomial, Approximabilité, Complexité paramétrisée, Parameterized complexity, Hiérarchie W, W hierarchy, Planarité, Problème NP, Polynomial time approximation scheme: Parameterized complexity, W-hierarchy
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer Science, Texas A&M University, College Station, TX 77843, United States
College of Information Science and Engineering, Central South University, Changshu 410083, China
Department of Computer Science, Arkansas State University, State University, AR 72467, United States
School of CTI, DePaul University, 243 S. Wabash Avenue, Chicago, IL 60604, United States
Department of Computer Science, Lafayette College, Easton, PA 18042, United States
ISSN:
0166-218X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18454953
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Operational research. Management
Accession Number:
edscal.18454953
Database:
PASCAL Archive

Further Information

In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes.