An appraisal of computational complexity for operations researchers
type: Item
instance of: scholarly article
title: An appraisal of computational complexity for operations researchers
zbMATH Open document ID: 0503.90053
DOI: 10.1016/0377-2217(82)90242-9
author: Peter van Emde Boas
author: Jan Karel Lenstra
author: Alexander H. G. Rinnooy Kan
published in: European Journal of Operational Research
publication date: 1982-01-01T00:00:00Z
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90-02
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 3793765
zbMATH Keywords: computational complexity
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: survey
zbMATH Keywords: NP- completeness
MaRDI profile type: Publication
full work available at URL: 0377-2217(82)90242-9
OpenAlex ID: W1981267577
cites work: On distinguishing prime numbers from composite numbers
cites work: Q3912033
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: An Algorithm for Large Zero-One Knapsack Problems
cites work: Q5729634
cites work: Pathology of Traveling-Salesman Subtour-Elimination Algorithms
cites work: Q3941433
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Feature Article—The Ellipsoid Method: A Survey
cites work: Q4138187
cites work: Analytical Evaluation of Hierarchical Planning Systems
cites work: Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
cites work: Linear programming is log-space hard for P
cites work: Q4065548
cites work: Probabilistic Analysis of the Planar k-Median Problem
cites work: Khachiyan’s algorithm for linear programming
cites work: Q4198056
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
cites work: Steinhaus's geometric location problem for random samples in the plane
cites work: The NP-Completeness of Edge-Coloring
cites work: The NP-completeness column: An ongoing guide
cites work: Q3937379
cites work: Q4142699
cites work: On the Computational Complexity of Combinatorial Problems
cites work: Q4144785
cites work: Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
cites work: Q3050157
cites work: Q4051879
cites work: On the Structure of Polynomial Time Reducibility
cites work: Q3899811
cites work: Q3899810
cites work: Q3940839
cites work: Q3933739
cites work: Integer Programming with a Fixed Number of Variables
cites work: Q3933051
cites work: Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
cites work: Computational Complexity of Discrete Optimization Problems
cites work: Q3206662
cites work: Matroid matching and some applications
cites work: Q3934404
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: Hierarchical vehicle routing problems
cites work: Polynomial algorithms for a class of linear programs
cites work: On the complexity of integer programming
cites work: Every Prime Has a Succinct Certificate
cites work: Q4164569
cites work: Probabilistic algorithm for testing primality
cites work: A simple heuristic approach to simplex efficiency
cites work: Decomposition of regular matroids
cites work: Subadditive Euclidean functionals and nonlinear growth in geometric probability
cites work: Complete Convergence of Short Paths and Karp's Algorithm for the TSP
cites work: Computing the Minimum Fill-In is NP-Complete
cites work: The Complexity of the Partial Order Dimension Problem
description: scientific article; zbMATH DE number 3793765