Non deterministic polynomial optimization problems and their approximations
From MaRDI portal
Cites work
- 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?)
- 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
- 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
- `` Strong NP-Completeness Results
Cited in
(48)- Polynomial time approximation schemes and parameterized complexity
- Approximation scheduling algorithms: a survey
- A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
- On different approximation criteria for subset product problems
- Parameterized domination in circle graphs
- On parallel versus sequential approximation
- Quantifiers and approximation
- Finding approximate and constrained motifs in graphs
- Path-driven orientation of mixed graphs
- Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
- A note on the hardness results for the labeled perfect matching problems in bipartite graphs
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- A survey on combinatorial optimization in dynamic environments
- A bounded approximation for the minimum cost 2-sat problem
- Optimization, approximation, and complexity classes
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- K-adaptability in stochastic optimization
- Complexity and algorithms for MUL-tree pruning
- On approximability of linear ordering and related NP-optimization problems on graphs.
- On the complexity of approximating the independent set problem (extended abstract)
- Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality
- Approximate solution of NP optimization problems
- Completeness in approximation classes
- Finding approximate and constrained motifs in graphs
- A survey on the structure of approximation classes
- Some tractable instances of interval data minmax regret problems
- Complexity issues in vertex-colored graph pattern matching
- On the complexity of approximating the independent set problem
- Parameterized complexity of three edge contraction problems with degree constraints
- Hardness and inapproximability of convex recoloring problems
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
- Efficient approximation of convex recolorings
- 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 approximation problems related to the independent set and vertex cover problems
- Correcting gene tree by removal and modification: tractability and approximability
- Parameterized (in)approximability of subset problems
- Coresets for the Nearest-Neighbor Rule
- Local search, reducibility and approximability of NP-optimization problems
- The Parameterized Complexity of the Unique Coverage Problem
- Structure of polynomial-time approximation
- On the complexity of approximately matching a string to a directed graph
- New local search approximation techniques for maximum generalized satisfiability problems
- MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms
- On the tractability of covering a graph with 2-clubs
- Reductions, completeness and the hardness of approximability
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)
