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) 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)