Maximal fördelning efter rang

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 januari 2021; verifiering kräver 1 redigering .

Rank- maximal ( RM) allokering är regeln för en rättvis uppdelning av odelbara poster . Anta att vi behöver fördela flera föremål bland ett visst antal personer. Varje person kan rangordna objekt från bäst till sämst. MP-regeln säger att vi ska ge så många som möjligt det bästa objektet (#1 på listan). Sedan ska vi ge så många som möjligt den näst viktigaste punkten (#2 på listan) och så vidare.

I det speciella fallet där varje person måste få ett föremål (till exempel om "objekten" är några åtgärder, och varje åtgärd måste utföras av en person), kallas problemet för maximal rangmatchning eller girig matchning .

Tanken liknar den att skära kakan efter nytta , där målet är att maximera summan av nyttan för alla deltagare. Emellertid fungerar verktygsregeln med kardinal (kvantitet) nyttofunktioner medan MP-regeln fungerar med ordinal utilities (rankning).

Definitioner

Det finns flera föremål och flera agenter. Varje agent har en linjär ordning av artiklar. Agenter kanske inte värderar vissa föremål. För varje agent kan vi dela upp föremål i ekvivalensklasser som innehåller föremål av samma rang. Till exempel, om Alices preferensrelation är x > y, z > w , betyder det att Alices bästa val är x , vilket är bättre än alla andra objekt. Alice föredrar då y och z , som i hennes ögon har samma värde men inte är lika värda som x . På sista plats har Alice w , som hon anser vara det sämsta av alla föremål.

För all distribution av föremål till agenter konstruerar vi dess rangvektor enligt följande. Element #1 i vektorn är lika med det totala antalet objekt som är på första plats för ägare, element #2 är lika med det totala antalet objekt som är på andra plats för ägare, och så vidare.

Den maximala rangfördelningen är den fördelning där rangvektorn är maximal (i lexikografisk ordning ).

Exempel

De tre objekten, x, y och z, ska delas upp på tre agenter, vars rankning är som följer:

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

I fördelningen ( x , y , z ) får Alice det första elementet ( x ), Bob får det andra elementet ( y ), och Carl får det tredje elementet ( z ). Rangvektorn är då (1,1,1).

I fördelningen ( x , z , y ) får Alice och Carl objekten på första plats, medan Bob får objektet som han placerar på 3:e plats. Rangvektorn är då (2,0,1), vilket är lexikografiskt större än (1,1,1) vektorn - det ger fler personer valet av 1:a plats.

Det är lätt att kontrollera att ingen fördelning ger en lexikografiskt större rangvektor. Därför är fördelningen ( x , z , y ) maximal i rang. På samma sätt är fördelningen ( z , x , y ) rank-maximum - den ger samma rankvektor (2,0,1).

Algoritmer

MP-matchningar studerades först av Robert Irving, som kallade dem giriga matchningar . Han föreslog en algoritm som hittar en MP -matchning i tid , där n är antalet agenter och c är den maximala längden på agentens preferenslista [1] . $O(n^{2}c^{3})$

Senare hittades en algoritm som körs i tiden , där m är den totala längden på alla preferenslistor (det totala antalet kanter i grafen), och C är den maximala rangordningen för objektet som används i MP-matchningen (det vill säga, det maximala antalet element som inte är noll i den optimala rangvektorn) [2] . $O(m\cdot \min(n,C{\sqrt {n))))$

En annan lösning med maximal viktmatchning uppnår en liknande körtid - [3] . $O(m\cdot \min(n+C,C{\sqrt {n))))$

Alternativ

Uppgiften har flera alternativ.

1. I en MP-matchning av maximal kardinalitet är målet att bland alla olika MP-matchningar hitta matchningen med det maximala antalet kombinationer.

2. I en rättvis matchning är målet att hitta en maximal kardinalitetsmatchning som använder det minsta antalet kanter av rang r , sedan det minsta antalet kanter av rang r −1, och så vidare.

Både maximal storlek MP-matchning och rättvis matchning kan hittas genom att minska till maximal viktmatchning [3] .

3. I problemet med kapacitiv MR-matchning har varje agent en övre kapacitet, som bestämmer den övre gränsen för det totala antalet artiklar som kan överföras till agenten. Varje artikel har en övre kvot, som anger en övre gräns för antalet olika agenter som varan kan ges. Problemet studerades av Melhorn och Mikhail, som föreslog en algoritm med körtid [4] . Det finns en förbättrad algoritm med körtid , där B är minimisumman av agentkvoter och summor av artikelkvoter. Den är baserad på en förlängning av Galai-Edmonds nedbrytning av flerkantsmatchningar [5] . $O(Cnm\log(n^{2}/m)\log(n))$ $O(m\cdot \min(B,C{\sqrt {B))))$

Se även

Anteckningar

↑ Irving, 2003 , sid. Tr–2003–136.
↑ Irving, Kavitha et al., 2006 , sid. 602–610.
↑ 12 Michail , 2007 , sid. 125–132.
↑ Mehlhorn, Michail, 2005 .
↑ Paluch, 2013 , sid. 324–335.

Litteratur

Robert W. Irving. Giriga matchningar. - University of Glasgow, 2003. - (Teknisk rapport).
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch. Rank-maximal Matchningar // ACM Trans. algoritmer. - 2006. - Oktober (vol. 2 ( nummer 4 ). - S. 602–610 . - ISSN 1549-6325 . - doi : 10.1145/1198513.1198520 .
Dimitrios Michail. Minskning av rang-maximal till maximal viktmatchning // Teoretisk datavetenskap. - 2007. - December (vol. 389). — ISSN 0304-3975 . - doi : 10.1016/j.tcs.2007.08.004 .
Kurt Mehlhorn, Dimitrios Michail. Nätverksproblem med icke-polynomiska vikter och applikationer . — 2005.
Katarzyna Paluch. Kapaciterade Rank-Maximum Matchningar. — Algoritmer och komplexiteter. - 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 .