scientific article; zbMATH DE number 1256750

zbMATH Open0922.68058MaRDI QIDQ4228486FDOQ4228486

Authors: Sanjeev Khanna, Rajeev Motwani 

Publication date: 1 March 1999

Title of this publication is not available (Why is that?)

Recommendations

• The complexity of polynomial-time approximation
• Structure of polynomial-time approximation
• On Syntactic versus Computational Views of Approximability
• Approximate solution of NP optimization problems

zbMATH Keywords

NP optimization problemsclass PTAS

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (20)

• Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
• Intractability of assembly sequencing: unit disks in the plane
• Planar 3-SAT with a clause/variable cycle
• Partition into cliques for cubic graphs: Planar case, complexity and approximation
• Satisfiability, branch-width and Tseitin tautologies
• Conjunctive query containment revisited
• Succinct monotone circuit certification: planarity and parameterized complexity
• On the efficiency of polynomial time approximation schemes
• Network pollution games
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Parameterized complexity: the main ideas and connections to practical computing
• Sublinear-space approximation algorithms for Max \(r\)-SAT
• PTAS for Sparse General-valued CSPs
• Succinct certification of monotone circuits
• Title not available (Why is that?)
• Parameterized computation and complexity: a new approach dealing with NP-hardness
• Max NP-completeness made easy
• On planar valued CSPs
• On MAX-SAT with cardinality constraint
• Complexity and Algorithms for Well-Structured k-SAT Instances

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4228486)