OPTIMIZATION, APPROXIMATION, AND COMPLEXITY CLASSES (Extended Abstract)

OPTIMIZATION, APPROXIMATION, AND COMPLEXITY CLASSES (Extended Abstract)

1988 | Christos H. Papadimitriou, Mihalis Yannakakis
The paper introduces and defines MAX NP and MAX SNP, subclasses of NP, focusing on optimization problems. These classes capture a variety of well-studied optimization problems and their approximability. The authors show that problems in these classes can be approximated with bounded error and that several common optimization problems are complete under a specific transformation called L-reduction, which preserves approximability. This implies that a complete problem in these classes has a polynomial-time approximation scheme (PTAS) if and only if the entire class does. The paper discusses the challenges in defining and reducing optimization problems to capture approximability and presents several examples of complete problems in MAX SNP, such as MAX 3SAT, MAX CUT, and MAX NOT-ALL-EQUAL 3SAT. It also explores weighted versions of these problems and their approximability. The authors conclude by highlighting the significance of these complexity classes in understanding the limits of approximability for various optimization problems.The paper introduces and defines MAX NP and MAX SNP, subclasses of NP, focusing on optimization problems. These classes capture a variety of well-studied optimization problems and their approximability. The authors show that problems in these classes can be approximated with bounded error and that several common optimization problems are complete under a specific transformation called L-reduction, which preserves approximability. This implies that a complete problem in these classes has a polynomial-time approximation scheme (PTAS) if and only if the entire class does. The paper discusses the challenges in defining and reducing optimization problems to capture approximability and presents several examples of complete problems in MAX SNP, such as MAX 3SAT, MAX CUT, and MAX NOT-ALL-EQUAL 3SAT. It also explores weighted versions of these problems and their approximability. The authors conclude by highlighting the significance of these complexity classes in understanding the limits of approximability for various optimization problems.
Reach us at info@study.space
[slides] Optimization%2C approximation%2C and complexity classes | StudySpace