Approximate solution of NP optimization problems
From MaRDI portal
Publication:672315
DOI10.1016/0304-3975(94)00291-PzbMath0874.68145MaRDI QIDQ672315
Pierluigi Crescenzi, Marco Protasi, Giorgio Ausiello
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
The NPO-completeness of the longest Hamiltonian cycle problem, Differential approximation results for the traveling salesman and related problems, On the approximability of two tree drawing conventions, Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Polynomial transformations and data-independent neighborhood functions, Analyzing the complexity of finding good neighborhood functions for local search algorithms, Polynomial approximation: a structural and operational study. (Abstract of thesis), The complexity and approximability of finding maximum feasible subsystems of linear relations, A randomized PTAS for the minimum consensus clustering with a fixed number of clusters, Local Monotonicity in Probabilistic Networks, Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\), An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\)), Reductions between scheduling problems with non-renewable resources and knapsack problems, An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm, Local search, reducibility and approximability of NP-optimization problems, COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES, Reductions, completeness and the hardness of approximability, Inapproximability results for equations over infinite groups, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), On computing the latest starting times and floats of activities in a network with imprecise durations, Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Differential approximation of NP-hard problems with equal size feasible solutions, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, Alphabet indexing for approximating features of symbols, On the hardness of approximating shortest integer relations among rational numbers, A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses, Elementary team strategies in a monotone game, Order preserving reductions and polynomial improving paths, The maximum \(f\)-depth spanning tree problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local search, reducibility and approximability of NP-optimization problems
- On approximating the longest path in a graph
- Completeness in approximation classes
- Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
- On different approximation criteria for subset product problems
- The complexity of optimization problems
- The Steiner problem with edge lengths 1 and 2
- Structure preserving reductions among convex optimization problems
- Toward a unified approach for the classification of NP-complete optimization problems
- Non deterministic polynomial optimization problems and their approximations
- A note on the approximation of the MAX CLIQUE problem
- On the complexity of approximating the independent set problem
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- Logical definability of NP optimization problems
- On Approximate Solutions for Combinatorial Optimization Problems
- Approximate Algorithms for the 0/1 Knapsack Problem
- `` Strong NP-Completeness Results
- AVERAGE MEASURE, DESCRIPTIVE COMPLEXITY AND APPROXIMATION OF MAXIMIZATION PROBLEMS
- Polynomially bounded minimization problems which are hard to approximate
- On the approximability of the maximum common subgraph problem
- On the hardness of approximating minimization problems
- Efficient probabilistically checkable proofs and applications to approximations
- Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions
