Skip to main content
SpringerLink
Log in

Towards auction algorithms for large dense assignment problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper, we focus on the problem of solving large-scale instances of the linear sum assignment problem by auction algorithms. We introduce a modified auction algorithm, called look-back auction algorithm, which extends the forward auction algorithm by the ability of reusing information from previous bids. We show that it is able to reuse information from the previous bids with high efficiency for all tested types of input instances. We discuss then the design and implementation of a suite of sequential and distributed memory auction algorithms on a Linux cluster with the evaluation on several types of input instances of the linear sum assignment problem. Our results show that the look-back auction algorithm solves sequentially nearly all types of dense instances faster than other evaluated algorithms and it is more stable than the forward-reverse auction algorithm for sparse instances. Our distributed memory auction algorithms are fully memory scalable.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Balas, E., Miller, D., Pekny, J., Toth, P.: A parallel shortest path algorithm for the assignment problem. J. ACM 38, 985–1004 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  2. Belongie, S., Malik, J., Puzicha, J.: Shape matching and object recognition using shape contexts. IEEE Trans. Pattern Anal. Mach. Intel. 24(24), 509–522 (2002)

    Article  Google Scholar 

  3. Bertsekas, D., Castañon, D.: A forward/reverse auction algorithm for asymmetric assignment problems. Comput. Optim. Appl. 1(3), 277–297 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bertsekas, D.P.: A distributed algorithm for the assignment problem. Laboratory for Information and Decision Systems Working Paper, (M.I.T.), March 1979

  5. Bertsekas, D.P.: A new algorithm for the assignment problem. Math. Program. 21, 152–171 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bertsekas, D.P.: Linear Network Optimization: Algorithms and Codes. MIT Press, Cambridge (1991)

    MATH  Google Scholar 

  7. Bertsekas, D.P.: Network Optimization: Continuous and Discrete Models. Athena Scientific, Belmont (1998)

    MATH  Google Scholar 

  8. Bertsekas, D.P., Castañon, D.A.: Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput. 17(6–7), 707–732 (1991)

    Article  MATH  Google Scholar 

  9. Bertsekas, D.P., Castañon, D.A.: Parallel asynchronous hungarian methods for the assignment problem. ORSA J. Comput. 5, 261–274 (1993)

    MATH  Google Scholar 

  10. Bertsekas, D.P., Castañon, D.A., Tsaknakis, H.: Reverse auction algorithm and the solution of inequality constrained assignment problems. SIAM J. Optim. 3, 268–299 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  11. Brady, M., Jung, K.K., Nguyen, H.T., Raghavan, R., Subramonian, R.: The assignment problem on parallel architectures. In: Network Flows and Matching. DIMACS, pp. 469–517. American Mathematical Society, Providence (1993)

    Google Scholar 

  12. Burkard, R.E., Çela, E.: Linear assignment problems and extensions. In: Handbook of Combinatorial Optimization, pp. 75–149. Kluwer Academic, Dordrecht (1999)

    Google Scholar 

  13. Buš, L., Tvrdík, P.: Look-back auction algorithm for the assignment problem and its distributed memory implementation. In: Proceedings of the 15th IASTED International Conference Parallel and Distributed Computing and Systems, pp. 551–556. Acta Press, Anaheim (2003)

    Google Scholar 

  14. Castañon, D.A.: Reverse auction algorithms for assignment problems. In: Network Flows and Matching. DIMACS, pp. 407–429. American Mathematical Society, Providence (1993)

    Google Scholar 

  15. Duff, I.S., Koster, J.: On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM J. Matrix Anal. Appl. 22(4), 973–996 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  16. Frieze, A., Galbiati, G., Maffioli, F.: On the worst-case performance on some algorithms fo the asymmetric traveling salesman problem. Networks 12, 23–39 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  17. Glover, F., Gutin, G., Yeo, A., Zverovich, A.: Contruction heuristics and domination analysis for the asymmetric tsp. Eur. J. Oper. Res. 129, 555–568 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  18. Goldberg, A., Kennedy, R.: An efficient cost scaling algorithm for the assignment problem. Math. Program. 75, 153–177 (1995)

    MathSciNet  Google Scholar 

  19. Goldberg, A., Plotkin, S., Shmoys, D., Tardos, E.: Using interior point methods for fast parallel algorithms for bipartite matching and related problems. SIAM J. Comput. 21(1), 140–150 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  20. Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325–340 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  21. Karp, R.M., Steele, J.M.: Probabilistic analysis of heuristics. In: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)

    Google Scholar 

  22. Korimont, T., Burkard, R., Çela, E.: An interior point approach for weighted bipartite matching. Technical Report FB196, Technische University Graz (2000)

  23. Kuhn, H.W.: The hungarian method for the assignment and transpotation problems. Nav. Res. Logist. Q. 2, 83–97 (1955)

    Article  MathSciNet  Google Scholar 

  24. Machol, R., Wien, M.: A ‘hard’ assignment problem. Oper. Res. 24, 190–192 (1976)

    Article  MATH  Google Scholar 

  25. Miller, D.L., Pekny, J.F.: Exact solution of large asymmetric traveling salesman problems. Science 251, 754–761 (1991)

    Article  Google Scholar 

  26. Ramakrishnan, K.G., Karmarkar, N.K., Kamath, A.P.: An approximate dual projective algorithm for solving assignment problems. In: Network Flows and Matching. DIMACS, pp. 431–451. American Mathematical Society, Providence (1993)

    Google Scholar 

  27. Schütt, C., Clausen, J.: Parallel algorithms for the assignment problem—an experimental evaluation of three distributed algorithms. In: Parallel Processing of Discrete Optimization Problems. DIMACS, pp. 337–351. American Mathematical Society, Providence (1995)

    Google Scholar 

  28. Schwartz, B.L.: A computational analysis of the auction algorithm. Eur. J. Oper. Res. 74, 161–169 (1994)

    Article  MATH  Google Scholar 

  29. Zhang, W.: Truncated branch-and-bound: A case study on the asymmetric tsp. In: Proceedings of AAAI 1993 Spring Symposium: AI and NP-Hard Problems, pp. 160–166. Stanford, CA (1993)

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Czech Technical University, Prague, Czech Republic

    Libor Buš & Pavel Tvrdík

Authors
  1. Libor Buš
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pavel Tvrdík
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pavel Tvrdík.

Additional information

This research has been supported by IGA CTU under grant CTU0308013 and under research program MSMT 6840770014.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Buš, L., Tvrdík, P. Towards auction algorithms for large dense assignment problems. Comput Optim Appl 43, 411–436 (2009). https://doi.org/10.1007/s10589-007-9146-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-007-9146-5

Keywords

Search

Navigation