Non deterministic polynomial optimization problems and their approximations

DOI10.1016/0304-3975(81)90081-5zbMath0459.68015OpenAlexW2056090079MaRDI 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

On different approximation criteria for subset product problems ⋮ A survey on combinatorial optimization in dynamic environments ⋮ New local search approximation techniques for maximum generalized satisfiability problems ⋮ Efficient approximation of convex recolorings ⋮ Polynomial time approximation schemes and parameterized complexity ⋮ Finding approximate and constrained motifs in graphs ⋮ On parallel versus sequential approximation ⋮ Parameterized domination in circle graphs ⋮ Max NP-completeness made easy ⋮ A survey on the structure of approximation classes ⋮ Bridging gap between standard and differential polynomial approximation: The case of bin-packing ⋮ Hardness and inapproximability of convex recoloring problems ⋮ On approximability of linear ordering and related NP-optimization problems on graphs. ⋮ 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 ⋮ The Parameterized Complexity of the Unique Coverage Problem ⋮ Path-driven orientation of mixed graphs ⋮ Coresets for the Nearest-Neighbor Rule ⋮ Correcting gene tree by removal and modification: tractability and approximability ⋮ On the complexity of approximating the independent set problem ⋮ Optimization, approximation, and complexity classes ⋮ Approximate solution of NP optimization problems ⋮ Local search, reducibility and approximability of NP-optimization problems ⋮ Finding Approximate and Constrained Motifs in Graphs ⋮ A bounded approximation for the minimum cost 2-sat problem ⋮ Structure of polynomial-time approximation ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Quantifiers and approximation ⋮ Reductions, completeness and the hardness of approximability ⋮ 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 ⋮ Parameterized (in)approximability of subset problems ⋮ Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality ⋮ Some tractable instances of interval data minmax regret problems ⋮ Algorithmic and hardness results for the colorful components problems ⋮ On the tractability of covering a graph with 2-clubs ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ The complexity of finding temporal separators under waiting time constraints ⋮ On the complexity of approximating the independent set problem ⋮ On approximation problems related to the independent set and vertex cover problems ⋮ Approximation scheduling algorithms: a survey ⋮ On the complexity of approximately matching a string to a directed graph ⋮ MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ \(K\)-adaptability in stochastic optimization ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems ⋮ Completeness in approximation classes ⋮ Complexity and algorithms for MUL-tree pruning

Cites Work