Suurin jakautuminen sijoituksen mukaan

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. tammikuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Rank- maksimaalinen ( RM) allokaatio on sääntö jakamattomien kohteiden oikeudenmukaiselle jaolle . Oletetaan, että meidän on jaettava useita esineitä tietylle määrälle ihmisiä. Jokainen voi luokitella kohteita parhaasta huonoimpaan. MP-sääntö sanoo, että meidän tulee antaa mahdollisimman monelle paras esine (listalla numero 1). Sitten meidän pitäisi antaa mahdollisimman monelle ihmiselle toiseksi tärkein kohde (nro 2 luettelossa) ja niin edelleen.

Erikoistapauksessa, jossa jokaisen henkilön on saatava yksi kohde (esimerkiksi jos "kohteet" ovat joitain toimintoja ja jokainen toiminto on suoritettava yhden henkilön toimesta), ongelmaa kutsutaan maksimitason vastaavuudeksi tai ahneeksi sovitukseksi .

Ajatus on samanlainen kuin kakun leikkaaminen hyödyn mukaan , jolloin tavoitteena on maksimoida kaikkien osallistujien hyötyjen summa. Hyödyllisyyssääntö toimii kuitenkin kardinaalien (määrä) hyödyllisyysfunktioiden kanssa, kun taas MP-sääntö toimii järjestyslukujen (ranking) kanssa.

Määritelmät

On useita kohteita ja useita agentteja. Jokaisella agentilla on lineaarinen kohteiden järjestys. Edustajat eivät välttämättä arvosta tiettyjä kohteita. Jokaiselle agentille voimme jakaa kohteet ekvivalenssiluokkiin , jotka sisältävät samanarvoisia kohteita. Esimerkiksi, jos Liisan preferenssirelaatio on x > y, z > w , tämä tarkoittaa, että Liisa paras valinta on x , joka on parempi kuin kaikki muut kohteet. Alice pitää sitten parempana y :tä ja z :tä, joilla on hänen silmissään sama arvo, mutta jotka eivät ole yhtä arvokkaita kuin x . Viimeisellä sijalla Alicella on w , jota hän pitää kaikista esineistä pahimpana.

Kun kyseessä on kohteiden jakelu agenteille, rakennamme sen sijoitusvektorin seuraavasti. Elementti #1 vektorissa on yhtä suuri kuin niiden kohteiden kokonaismäärä, jotka ovat ensimmäisellä sijalla omistajien kannalta, elementti #2 on yhtä suuri kuin niiden kohteiden kokonaismäärä, jotka ovat omistajille toisella sijalla ja niin edelleen.

Maksimijakauma on jakauma, jossa sijoitusvektori on maksimaalinen ( leksikografisessa järjestyksessä ).

Esimerkki

Kolme kohdetta, x, y ja z, jaetaan kolmen agentin kesken, joiden järjestys on seuraava:

Liisa: x > y > z
Bob: x > y > z
Carl: y > x > z

Jakaumassa ( x , y , z ), Alice saa ensimmäisen alkion ( x ), Bob saa toisen alkion ( y ) ja Carl kolmannen alkion ( z ). Sijoitusvektori on tällöin (1,1,1).

Jakaumassa ( x , z , y ) Alice ja Carl saavat kohteet ensimmäiselle sijalle, kun taas Bob saa esineen, jonka hän sijoittaa kolmannelle sijalle. Sijoitusvektori on tällöin (2,0,1), joka on leksikografisesti suurempi kuin vektori (1,1,1) - se antaa useammalle ihmiselle mahdollisuuden valita 1. sija.

On helppo tarkistaa, ettei mikään jakauma anna leksikografisesti suurempaa arvovektoria. Siksi jakauma ( x , z , y ) on maksimaalinen. Vastaavasti jakauma ( z , x , y ) on rank-max - se antaa saman arvovektorin (2,0,1).

Algoritmit

MP-sovituksia tutki ensin Robert Irving, joka kutsui niitä ahneiksi vastaavuuksiksi . Hän ehdotti algoritmia , joka löytää MP- sovituksen ajassa , missä n on agenttien lukumäärä ja c on agentin preferenssilistan maksimipituus [1] . $O(n^{2}c^{3})$

Myöhemmin löydettiin ajassa ajava algoritmi , jossa m on kaikkien preferenssiluetteloiden kokonaispituus (kaavion reunojen kokonaismäärä) ja C on MP-sovituksessa käytetyn kohteen maksimiarvo (eli nollasta poikkeavien elementtien enimmäismäärä optimaalisessa järjestysvektorissa) [2] . $O(m\cdot \min(n,C{\sqrt {n))))$

Erilainen ratkaisu, jossa käytetään maksimipainon sovitusta , saavuttaa samanlaisen käyttöajan - [3] . $O(m\cdot \min(n+C,C{\sqrt {n))))$

Vaihtoehdot

Tehtävässä on useita vaihtoehtoja.

1. Maksimikardinaalisuuden MP-sovituksessa tavoitteena on löytää kaikkien eri MP-sovitusten joukosta se, jolla on maksimimäärä yhdistelmiä.

2. Reilussa sovituksessa tavoitteena on löytää maksimikardinaliteettisovitus, joka käyttää minimimäärää asteen r särmiä , sitten minimimäärää asteen r −1 särmiä ja niin edelleen.

Sekä maksimikoon MP-sovitus että reilu vastaavuus voidaan löytää vähentämällä maksimipainosovitus [3] .

3. Kapasitiivisen MR-sovituksen ongelmassa jokaisella agentilla on yläkapasiteetti, joka määrittää agentille siirrettävien kohteiden kokonaismäärän ylärajan. Jokaisella tuotteella on yläkiintiö, joka määrittää ylärajan eri agenttien lukumäärälle, joille tuote voidaan antaa. Ongelmaa tutkivat Melhorn ja Mikhail, jotka ehdottivat algoritmia ajoajalla [4] . Käytössä on parannettu algoritmi, jossa on ajoaika , jossa B on agenttikiintiöiden ja tuotekiintiöiden vähimmäissumma. Se perustuu monireunaisten sovitusten Galai-Edmonds-hajotelman laajennukseen [5] . $O(Cnm\log(n^{2}/m)\log(n))$ $O(m\cdot \min(B,C{\sqrt {B))))$

Katso myös

Muistiinpanot

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

Kirjallisuus

Robert W. Irving. Ahneita vastaavuuksia. - Glasgow'n yliopisto, 2003. - (Tekninen raportti).
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch. Sijoitus-maksimivastaavuus // ACM Trans. algoritmeja. - 2006. - lokakuu (nide 2 ( numero 4 ). - S. 602-610 . - ISSN 1549-6325 . - doi : 10.1145/1198513.1198520 .
Dimitrios Michail. Vähennetään rank-maksimin vastaavuutta maksimipainoon // Teoreettinen tietojenkäsittelytiede. - 2007. - joulukuu (nide 389). — ISSN 0304-3975 . - doi : 10.1016/j.tcs.2007.08.004 .
Kurt Mehlhorn, Dimitrios Michail. Verkko-ongelmat ei-polynomisten painojen ja sovellusten kanssa . – 2005.
Katarzyna Paluch. Kapasitoitujen sijoitusten maksimi vastaavuudet. — Algoritmit ja monimutkaisuudet. - Springer, Berliini, Heidelberg, 2013. - T. 7878. - (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-642-38232-1 . - doi : 10.1007/978-3-642-38233-8_27 .