Combinatorial Problems: Reductibility and Approximation
DOI10.1287/OPRE.26.5.718zbMATH Open0388.68041OpenAlexW2109155166MaRDI QIDQ4170233FDOQ4170233
Authors: Ellis Horowitz, Sartaj Sahni 
Publication date: 1978
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.26.5.718
Permutations, words, matrices (05A05) Linear programming (90C05) Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Algorithms in computer science (68W99)
Cited In (7)
- A lower bound to the complexity of Euclidean and rectilinear matching algorithms
- Non deterministic polynomial optimization problems and their approximations
- Heuristic methods and applications: A categorized survey
- Knapsack problem with objective value gaps
- Solving certain singly constrained convex optimization problems in production planning
- NP-Complete operations research problems and approximation algorithms
- The edge Hamiltonian path problem is NP-complete
This page was built for publication: Combinatorial Problems: Reductibility and Approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4170233)
