IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v40y1992i1p178-187.html
   My bibliography  Save this article

A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem

Author

Listed:
  • J. Kennington

    (Southern Methodist University, Dallas, Texas)

  • Z. Wang

    (Southern Methodist University, Dallas, Texas)

Abstract

The objective of this study is to develop a shortest augmenting path algorithm for solving the semi-assignment problem and conduct an extensive computational comparison with the best alternative approaches. The algorithm maintains dual feasibility and complementary slackness and works toward satisfying primal feasibility. Effective heuristics arc used to achieve an excellent advanced start, and convergence is assured via the use of the shortest augmenting path procedure using reduced costs for arc lengths. Unlike other algorithms, such as the primal simplex or the auction algorithm, each iteration during the final phase of the procedure (also known as the end-game) achieves one additional assignment. The software implementations of our algorithm are fastest for the semi-assignment problems that we tested. Our dense code is also faster than the best software for assignment problems. In addition, the algorithm has the best polynomial worst-case running time bound that we have seen; and the memory requirements are relatively small.

Suggested Citation

  • J. Kennington & Z. Wang, 1992. "A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem," Operations Research, INFORMS, vol. 40(1), pages 178-187, February.
    • Handle: RePEc:inm:oropre:v:40:y:1992:i:1:p:178-187
    DOI: 10.1287/opre.40.1.178
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.40.1.178
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.40.1.178?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
    ---><---

    Citations

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


    Cited by:

    1. Jonker, R. & Volgenant, A., 1999. "Linear assignment procedures," European Journal of Operational Research, Elsevier, vol. 116(1), pages 233-234, July.
    2. Andreas Kleine & Andreas Dellnitz, 2017. "Allocation of seminar applicants," Journal of Business Economics, Springer, vol. 87(7), pages 927-941, October.
    3. Andreas Dellnitz & Damian Pozo & Jochen Bauer & Andreas Kleine, 2023. "Practice Summary: Seminar Assignments in a University—MATLAB-Based Decision Support," Interfaces, INFORMS, vol. 53(4), pages 307-311, July.
    4. Ioannis T. Christou & Armand Zakarian & Jun-Min Liu & Helen Carter, 1999. "A Two-Phase Genetic Algorithm for Large-Scale Bidline-Generation Problems at Delta Air Lines," Interfaces, INFORMS, vol. 29(5), pages 51-65, October.
    5. Volgenant, A., 2004. "Solving the k-cardinality assignment problem by transformation," European Journal of Operational Research, Elsevier, vol. 157(2), pages 322-331, September.
    6. Pentico, David W., 2007. "Assignment problems: A golden anniversary survey," European Journal of Operational Research, Elsevier, vol. 176(2), pages 774-793, January.
    7. Yuli Zhang & Zuo-Jun Max Shen & Shiji Song, 2018. "Exact Algorithms for Distributionally β -Robust Machine Scheduling with Uncertain Processing Times," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 662-676, November.
    8. Volgenant, A., 2004. "A note on the assignment problem with seniority and job priority constraints," European Journal of Operational Research, Elsevier, vol. 154(1), pages 330-335, April.

    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:oropre:v:40:y:1992:i:1:p:178-187. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.