Combinatorial Problems: Reductibility and Approximation

DOI10.1287/OPRE.26.5.718MaRDI QIDQ4170233zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Cited in

(7)

• A lower bound to the complexity of Euclidean and rectilinear matching algorithms
• 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
• Heuristic methods and applications: A categorized survey
• Knapsack problem with objective value gaps
• NP-Complete operations research problems and approximation algorithms

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)