Combinatorial Problems: Reductibility and Approximation

DOI10.1287/OPRE.26.5.718zbMath0388.68041OpenAlexW2109155166MaRDI QIDQ4170233

Ellis Horowitz, Sartaj K. 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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Permutations, words, matrices (05A05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Algorithms in computer science (68W99)

Related Items (7)

Knapsack problem with objective value gaps ⋮ Non deterministic polynomial optimization problems and their approximations ⋮ The edge Hamiltonian path problem is NP-complete ⋮ Solving certain singly constrained convex optimization problems in production planning ⋮ NP-Complete operations research problems and approximation algorithms ⋮ Heuristic methods and applications: A categorized survey ⋮ A lower bound to the complexity of Euclidean and rectilinear matching algorithms

This page was built for publication: Combinatorial Problems: Reductibility and Approximation