2004/06/01 by Dorit S. Hochbaum · 35 citations
Engineering · Mathematics · #Mining Techniques and Economics #Belt Conveyor Systems Engineering #Mineral Processing and Grinding #Computer science #Selection (genetic algorithm) #Generalization #Variety (cybernetics) #Mathematical optimization #Integer programming #Closure (psychology) #Field (mathematics) #Linear programming #Operations research #Mathematics #Algorithm #Artificial intelligence #Economics
paper · doi:10.1287/mnsc.1040.0242
published in Management Science 50(6), 709-723 (Institute for Operations Research and the Management Sciences)
openalex publication_date 2004/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
Motivated by applications in freight handling and open-pit mining, Rhys, Balinski, and Picard studied the problems of selection and closure in papers published in Management Science in 1970 and 1976. They identified efficient algorithms based on linear programming and maximum-flow/minimum-cut procedures to solve these problems. This research has had major impact well beyond the initial applications, reaching across three decades and inspiring work on numerous applications and extensions. The extensions are nontrivial optimization problems that are of theoretical interest. The applications ranged from evolving technologies, image segmentation, revealed preferences, pricing, adjusting utilities for consistencies, just-in-time production, solving certain integer programs in polynomial time, and providing efficient 2-approximation algorithms for a wide variety of hard problems. A recent generalization to a convex objective function has even produced novel solutions to prediction and Bayesian estimation problems. This paper surveys the streams of research stimulated by these papers as an example of the impact of Management Science on the optimization field and an illustration of the far-reaching implications of good original research.