Optimization, approximation, and complexity classes
From MaRDI portal
The authors introduce a complexity class, called MAX NP, which is a variant of NP. They define also MAX SNP which is a subclass of MAX NP. These are classes of optimization problems that contain many known and well-studied problems. The main result of the paper is the proof that problems in these classes can be approximated with some bounded error. Additionally, the authors show that a number of common optimization problems are complete for MAX SNP under a specific transformation, \textit{L-reduction}, that preserves approximability. It follows that such a complete problem has a polynomial-time approximation scheme if and only if the whole class does.
Recommendations
Cites work
- Approximation algorithms for combinatorial problems
- How well can a graph be n-colored?
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3566230 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Non deterministic polynomial optimization problems and their approximations
- On the complexity of approximating the independent set problem
- Some Examples of Difficult Traveling Salesman Problems
- Structure preserving reductions among convex optimization problems
- The Complexity of Near-Optimal Graph Coloring
- The complexity of optimization problems
- Toward a unified approach for the classification of NP-complete optimization problems
Cited in
(only showing first 100 items - show all)- Approximability of partitioning graphs with supply and demand
- Parameterizing above or below guaranteed values
- Routing to reduce the cost of wavelength conversion
- Finding occurrences of protein complexes in protein-protein interaction graphs
- Red-blue covering problems and the consecutive ones property
- Connected domination of regular graphs
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Paintshop, odd cycles and necklace splitting
- Hardness results and approximation algorithms for (weighted) paired-domination in graphs
- Cryptography with constant input locality
- PTAS for connected vertex cover in unit disk graphs
- Covering the edges of bipartite graphs using \(K_{2,2}\) graphs
- Priority algorithms for graph optimization problems
- Non-approximability of weighted multiple sequence alignment for arbitrary metrics
- The labeled perfect matching in bipartite graphs
- Efficient delay routing
- A unified approximation algorithm for node-deletion problems
- On a scheduling problem of time deteriorating jobs
- Alphabet indexing for approximating features of symbols
- On the approximation of protein threading
- On the hardness of allocating frequencies for hybrid networks
- A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses
- Integer programming as a framework for optimization and approximability
- Class Steiner trees and VLSI-design
- Computational experience with approximation algorithms for the set covering problem
- On the approximability of the Steiner tree problem in phylogeny
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- The computational complexity of some problems of linear algebra
- Some MAX SNP-hard results concerning unordered labeled trees
- Maximum bounded \(H\)-matching is Max SNP-complete
- Oracle computations in parallel numerical linear algebra
- The hardness of approximation: Gap location
- Approximations for the maximum acyclic subgraph problem
- A short note on the approximability of the maximum leaves spanning tree problem
- On the power of multi-prover interactive protocols
- Probabilistically checkable proofs and their consequences for approximation algorithms
- Approximability of maximum splitting of k-sets and some other Apx-complete problems
- On approximation algorithms for the minimum satisfiability problem
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- New local search approximation techniques for maximum generalized satisfiability problems
- Inferring a tree from walks
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- On fixed-parameter tractability and approximability of NP optimization problems
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- MNP: A class of NP optimization problems
- Rounding algorithms for covering problems
- Metafinite model theory
- On the approximability of some Maximum Spanning Tree Problems
- Non-approximability of weighted multiple sequence alignment.
- Studying the complexity of global verification for NP-hard discrete optimization problems
- The task allocation problem with constant communication.
- Local approximations for maximum partial subgraph problem.
- On approximability of linear ordering and related NP-optimization problems on graphs.
- Hardness of approximation for non-overlapping local alignments.
- Distinguishing string selection problems.
- Differential approximation results for the Steiner tree problem
- Some APX-completeness results for cubic graphs
- Counting problems over the reals
- Interactive and probabilistic proof-checking
- Approximating minimum feedback vertex sets in hypergraphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Structural properties of bounded relations with an application to NP optimization problems
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Hardness results for neural network approximation problems
- Which problems have strongly exponential complexity?
- A randomized approximation scheme for metric MAX-CUT
- Computing similarity between RNA structures
- On bounded occurrence constraint satisfaction
- The complexity of minimizing and learning OBDDs and FBDDs
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- On the complexity of computing MP distance between binary phylogenetic trees
- Sparsification and subexponential approximation
- The many facets of upper domination
- The complexity of secure domination problem in graphs
- Complexity and lowers bounds for power edge set problem
- Restricted assignment scheduling with resource constraints
- Affine reductions for LPs and SDPs
- Limitations of semidefinite programs for separable states and entangled games
- Finding a potential community in networks
- Finding a most parsimonious or likely tree in a network with respect to an alignment
- Deciding the existence of a cherry-picking sequence is hard on two trees
- Approximation algorithms for connected graph factors of minimum weight
- Competitive algorithms for multistage online scheduling
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- Complexity of distance paired-domination problem in graphs
- The approximability of non-Boolean satisfiability problems and restricted integer programming
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- Order consolidation for batch processing
- On the approximability of the maximum induced matching problem
- Conversion of coloring algorithms into maximum weight independent set algorithms
- On the complexity of finding emerging patterns
- Minimizing the number of switch instances on a flexible machine in polynomial time
- Metabolic networks are NP-hard to reconstruct
- \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
- Submodular unsplittable flow on trees
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Local search for the minimum label spanning tree problem with bounded color classes.
- On the complexity of the approximation of nonplanarity parameters for cubic graphs
- Derandomized graph products
This page was built for publication: Optimization, approximation, and complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186548)
