Distribuție maximă pe rang

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 ianuarie 2021; verificarea necesită 1 editare .

Alocarea cu rang maxim ( RM) este regula pentru o împărțire corectă a articolelor indivizibile . Să presupunem că trebuie să distribuim mai multe articole într-un anumit număr de oameni. Fiecare persoană poate clasifica articolele de la cel mai bun la cel mai rău. Regula MP spune că ar trebui să oferim cât mai multor oameni posibil cel mai bun articol (nr. 1 pe listă). Atunci ar trebui să dăm cât mai multor persoane al doilea cel mai important element (#2 pe listă) și așa mai departe.

În cazul special în care fiecare persoană trebuie să primească un articol (de exemplu, dacă „articolele” sunt niște acțiuni, iar fiecare acțiune trebuie efectuată de o persoană), problema se numește potrivire de rang maxim sau potrivire greedy .

Ideea este similară cu cea a tăierii prăjiturii în funcție de utilitate , unde scopul este de a maximiza suma utilităților tuturor participanților. Cu toate acestea, regula de utilitate funcționează cu funcții de utilitate cardinale (cantitate) , în timp ce regula MP funcționează cu utilități ordinale (clasare).

Definiții

Există mai multe articole și mai mulți agenți. Fiecare agent are o ordonare liniară a articolelor. Este posibil ca agenții să nu aprecieze anumite articole. Pentru fiecare agent, putem împărți articole în clase de echivalență care conțin articole de același rang. De exemplu, dacă relația de preferințe a lui Alice este x > y, z > w , aceasta înseamnă că cea mai bună alegere a lui Alice este x , care este mai bună decât toate celelalte elemente. Alice preferă apoi y și z , care în ochii ei au aceeași valoare, dar nu sunt la fel de valoroase ca x . Pe ultimul loc, Alice are w , pe care îl consideră cel mai rău dintre toate articolele.

Pentru orice distribuție de articole către agenți, construim vectorul de rang după cum urmează. Elementul #1 din vector este egal cu numărul total de articole care sunt pe primul loc pentru proprietari, elementul #2 este egal cu numărul total de articole care sunt pe locul doi pentru proprietari și așa mai departe.

Distribuția maximă de rang este distribuția în care vectorul de rang este maxim (în ordine lexicografică ).

Exemplu

Cele trei elemente, x, y și z, trebuie împărțite între trei agenți, a căror clasare este următoarea:

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

În distribuția ( x , y , z ), Alice obține primul element ( x ), Bob primește al doilea element ( y ), iar Carl primește al treilea element ( z ). Vectorul rang este atunci (1,1,1).

În distribuție ( x , z , y ), Alice și Carl primesc articolele pe primul loc, în timp ce Bob primește elementul pe care îl plasează pe locul 3. Vectorul de rang este atunci (2,0,1), care este mai mare din punct de vedere lexicografic decât vectorul (1,1,1) - oferă mai multor oameni să aleagă locul 1.

Este ușor de verificat că nicio distribuție nu oferă un vector de rang lexicografic mai mare. Prin urmare, distribuția ( x , z , y ) este maximă în rang. În mod similar, distribuția ( z , x , y ) este de rang maxim - dă același vector de rang (2,0,1).

Algoritmi

Potrivirile MP au fost studiate pentru prima dată de Robert Irving, care le-a numit potriviri lacome . El a propus un algoritm care găsește o potrivire MP în timp , unde n este numărul de agenți și c este lungimea maximă a listei de preferințe a agentului [1] . $O(n^{2}c^{3})$

Mai târziu, a fost găsit un algoritm care rulează în timp , unde m este lungimea totală a tuturor listelor de preferințe (numărul total de margini din grafic), iar C este rangul maxim al articolului utilizat în potrivirea MP (adică, numărul maxim de elemente nenule în vectorul de rang optim) [2] . $O(m\cdot \min(n,C{\sqrt {n)}))$

O soluție diferită care utilizează potrivirea greutății maxime realizează un timp de funcționare similar - [3] . $O(m\cdot \min(n+C,C{\sqrt {n)}))$

Opțiuni

Sarcina are mai multe opțiuni.

1. Într- o potrivire MP de cardinalitate maximă, scopul este de a găsi între toate potrivirile MP diferite potrivirea cu numărul maxim de combinații.

2. Într -o potrivire corectă, scopul este de a găsi o potrivire de cardinalitate maximă care utilizează numărul minim de muchii ale rangului r , apoi numărul minim de muchii ale rangului r −1 și așa mai departe.

Atât potrivirea dimensiunii maxime MP, cât și potrivirea corectă pot fi găsite prin reducerea la potrivirea greutății maxime [3] .

3. În problema potrivirii MR capacitive, fiecare agent are o capacitate superioară, care determină limita superioară a numărului total de articole care pot fi transferate agentului. Fiecare articol are o cotă superioară, care specifică o limită superioară a numărului de agenți diferiți cărora le poate fi dat articolul. Problema a fost studiată de Melhorn și Mikhail, care au propus un algoritm cu timp de rulare [4] . Există un algoritm îmbunătățit cu durata de rulare , unde B este suma minimă a cotelor de agenți și a sumelor cotelor de articole. Se bazează pe o extensie a descompunere Galai-Edmonds a potrivirilor cu mai multe muchii [5] . $O(Cnm\log(n^{2}/m)\log(n))$ $O(m\cdot \min(B,C{\sqrt {B)}))$

Vezi și

Note

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

Literatură

Robert W. Irving. Potriviri lacome. - Universitatea din Glasgow, 2003. - (Raport tehnic).
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch. Potriviri maxime de rang // ACM Trans. algoritmi. - 2006. - Octombrie (vol. 2 ( numărul 4 ). - S. 602–610 . - ISSN 1549-6325 . - doi : 10.1145/1198513.1198520 .
Dimitrios Mihail. Reducerea gradului de potrivire a greutății maxime la maximă // Informatică teoretică. - 2007. - Decembrie (vol. 389). — ISSN 0304-3975 . - doi : 10.1016/j.tcs.2007.08.004 .
Kurt Mehlhorn, Dimitrios Michail. Probleme de rețea cu greutăți și aplicații non-polinomiale . — 2005.
Katarzyna Paluch. Capacitate Rang-Potriviri maxime. — Algoritmi și complexități. - 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 .