Maksimal fordeling efter rang

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. januar 2021; verifikation kræver 1 redigering .

Rang- maksimal ( RM) allokering er reglen for en retfærdig opdeling af udelelige poster .  Antag, at vi skal fordele flere varer blandt et vist antal personer. Hver person kan rangere genstande fra bedst til værst. MP-reglen siger, at vi skal give så mange mennesker som muligt den bedste genstand (#1 på listen). Så bør vi give så mange mennesker som muligt det næstvigtigste punkt (#2 på listen) og så videre.

I det specielle tilfælde, hvor hver person skal modtage én genstand (f.eks. hvis "emnerne" er nogle handlinger, og hver handling skal udføres af én person), kaldes problemet maksimal rang -matching eller grådig matching .

Idéen ligner den med at skære kagen ud efter nytte , hvor målet er at maksimere summen af ​​alle deltageres nytteværdi. Brugsreglen fungerer dog med kardinal (mængde) nyttefunktioner , mens MP-reglen fungerer med ordinal hjælpeprogrammer (rangering).

Definitioner

Der er flere varer og flere agenter. Hver agent har en lineær bestilling af varer. Agenter værdsætter muligvis ikke visse genstande. For hver agent kan vi opdele elementer i ækvivalensklasser, der indeholder elementer af samme rang. For eksempel, hvis Alices præferencerelation er x > y, z > w , betyder det, at Alices bedste valg er x , hvilket er bedre end alle andre elementer. Alice foretrækker så y og z , som i hendes øjne har samme værdi, men ikke er så værdifulde som x . På sidstepladsen har Alice w , som hun betragter som den værste af alle genstande.

For enhver distribution af varer til agenter konstruerer vi dens rangvektor som følger. Element #1 i vektoren er lig med det samlede antal elementer, der er på førstepladsen for ejere, element #2 er lig med det samlede antal elementer, der er på andenpladsen for ejere, og så videre.

Den maksimale rangfordeling er den fordeling, hvor rangvektoren er maksimal (i leksikografisk rækkefølge ).

Eksempel

De tre elementer, x, y og z, skal deles mellem tre agenter, hvis rangering er som følger:

• Alice: x > y > z
• Bob: x > y > z
• Carl: y > x > z

I fordelingen ( x , y , z ) får Alice det første element ( x ), Bob får det andet element ( y ), og Carl får det tredje element ( z ). Rangvektoren er da (1,1,1).

I fordelingen ( x , z , y ) får Alice og Carl emnerne på førstepladsen, mens Bob får genstanden, som han placerer på 3. pladsen. Rangvektoren er så (2,0,1), hvilket er leksikografisk større end (1,1,1) vektoren - det giver flere valg af 1. pladsen.

Det er let at kontrollere, at ingen fordeling giver en leksikografisk større rangvektor. Derfor er fordelingen ( x , z , y ) maksimal i rang. Tilsvarende er fordelingen ( z , x , y ) rang-maksimum - den giver samme rangvektor (2,0,1).

Algoritmer

MP-matchninger blev først undersøgt af Robert Irving, som kaldte dem grådige matchninger . Han foreslog en algoritme , der finder en MP - matchning i tid , hvor n er antallet af agenter og c er den maksimale længde af agentens præferenceliste [1] .

Senere blev der fundet en algoritme, der kører i tid , hvor m er den samlede længde af alle præferencelister (det samlede antal kanter i grafen), og C er den maksimale rangering af det element, der blev brugt i MP-matchningen (dvs. det maksimale antal ikke-nul elementer i den optimale rangvektor) [2] .

En anden løsning med maksimal vægttilpasning opnår en lignende køretid - [3] .

Indstillinger

Opgaven har flere muligheder.

1. I en MP-matchning af maksimal kardinalitet er målet at finde blandt alle forskellige MP-matches matchningen med det maksimale antal kombinationer.

2. I en fair matchning er målet at finde en maksimal kardinalitetsmatchning, der bruger det mindste antal kanter af rang r , derefter minimum antal kanter af rang r −1, og så videre.

Både den maksimale størrelse MP-matchning og den rimelige matchning kan findes ved at reducere til den maksimale vægtmatchning [3] .

3. I problemet med kapacitiv MR-matching har hver agent en øvre kapacitet, som bestemmer den øvre grænse for det samlede antal genstande, der kan overføres til agenten. Hver vare har en øvre kvote, som angiver en øvre grænse for antallet af forskellige agenter, som varen kan gives til. Problemet blev undersøgt af Melhorn og Mikhail, som foreslog en algoritme med køretid [4] . Der er en forbedret algoritme med køretid , hvor B er minimumsummen af ​​agentkvoter og summen af ​​varekvoter. Det er baseret på en udvidelse af Galai-Edmonds-nedbrydningen af multi-edge matching [5] .

Se også

• Fair fordeling af genstande
• Ægteskabsproblem
• Matchende uden misundelse

Noter

1. ↑ Irving, 2003 , s. Tr–2003–136.
2. ↑ Irving, Kavitha et al., 2006 , s. 602-610.
3. ↑ 12 Michail , 2007 , s. 125-132.
4. ↑ Mehlhorn, Michail, 2005 .
5. ↑ Paluch, 2013 , s. 324-335.

Litteratur

• Robert W. Irving. Grådige matchninger. - University of Glasgow, 2003. - (Teknisk rapport).
• Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch. Rang-maksimale matchninger // ACM Trans. algoritmer. - 2006. - Oktober (vol. 2 ( udgave 4 ). - S. 602–610 . - ISSN 1549-6325 . - doi : 10.1145/1198513.1198520 .
• Dimitrios Michail. Reduktion af rang-maksimal til maksimal vægtmatching // Teoretisk datalogi. - 2007. - December (bd. 389). — ISSN 0304-3975 . - doi : 10.1016/j.tcs.2007.08.004 .
• Kurt Mehlhorn, Dimitrios Michail. Netværksproblemer med ikke-polynomiale vægte og applikationer . - 2005.
• Katarzyna Paluch. Kapaciterede rang-maksimum matchninger. — Algoritmer og kompleksiteter. - Springer, Berlin, Heidelberg, 2013. - T. 7878. - (Lecture Notes in Computer Science). — ISBN 978-3-642-38232-1 . - doi : 10.1007/978-3-642-38233-8_27 .