Complexity of the Resource Allocation/Matching Problem with Weight Based Ceilings | SpringerLink
Skip to main content
Springer Nature Link
Log in

Complexity of the Resource Allocation/Matching Problem with Weight Based Ceilings

  • Conference paper
Algorithms and Architectures for Parallel Processing (ICA3PP 2012)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7440))

Abstract

Assigning elements of one set to elements of another set is a common occurrence. This has to be done so that certain objectives are met. In some situations, matching between two different sets is done according to preferences of either one set or both. At the same time, in many cases, a ceiling beyond which the allocations can no longer be made exist. Oftentimes, such a ceiling is made on numbers not on weights (for homogeneous tasks/actors, numbers and weights are synonymous). In this paper, we consider allocations where the tasks and actors are not necessarily homogeneous and the allocation ceilings are based on weights rather than numbers. We develop the algorithm using the Gale and Shapely algorithm for the stable marriage problem as the novel set up. We show that the problem can be solved in polynomial time with worst case being quadratic and best case being linear. We also make sensitivity studies on selected parameters.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Campbell, A., Wu, A.S.: Learning and Exploiting Knowledge in Multi-Agent Task Allocation Problems. In: Proceedings of the 2007 GECCO Conference Companion on Genetic and Evolutionary Computation, pp. 2637–2642 (2007)

    Google Scholar 

  2. Roth, A.E., Sotomayor, M.A.O.: Two-sided matching: a study in game-theoretic modeling and analysis. Econometric Society Monographs, vol. 18. Cambridge University Press, Cambridge (1990)

    MATH  Google Scholar 

  3. Mills-Tettey, G.A., Stentz, A., Dias, M.B.: The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs. Technical Report 7-2007, Robotics Institute-Carnegie Mellon University (July 2007)

    Google Scholar 

  4. Gerkey, B.: A formal analysis and taxonomy of task allocation in multirobot systems. Intl. J. of Robotics Research 23(9), 939–954 (2004)

    Article  Google Scholar 

  5. Zhou, C.: Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times. Annals of Operations Research 107(1-4), 65–81 (2001)

    MathSciNet  MATH  Google Scholar 

  6. Gale, D., Shapley, L.S.: College admissions and the stability of marriage. American Mathematical Monthly 69, 9–15 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  7. Gale, D., Sotomayor, M.: Some remarks on the stable matching problem. Discrete Applied Mathematics 11(3), 223–232 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  8. Manlove, D., Irving, R.W., Iwama, K., Miyaziki, S., Morita, Y.: Hard variants of stable marriage. Theoretical Computer Science 276(1-2), 261–279 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  9. de Weerdt, M., van der Krogt, R.: Inefficiencies in Task Allocation for Multiagent Planning with Bilateral Deals. In: Proceedings of the 25th Workshop of the UK Planning and Scheduling Special Interest Group, PlanSIG, pp. 33–38 (2007)

    Google Scholar 

  10. McVitie, D.G., Wilson, L.B.: The Stable Marriage Problem. Communications of the ACM 144, 486–492 (2006)

    MathSciNet  Google Scholar 

  11. Irving, R.: Stable marriage and indifference. Discrete Applied Mathematics 48, 261–272 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  12. Irving, R.W., Manlove, D.F., Scott, S.: The Hospitals/Residents Problem with Ties. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 259–271. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  13. Shen, W.: Distributed manufacturing scheduling using intelligent agents. IEEE Intelligent Systems Magazine 17(1), 88–94 (2002)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Computing and Information Sciences, Department of Computer Science, Makerere University, Uganda

    Charles Karemera & John Ngubiri

Authors
  1. Charles Karemera
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. John Ngubiri
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Information Technology, Deakin University, Melbourne Burwood Campus, 221 Burwood Highway, 3125, Burwood, VIC, Australia

    Yang Xiang

  2. SEECS, University of Ottawa, 8, King Edward Ave, K1N 6N5, Ottawa, ON, Canada

    Ivan Stojmenovic

  3. Department of Intelligent Informatics, Kyushu Sangyo University, 2-3-1 Matsukadai, Higashi-ku, 813-8503, Fukuoka, Japan

    Bernady O. Apduhan

  4. School of Information Science and Engineering, Central South University, 410083, Changsha, Hunan Province, P.R. China

    Guojun Wang

  5. Department of Information Engineering, Hiroshima University, 1-4-1, Kagamiyama, 739-8527, Higashi-Hiroshima, Japan

    Koji Nakano

  6. School of Information Technologies, University of Sydney, Building J12, 2006, Sydney, NSW, Australia

    Albert Zomaya

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Karemera, C., Ngubiri, J. (2012). Complexity of the Resource Allocation/Matching Problem with Weight Based Ceilings. In: Xiang, Y., Stojmenovic, I., Apduhan, B.O., Wang, G., Nakano, K., Zomaya, A. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2012. Lecture Notes in Computer Science, vol 7440. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33065-0_26

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-33065-0_26

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-33064-3

  • Online ISBN: 978-3-642-33065-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics