IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v50y2004i6p709-723.html
   My bibliography  Save this article

50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today

Author

Listed:
  • Dorit S. Hochbaum

    (Department of Industrial Engineering and Operations Research and Walter A. Haas School of Business, University of California, Berkeley, California 94720)

Abstract

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.

Suggested Citation

  • Dorit S. Hochbaum, 2004. "50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today," Management Science, INFORMS, vol. 50(6), pages 709-723, June.
    • Handle: RePEc:inm:ormnsc:v:50:y:2004:i:6:p:709-723
    DOI: 10.1287/mnsc.1040.0242
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.1040.0242
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.1040.0242?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. John W. Mamer & Stephen A. Smith, 1982. "Optimizing Field Repair Kits Based on Job Completion Rate," Management Science, INFORMS, vol. 28(11), pages 1328-1333, November.
    2. Ravindra K. Ahuja & Dorit S. Hochbaum & James B. Orlin, 2003. "Solving the Convex Cost Integer Dual Network Flow Problem," Management Science, INFORMS, vol. 49(7), pages 950-964, July.
    3. Edward I. Altman, 1968. "Financial Ratios, Discriminant Analysis And The Prediction Of Corporate Bankruptcy," Journal of Finance, American Finance Association, vol. 23(4), pages 589-609, September.
    4. Robin Roundy, 1985. "98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer Systems," Management Science, INFORMS, vol. 31(11), pages 1416-1430, November.
    5. William L. Maxwell & John A. Muckstadt, 1985. "Establishing Consistent and Realistic Reorder Intervals in Production-Distribution Systems," Operations Research, INFORMS, vol. 33(6), pages 1316-1341, December.
    6. Edward I. Altman, 1968. "The Prediction Of Corporate Bankruptcy: A Discriminant Analysis," Journal of Finance, American Finance Association, vol. 23(1), pages 193-194, March.
    7. Dorit S. Hochbaum, 2003. "Efficient Algorithms for the Inverse Spanning-Tree Problem," Operations Research, INFORMS, vol. 51(5), pages 785-797, October.
    8. Hochbaum, Dorit S., 2002. "Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations," European Journal of Operational Research, Elsevier, vol. 140(2), pages 291-321, July.
    9. J. M. W. Rhys, 1970. "A Selection Problem of Shared Fixed Costs and Network Flows," Management Science, INFORMS, vol. 17(3), pages 200-207, November.
    10. Ravindra K. Ahuja & James B. Orlin, 2001. "A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints," Operations Research, INFORMS, vol. 49(5), pages 784-789, October.
    11. Arthur F. Veinott, Jr., 1971. "Least d-Majorized Network Flows with Inventory and Statistical Applications," Management Science, INFORMS, vol. 17(9), pages 547-567, May.
    12. Jean-Claude Picard, 1976. "Maximal Closure of a Graph and Applications to Combinatorial Problems," Management Science, INFORMS, vol. 22(11), pages 1268-1272, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Colombi, Marco & Mansini, Renata & Savelsbergh, Martin, 2017. "The generalized independent set problem: Polyhedral analysis and solution approaches," European Journal of Operational Research, Elsevier, vol. 260(1), pages 41-55.
    2. Olszewski, Wojciech & Vohra, Rakesh, 2014. "Selecting a discrete portfolio," Journal of Mathematical Economics, Elsevier, vol. 55(C), pages 69-73.
    3. You, Byungjun & Yamada, Takeo, 2007. "A pegging approach to the precedence-constrained knapsack problem," European Journal of Operational Research, Elsevier, vol. 183(2), pages 618-632, December.
    4. Dorit S. Hochbaum & Erick Moreno-Centeno & Phillip Yelland & Rodolfo A. Catena, 2011. "Rating Customers According to Their Promptness to Adopt New Products," Operations Research, INFORMS, vol. 59(5), pages 1171-1183, October.
    5. Queyranne, M. & Wolsey, L.A., 2015. "Modeling poset convex subsets," LIDAM Discussion Papers CORE 2015049, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dorit Hochbaum, 2007. "Complexity and algorithms for nonlinear optimization problems," Annals of Operations Research, Springer, vol. 153(1), pages 257-296, September.
    2. Barbara Su, 2023. "Banking practices and borrowing firms’ financial reporting quality: evidence from bank cross-selling," Review of Accounting Studies, Springer, vol. 28(1), pages 201-236, March.
    3. Shaikh, Ibrahim A. & O'Brien, Jonathan Paul & Peters, Lois, 2018. "Inside directors and the underinvestment of financial slack towards R&D-intensity in high-technology firms," Journal of Business Research, Elsevier, vol. 82(C), pages 192-201.
    4. Mikel Bedayo & Gabriel Jiménez & José-Luis Peydró & Raquel Vegas, 2020. "Screening and Loan Origination Time: Lending Standards, Loan Defaults and Bank Failures," Working Papers 1215, Barcelona School of Economics.
    5. Ruey-Ching Hwang, 2013. "Forecasting credit ratings with the varying-coefficient model," Quantitative Finance, Taylor & Francis Journals, vol. 13(12), pages 1947-1965, December.
    6. Antonio Davila & George Foster & Xiaobin He & Carlos Shimizu, 2015. "The rise and fall of startups: Creation and destruction of revenue and jobs by young companies," Australian Journal of Management, Australian School of Business, vol. 40(1), pages 6-35, February.
    7. Masahiro Enomoto, 2018. "Effects of Corporate Governance on the Relationship between Accounting Quality and Trade Credit: Evidence from Japan," Discussion Paper Series DP2018-12, Research Institute for Economics & Business Administration, Kobe University, revised Dec 2023.
    8. Chen, Peimin & Wu, Chunchi, 2014. "Default prediction with dynamic sectoral and macroeconomic frailties," Journal of Banking & Finance, Elsevier, vol. 40(C), pages 211-226.
    9. Knyazeva, Anzhela & Knyazeva, Diana, 2012. "Does being your bank’s neighbor matter?," Journal of Banking & Finance, Elsevier, vol. 36(4), pages 1194-1209.
    10. Giordani, Paolo & Jacobson, Tor & Schedvin, Erik von & Villani, Mattias, 2014. "Taking the Twists into Account: Predicting Firm Bankruptcy Risk with Splines of Financial Ratios," Journal of Financial and Quantitative Analysis, Cambridge University Press, vol. 49(4), pages 1071-1099, August.
    11. Li, Chunyu & Lou, Chenxin & Luo, Dan & Xing, Kai, 2021. "Chinese corporate distress prediction using LASSO: The role of earnings management," International Review of Financial Analysis, Elsevier, vol. 76(C).
    12. Suzan Hol, 2006. "The influence of the business cycle on bankruptcy probability," Discussion Papers 466, Statistics Norway, Research Department.
    13. Gropp, R. & Grundl, C. & Guttler, A., 2012. "Does Discretion in Lending Increase Bank Risk? Borrower Self-Selection and Loan Officer Capture Effects," Other publications TiSEM bfec5360-2a2b-47e4-ba3f-d, Tilburg University, School of Economics and Management.
    14. Pavol Durana & Lucia Michalkova & Andrej Privara & Josef Marousek & Milos Tumpach, 2021. "Does the life cycle affect earnings management and bankruptcy?," Oeconomia Copernicana, Institute of Economic Research, vol. 12(2), pages 425-461, June.
    15. Dinh, K. & Kleimeier, S., 2006. "Credit scoring for Vietnam's retail banking market : implementation and implications for transactional versus relationship lending," Research Memorandum 012, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    16. Park, Moon Deok & Han, Seung Hun, 2023. "Pay dispersion and CSR," Finance Research Letters, Elsevier, vol. 51(C).
    17. Simon Cornée, 2014. "Soft Information and Default Prediction in Cooperative and Social Banks," Journal of Entrepreneurial and Organizational Diversity, European Research Institute on Cooperative and Social Enterprises, vol. 3(1), pages 89-103, June.
    18. Elizaveta Danilova & Evgeny Rumyantsev & Ivan Shevchuk, 2018. "Review of the Bank of Russia – IMF Workshop 'Recent Developments in Macroprudential Stress Testing'," Russian Journal of Money and Finance, Bank of Russia, vol. 77(4), pages 60-83, December.
    19. Alderson, Michael J. & Betker, Brian L. & Halford, Joseph T., 2021. "Fictitious dividend cuts in the CRSP data," Journal of Corporate Finance, Elsevier, vol. 71(C).
    20. Pesaran, M. Hashem & Schuermann, Til & Treutler, Bjorn-Jakob & Weiner, Scott M., 2006. "Macroeconomic Dynamics and Credit Risk: A Global Perspective," Journal of Money, Credit and Banking, Blackwell Publishing, vol. 38(5), pages 1211-1261, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:50:y:2004:i:6:p:709-723. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.