Non deterministic polynomial optimization problems and their approximations
From MaRDI portal
Publication:1152215
DOI10.1016/0304-3975(81)90081-5zbMath0459.68015MaRDI QIDQ1152215
Publication date: 1981
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(81)90081-5
68Q25: Analysis of algorithms and problem complexity
Related Items
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, The Parameterized Complexity of the Unique Coverage Problem, Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality, Approximate solution of NP optimization problems, Local search, reducibility and approximability of NP-optimization problems, Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), On approximation problems related to the independent set and vertex cover problems, Completeness in approximation classes, Polynomial time approximation schemes and parameterized complexity, Some tractable instances of interval data minmax regret problems, Efficient approximation of Min Set Cover by moderately exponential algorithms, On different approximation criteria for subset product problems, On the complexity of approximating the independent set problem, Optimization, approximation, and complexity classes, A bounded approximation for the minimum cost 2-sat problem, Quantifiers and approximation, New local search approximation techniques for maximum generalized satisfiability problems, On approximability of linear ordering and related NP-optimization problems on graphs., Max NP-completeness made easy, Bridging gap between standard and differential polynomial approximation: The case of bin-packing, Reductions, completeness and the hardness of approximability, Parameterized computation and complexity: a new approach dealing with NP-hardness, Efficient approximation of convex recolorings, A note on the hardness results for the labeled perfect matching problems in bipartite graphs, Approximation scheduling algorithms: a survey
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- General approximation algorithms for some arithmetical combinatorial problems
- Relationships between nondeterministic and deterministic tape complexities
- On the computational power of pushdown automata
- Applications of a Planar Separator Theorem
- The Complexity of Near-Optimal Graph Coloring
- A Fast Monte-Carlo Test for Primality
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- P-Complete Approximation Problems
- `` Strong NP-Completeness Results
- Combinatorial Problems: Reductibility and Approximation
- Combinatorial Problems: Reductibility and Approximation
- Computationally Related Problems
- The complexity of theorem-proving procedures
