An appraisal of computational complexity for operations researchers
From MaRDI portal
Publication:1173532
DOI10.1016/0377-2217(82)90242-9zbMath0503.90053OpenAlexW1981267577MaRDI QIDQ1173532
Peter van Emde Boas, Alexander H. G. Rinnooy Kan, Jan Karel Lenstra
Publication date: 1982
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0377-2217(82)90242-9
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Cites Work
- On distinguishing prime numbers from composite numbers
- Probabilistic algorithm for testing primality
- Decomposition of regular matroids
- Matroid matching and some applications
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- A simple heuristic approach to simplex efficiency
- The ellipsoid method and its consequences in combinatorial optimization
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Linear programming is log-space hard for P
- Integer Programming with a Fixed Number of Variables
- Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
- The Complexity of the Partial Order Dimension Problem
- Probabilistic Analysis of the Planar k-Median Problem
- An Algorithm for Large Zero-One Knapsack Problems
- Khachiyan’s algorithm for linear programming
- Analytical Evaluation of Hierarchical Planning Systems
- On the complexity of integer programming
- The NP-Completeness of Edge-Coloring
- Feature Article—The Ellipsoid Method: A Survey
- A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
- Computing the Minimum Fill-In is NP-Complete
- Complete Convergence of Short Paths and Karp's Algorithm for the TSP
- Steinhaus's geometric location problem for random samples in the plane
- Every Prime Has a Succinct Certificate
- On the Structure of Polynomial Time Reducibility
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On the Computational Complexity of Combinatorial Problems
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- Computational Complexity of Discrete Optimization Problems
- Polynomial algorithms for a class of linear programs
- Hierarchical vehicle routing problems
- Pathology of Traveling-Salesman Subtour-Elimination Algorithms
- The NP-completeness column: An ongoing guide
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An appraisal of computational complexity for operations researchers
