Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Swift Logic for Big Data and Knowledge Graphs Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

House Allocation Problems with Existing Tenants and Priorities for Teacher Recruitment

verfasst von : Ana Paula Tomás

Erschienen in: SOFSEM 2018: Theory and Practice of Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study a variant of house allocation problems with application to a real-world job assignment problem where some applicants cannot result unmatched. Such applicants hold posts initially, which enter the market if they can get strictly better posts. All applicants are strictly ordered by priority in a single master list. Their preference lists may be incomplete and may contain ties. We seek a matching that assigns the best possible post to each applicant, taking into account their preferences, priorities and initial posts. We give algorithms for solving the problem in polynomial time for three different cases.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Michiko: Poem Models used in Automated Haiku Poetry Generation
Nächstes Kapitel Runtime Distributions and Criteria for Restarts
Literatur
1.
Abdulkadiroğlu, A., Sönmez, T.: House allocation with existing tenants. J. Econ. Theory 88, 233–260 (1999)CrossRefMATH
2.
Abraham, D.J., Irving, R.W., Kavitha, R., Mehlhorn, K.: Popular matchings. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 424–432. SIAM (2005)
3.
4.
Cechlárová, K., Fleiner, T., Manlove, D.F., McBride, I.: Stable matchings of teachers to schools. Theoret. Comput. Sci. 653, 15–25 (2016)MathSciNetCrossRefMATH
5.
6.
Goldberg, A.V., Kaplan, H., Hed, S., Tarjan, R.E.: Minimum cost flows in graphs with unit capacities. In: Mayr, E.W., Ollinger, N. (eds.) STACS 2015, pp. 406–419 (2015)
7.
Gusfield, D., Irving, R.W.: The Stable Marriage Problem - Structure and Algorithms. MIT Press, Cambridge (1989)MATH
8.
9.
Irving, R.W.: Greedy matchings. University of Glasgow, Computing Science Department Research report, TR-2003-136, April 2003
10.
Irving, R.W., Manlove, D.F., Scott, S.: The stable marriage problem with master preference lists. Discret. Appl. Math. 156(15), 2959–2977 (2008)MathSciNetCrossRefMATH
11.
Irving, R.W., Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: Rank-maximal matchings. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 68–75. SIAM (2004)
12.
13.
Krysta, P., Manlove, D., Rastegari, B., Zhang, J.: Size versus truthfulness in the House Allocation problem. In: Proceedings of the EC 2014 15th ACM Conference on Economics and Computation, pp. 453–470. ACM (2014)
14.
15.
Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific, Singapore (2013)CrossRefMATH
16.
Manlove, D.F., Irving, R., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theoret. Comput. Sci. 276, 261–279 (2002)MathSciNetCrossRefMATH
17.
18.
Niederle, M., Roth, A.E., Sönmez, T.: Matching. In: The New Palgrave Dictionary of Economics, 2nd edn. Palgrave Macmillan (2007)
19.
Roth, A.E.: The evolution of the labor market for interns and residents: a case study in game theory. J. Polit. Econ. 92, 991–1016 (1984)CrossRef
20.
21.
Sng, C.T.S., Manlove, D.F.: Popular matchings in the weighted capacitated house allocation problem. J. Discret. Algorithms 8, 102–116 (2010)MathSciNetCrossRefMATH
22.
Wolsey, L.A.: Integer Programming. Wiley-Interscience, Hoboken (1998)MATH
23.
Yuan, R.: Residence exchange wanted: a stable residence exchange problem. Eur. J. Oper. Res. 90, 536–546 (1996)CrossRefMATH
24.
25.
Tomás, A.P.: Weak stable matchings with tenants and ties. Presented at CSCLP 2006: Annual ERCIM Workshop on Constraint Solving and Constraint Logic Programming, Lisbon, Portugal, June 2006
Metadaten
Titel
House Allocation Problems with Existing Tenants and Priorities for Teacher Recruitment
verfasst von
Ana Paula Tomás
Copyright-Jahr
2018
Buch
SOFSEM 2018: Theory and Practice of Computer Science

Print ISBN: 978-3-319-73116-2

Electronic ISBN: 978-3-319-73117-9

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-73117-9_34