Non deterministic polynomial optimization problems and their approximations
From MaRDI portal
Cites work
- `` Strong NP-Completeness Results
- A Fast Monte-Carlo Test for Primality
- Applications of a Planar Separator Theorem
- Combinatorial Problems: Reductibility and Approximation
- Combinatorial Problems: Reductibility and Approximation
- Computationally Related Problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- General approximation algorithms for some arithmetical combinatorial problems
- scientific article; zbMATH DE number 3495588 (Why is no real title available?)
- scientific article; zbMATH DE number 3551892 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3576997 (Why is no real title available?)
- scientific article; zbMATH DE number 3593565 (Why is no real title available?)
- scientific article; zbMATH DE number 3597592 (Why is no real title available?)
- scientific article; zbMATH DE number 3639145 (Why is no real title available?)
- On the computational power of pushdown automata
- P-Complete Approximation Problems
- Relationships between nondeterministic and deterministic tape complexities
- The Complexity of Near-Optimal Graph Coloring
- The complexity of theorem-proving procedures
Cited in
(48)- 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.
- Parameterized (in)approximability of subset problems
- Max NP-completeness made easy
- Bridging gap between standard and differential polynomial approximation: The case of bin-packing
- The complexity of finding temporal separators under waiting time constraints
- On the complexity of approximately matching a string to a directed graph
- MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms
- K-adaptability in stochastic optimization
- A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
- Complexity and algorithms for MUL-tree pruning
- Parameterized domination in circle graphs
- Hardness and inapproximability of convex recoloring problems
- Reductions, completeness and the hardness of approximability
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Efficient approximation of convex recolorings
- A survey on combinatorial optimization in dynamic environments
- Finding approximate and constrained motifs in graphs
- A note on the hardness results for the labeled perfect matching problems in bipartite graphs
- Finding approximate and constrained motifs in graphs
- Approximation scheduling algorithms: a survey
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- A survey on the structure of approximation classes
- On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
- Parameterized complexity of three edge contraction problems with degree constraints
- Path-driven orientation of mixed graphs
- Correcting gene tree by removal and modification: tractability and approximability
- On the complexity of approximating the independent set problem (extended abstract)
- Complexity issues in vertex-colored graph pattern matching
- The Parameterized Complexity of the Unique Coverage Problem
- Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality
- Coresets for the Nearest-Neighbor Rule
- On the tractability of covering a graph with 2-clubs
- On parallel versus sequential approximation
- Approximate solution of NP optimization problems
- Local search, reducibility and approximability of NP-optimization problems
- Structure of polynomial-time approximation
- 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
This page was built for publication: Non deterministic polynomial optimization problems and their approximations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1152215)
