Approximate solution of NP optimization problems
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1944142
- scientific article; zbMATH DE number 847149
- On approximating NP-hard optimization problems
- Approximating values and solutions of NP-optimization problems: concepts and examples
- scientific article; zbMATH DE number 1086675
- Approximation algorithms for NP-hard problems
- On Approximate Solutions for Combinatorial Optimization Problems
- scientific article; zbMATH DE number 1775419
- Improving the complexities of approximation algorithms for optimization problems
- On fixed-parameter tractability and approximability of NP optimization problems
Cites work
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3850828 (Why is no real title available?)
- scientific article; zbMATH DE number 3733262 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256635 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 515727 (Why is no real title available?)
- scientific article; zbMATH DE number 578252 (Why is no real title available?)
- scientific article; zbMATH DE number 2077131 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- A note on the approximation of the MAX CLIQUE problem
- AVERAGE MEASURE, DESCRIPTIVE COMPLEXITY AND APPROXIMATION OF MAXIMIZATION PROBLEMS
- Approximate Algorithms for the 0/1 Knapsack Problem
- Approximation algorithms for combinatorial problems
- Completeness in approximation classes
- Efficient probabilistically checkable proofs and applications to approximations
- Local search, reducibility and approximability of NP-optimization problems
- Logical definability of NP optimization problems
- Non deterministic polynomial optimization problems and their approximations
- On Approximate Solutions for Combinatorial Optimization Problems
- On approximating the longest path in a graph
- On different approximation criteria for subset product problems
- On the approximability of the maximum common subgraph problem
- On the complexity of approximating the independent set problem
- On the hardness of approximating minimization problems
- Optimization, approximation, and complexity classes
- Polynomially bounded minimization problems which are hard to approximate
- Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions
- Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
- Structure preserving reductions among convex optimization problems
- The Steiner problem with edge lengths 1 and 2
- The complexity of optimization problems
- Toward a unified approach for the classification of NP-complete optimization problems
- `` Strong NP-Completeness Results
Cited in
(39)- Differential approximation of NP-hard problems with equal size feasible solutions
- Local search, reducibility and approximability of NP-optimization problems
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- scientific article; zbMATH DE number 3902037 (Why is no real title available?)
- Approximability of hard combinatorial optimization problems: an introduction
- The maximum \(f\)-depth spanning tree problem
- Improving the complexities of approximation algorithms for optimization problems
- On computing the latest starting times and floats of activities in a network with imprecise durations
- Reducing the number of solutions of NP functions
- Polynomial transformations and data-independent neighborhood functions
- MNP: A class of NP optimization problems
- Differential approximation results for the traveling salesman and related problems
- Reductions between scheduling problems with non-renewable resources and knapsack problems
- A randomized PTAS for the minimum consensus clustering with a fixed number of clusters
- Elementary team strategies in a monotone game
- Reoptimization of NP-Hard Problems
- Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\)
- Inapproximability results for equations over infinite groups
- Polynomial approximation: a structural and operational study. (Abstract of thesis)
- Reductions, completeness and the hardness of approximability
- Order preserving reductions and polynomial improving paths
- Analyzing the complexity of finding good neighborhood functions for local search algorithms
- Local Monotonicity in Probabilistic Networks
- Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
- Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
- On the hardness of approximating shortest integer relations among rational numbers
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Constructive -- non-constructive approximation and maximum independent set problem
- On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
- The NPO-completeness of the longest Hamiltonian cycle problem
- On the approximability of two tree drawing conventions
- Alphabet indexing for approximating features of symbols
- A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- scientific article; zbMATH DE number 847149 (Why is no real title available?)
This page was built for publication: Approximate solution of NP optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672315)
