Non Deterministic Polynomial Optimization Problems and their Approximations

Keywords

Nondeterministic algorithm, Impossibility, Mathematics, Frame (networking), Polynomial

References

• The Design and Analysis of Computer AlgorithmsAlfred V. Aho, John E. Hopcroft — 1974
• A Fast Monte-Carlo Test for PrimalityR. M. Solovay, Volker Strassen — 1977
• General Approximation Algorithms for some Arithmetical Combinatorial ProblemsShlomo Moran — 1981
• Relationships Between Nondeterministic and Deterministic Tape ComplexitiesWalter J. Savitch — 1970
• Applications of a planar separator theoremRichard J. Lipton, Robert E. Tarjan — 1977
• Fast approximation algorithms for knapsack problemsEugene L. Lawler — 1977
• Computationally Related ProblemsSartaj Sahni — 1974
• `` Strong '' NP-Completeness Results: Motivation, Examples, and ImplicationsM. R. Garey, David Johnson — 1978
• The Complexity of Near-Optimal Graph ColoringM. R. Garey, David S. Johnson — 1976
• Postscript about NP-hard problemsDonald E. Knuth — 1974
• Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsÓscar H. Ibarra, Chul E. Kim — 1975
• Some simplified NP-complete problemsM. R. Garey, D. S. Johnson, Larry Stockmeyer — 1974
• The complexity of theorem-proving proceduresStephen Cook — 1971
• Approximation algorithms for combinatorial problemsDavid S. Johnson — 1973
• P-Complete Approximation ProblemsSartaj Sahni, Teofilo F. Gonzalez — 1976
• Combinatorial Problems: Reductibility and ApproximationSartaj Sahni, Ellis Horowitz — 1978
• General Techniques for Combinatorial ApproximationSartaj Sahni — 1977
• On the Structure and Properties of NP-Complete Problems and Their Associated Optimization ProblemsG. Ausiello — 1977
• Approximation algorithms for combinatorial problems: an annotated bibliographyM. Garey, David S. Johnson — 1976
• On the Structure of Combinatorial Problems and Structure Preserving ReductionsG. Ausiello, A. D'Atri, M. Protasi — 1977

Cited by

• On Approximation Preserving Reductions: Complete Problems and Robust Measures (Revised Version)Pekka Orponen, Heikki Mannila — 1987
• Convex Recolorings of Strings and TreesShlomo Moran, Sagi Snir — 2003
• Compendium of Parameterized ProblemsMarco Cesati — 2006
• Hyper-rectangle-based discriminative data generalization and applications in data miningByron J. Gao — 2006
• A Framework for Approximate Optimization of BoT Application Deployment in Hybrid Cloud EnvironmentM. HoseinyFarahabady — 2014
• Lattice Theoretic Ordering Properties for NP-Complete Optimization ProblemsGiorgio Ausiello, Alessandro D’Atri, Marco Protasi — 1981
• MAX NP-Completeness Made EasyPierluigi Crescenzi, Luca Trevisan — 1999
• Comparaison de réseaux biologiquesHafedh Mohamed Babou — 2012
• Approximation and electionsEric Brelsford — 2007
• Language models for hierarchical summarizationDawn Lawrie, W. Bruce Croft — 2003
• Positive and Negative Results in Approximation and Parameterized Complexity. (Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée)Édouard Bonnet — 2014
• Decision Region Connectivity Analysis: A Method for Analyzing High-Dimensional ClassifiersOfer Melnik — 2002
• Approximating the domatic numberUriel Feige, Magnús M. Halldórsson, Guy Kortsarz — 2000
• Approximability of hard combinatorial optimization problems: an introductionFrancesco Maffioli, Giulia Galbiati — 2000
• Approximation polynomiale de problèmes d’optimisation : aspects structurels et opérationnelsBruno Escoffier — 2005
• Efficient Checking of Polynomials and Proofs and the Hardness of Appoximation ProblemsMadhu Sudan — 1995
• Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)Jérôme Monnot — 2005
• On the complexity of designing optimal partial-match retrieval systemsShlomo Moran — 1983
• On approximation problems related to the independent set and vertex cover problemsReuven Bar-Yehuda, Shlomo Moran — 1984
• The Minimum Consistent Subset Cover Problem: A Minimization View of Data MiningByron J. Gao, Martin Ester, Hui Xiong — 2013

Related papers

• SIGESTThe Editors — 2006
• Nondeterministic polynomial time versus nondeterministic logarithmic space: time-space tradeoffs for satisfiabilityLance Fortnow — 1997
• Strong Nondeterministic Polynomial-Time ReducibilitiesTimothy J. Long — 1982
• On the power of deterministic reductions to C=PFrederic Green — 1993
• Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classesPhilippe Chapdelaine, Étienne Grandjean — 2006
• Trading Determinism for Time in Space Bounded ComputationsVivek Anand T Kallampally, Raghunath Tewari — 2016