Combinatorial Problems: Reductibility and Approximation
From MaRDI portal
Publication:4170233
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
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
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
