Rabawa na daidaito

Rarraba abubuwa na dai-daito, wanda kuma ake kira rabawa na abubuwa mafi-min matsala ce ta rabawa na abu mai kyau, inda ma'auni na adalci ke bin dokar dai-daito. Manufar ita ce kara girman darajar wakili. Wato, daga cikin duk yiwuwar rabon, burin shine neman rabon da mafi ƙanƙanta darajar wakili ya fi girma. Idan akwai rabon biyu ko fiye tare da wannan ƙaramin darajar, to burin shine zaɓar, daga cikin waɗannan rabon, wanda ƙimar ta biyu mafi ƙanƙanta ta fi girma, da sauransu (ta hanyar tsari na leximin). Sabili da haka, wani lokaci ana kiran rabon abu na daidaito a matsayin rabon abu mai mahimmanci.

Halin na musamman wanda daraj kowane abu j ga kowane wakili shine ko dai 0 ko wasu v_j na yau da kullun ana kiransa Matsalar Santa Claus: santa claus yana da kyaututtuka masu kyau, kuma yana so ya raba su tsakanin yara don yaron da ba shi da farin ciki.

Wasu matsalolin da suka danganci su sune:

• Rarraba lambar Multiway tare da manufar max-min ya dace da wani lamari na musamman wanda duk wakilai suna da ƙimar iri ɗaya. Har ma da wani lamari na musamman shine Matsalar rabuwa, wanda ya dace da yanayin wakilai biyu. Ko da wannan lamari na musamman yana da NP-mai wuya gabaɗaya.
• Shirye-shiryen na'urori marasa alaƙa matsala ce ta biyu, inda burin shine ragewa matsakaicin darajar.
• Rarraba kayan rabawa na Maximin matsala ce daban, inda burin ba shine samun mafita mafi kyau ba, amma don samun duk wani mafita wanda kowane wakili ke karɓar darajar sama da wani ƙofar.

Daidaitawa

Akwai bambance-bambance guda biyu na mulkin daidaito:

• cikakkiyar daidaito (ko cikakkiyar leximin), inda haɓaka ke amfani da ƙimar ƙididdigar wakilai;
• daidaito na dangi (ko leximin dangi) inda haɓaka ke amfani da dabi'un su na al'ada - ƙimar ƙididdiga da aka raba ta ƙimar duk abubuwa.

Dokokin biyu dai-dai ne lokacin da kimantawar wakilai ta riga ta daidaita, wato, duk wakilai suna ba da ƙimar iri ɗaya ga saitin dukkan abubuwa. Koyaya, suna iya bambanta da ƙididdigar da ba ta dace ba. Misali, idan akwai abubuwa huɗu, Alice tana darajar su a 1,1,1 kuma George tana darajarsu a 3,3,3, to, dokar cikakkiyar doka za ta ba Alice abubuwa uku da abu ɗaya ga George, tunda bayanin martaba a wannan yanayin shine (3,3), wanda shine mafi kyau. Sabanin haka, dokar dangi-leximin za ta ba da abubuwa biyu ga kowane wakili, tunda bayanin kayan aiki na al'ada a wannan yanayin, lokacin da jimlar darajar wakilai biyu ta daidaita zuwa 1, shine (0.5,0.5), wanda shine mafi kyau.

Algorithms daidai

Kodayake matsalar gabaɗaya tana da NP-mai wuya, ana iya warware ƙananan lokuta daidai ta hanyar dabarun shirye-shiryen ƙuntatawa.

• Bouveret da Lemaître sun gabatar da algorithms daban-daban guda biyar don gano mafita mafi kyau ga matsalolin ƙuntatawa- gamsuwa. Suna gabatar da rabon abubuwa na max-min a matsayin lamari na musamman.
• Dall'Aglio da Mosca sun ba da ainihin, reshe-da-bound algorithm ga wakilai biyu, bisa ga daidaitawa da tsarin mai nasara.

Algorithms na bazuwar

Demko da Hill sun gabatar da algorithm na bazuwar wanda ya sami rabon abu na daidaito a cikin tsammanin.

Algorithms na kusanci

Da ke ƙasa, m">n shine yawan wakilai kuma m shine yawan abubuwa.

Don yanayin musamman na matsalar Santa Claus:

• Bansal da Sviridenko sun ba da O (log) Layin da ya faru n / Layin da ya faru Layin da ya faru Layin da ya faru n ) {\displaystyle O (\log {\log {n}}/\log {\ log {n}}}) } -kimanin algorithm, bisa ga zagaye Shirin layi.
• Feige ya tabbatar da cewa wani polynomial-lokaci-lokaci m-factor algorithm wanzu, amma hujja ta yi amfani da Lovász gida lemma kuma ba ta da ginawa.
• Asadpour, Feige da Saberi sun tabbatar da cewa gibin haɗin kai na shirin layi na tsari shine 1/4. Wannan yana nuna algorithm na kusanci na 1/4, ta amfani da daidaitawar hypergraph. Koyaya, ba za su iya tabbatar da cewa algorithm ya haɗu a cikin matakan polynomial ba.
• Annamalai, Kalaitzis da Svensson sun ba da algorithm na kusanci na 13 na polynomial-lokaci.
• Davies, Rothvoss da Zhang sun inganta kusanci zuwa 4 ta hanyar gabatar da ƙuntatawa na Matroid zuwa Shirin layi na asali.

Ga al'amarin gaba ɗaya, ga wakilai tare da ƙididdigar ƙididdiga:

• Chakrabarty, Chuzoy da Khanna sun ba da O ( m ε ) {\displaystyle O (m^{\varepsilon }) } -kimanin algorithm tare da lokacin gudu na O ( m 1 / ε ) {\displaystyle O (m^{1/\varepsilon }) } , ga kowa ε ∈ Ω (Abin da ya fi dacewa da shi) Ya kamata a yi amfani da shi Ya kasance m ) {\displaystyle \varepsilon \in \Omega \left ({\frac {\log \log m}{\log m}}\right) } . Ga yanayin na musamman wanda kowane abu yana da amfani mara amfani ga a kalla wakilai biyu, sun ba da algorithm na kusanci na 2-factor, kuma sun tabbatar da cewa yana da wahala a kusanci ga kowane abu mafi kyau.
• Golovin ya ba da algorithm wanda, ga kowane adadi k {\displaystyle k} , a ( 1 − 1 / k) {\displaystyle (1-1/k) } kashi na wakilai suna karɓar amfani aƙalla Ya P T / k {\displaystyle OPT/k} . Ana samun wannan sakamakon ne daga zagaye tsarin shirye-shiryen layi mai dacewa na matsalar, kuma shine mafi kyawun sakamako ga wannan shirin layi. Ya kuma ba da O ( n ) {\displaystyle O ({\sqrt {n}}) } -kimanin algorithm don shari'ar ta musamman tare da nau'ikan kayayyaki guda biyu.
• Lokacin da yawan wakilai ya kasance ba daidai ba akwai FPTAS ta amfani da fasahar Woeginger.

Ga wakilai tare da Ayyukan amfani na submodular:

• Golovin ya ba da (m − n + 1) {\displaystyle (m-n+1) } -kimanin algorithm, da wasu sakamakon rashin kusanci don ayyukan amfani na gaba ɗaya.
• Goemans, Harvey, Iwata da Mirrkoni sun ba da O ( m ⋅ n 1 / 4 ⋅ log ⋅ log 3 / 2 Sanya m) {\displaystyle O ({\sqrt {m}}\cdot n^{1/4}\cdot \log n\cdot\log ^{3/2}m) } -kimanin algorithm
• Nguyen, Roos da Rothe sun gabatar da wasu sakamako masu karfi.

Rarraba daidaito na yau da kullun

Ka'idar daidaito tana buƙatar kowane wakili ya ba da ƙimar lambobi ga kowane abu. Sau da yawa, jami'an suna da kayan aiki na yau da kullun kawai. Akwai nau'o'i biyu na mulkin daidaito zuwa saitunan tsari.

1. Ka yi la'aka<i i="mwvA">ri> da wakilai sun da matsayi na yau da kullun akan saitin bundles. Idan aka ba da kowane rabon rarraba, ga kowane wakili i, ayyana r (i) a matsayin matsayi na wakili i's bundle, don haka r (i" =1 idan na sami mafi kyawun bundle, r (i") =2 idan na sami na biyu mafi kyawun bundl, da dai sauransu. Wannan r shine vector na girman n (yawan wakilai). Rarraba daidaito na yau da kullun shine wanda ke rage mafi girma a cikin r. Hanyar Rage buƙata tana samun rabon daidaito na kowane adadin wakilai tare da kowane tsari na bundles.

2. m">k ym">i="mwyA">i la'a'k' da jami'ai su'n' da ma'''t''' na yau da kullun akan saitin abubuwa. Idan aka ba da kowane rarraba ko raguwa, ga kowane wakili i da ƙididdigar ƙididdiga mai kyau k, ayyana t (i,k) a matsayin jimlar ɓangaren da wakili na karɓa daga manyan ɗalibai na k. Wannan t shine vector na girman a mafi yawan n * m, inda n shine yawan wakilai kuma m shine yawan abubuwa. Rarrabawar daidaito ta yau da kullun shine wanda ke kara girman t a cikin tsari na leximin. <b id="mw1w">Algorithm na cin abinci a lokaci guda</b> tare da saurin cin abinci daidai shine doka ta musamman wacce ke dawo da rabon daidaito na yau da kullun.

Rarraba daidaito a kan layi

A cikin saitin kan layi, abubuwa suna zuwa ɗaya bayan ɗaya. Dole ne a rarraba kowane abu nan da nan lokacin da ya isa.

Kawase da Sumita suna nazarin bambance-bambance guda biyu: don bambancin abokin hamayya, suna ba da algorithm tare da rabo na gasa 1/n, kuma suna nuna cewa shine mafi kyawun yiwuwar. Ga bambancin i.i.d., suna ba da kusan-mafi kyawun algorithm.

Kwatanta da sauran ka'idojin adalci

Daidaitawa

Duk lokacin da aka raba daidaito, rarraba dangi-leximin daidai ne. Wannan shi ne saboda, a cikin rabon daidaito, mafi ƙanƙanta darajar dangi na wakili shine aƙalla 1/n, don haka dole ne ya riƙe lokacin da muka kara ƙarancin darajar doki. Koyaya, cikakkiyar rabon ƙayyadaddun ƙayyadadden ƙayyadyadaddun ba zai iya zama daidai ba, kamar yadda aka nuna a cikin misalin da ke sama.

Kishiyar kishi

1. Lokacin da duk wakilai suna da kimantawa iri ɗaya tare da kayan aiki na gefe, duk wani rabon dangi-leximin shine PO da EFX.

• Inganta leximin++ da ake kira leximin ++ ya tabbatar da EFX (amma ba PO ba) tare da kimantawa iri ɗaya.

2. Ga wakilai biyu tare da ƙididdigar ƙididdiga, duk wani rabon dangi shine EF1. : Thm.5.5 Koyaya:

• Cikakken rabon-leximin bazai zama EF1 ba har ma ga wakilai biyu tare da ƙididdigar ƙididdiga. Misali, a ce akwai kayayyaki huɗu da wakilai biyu waɗanda ke darajar su a {0,1,1,1} da {3,3,3}. Rarrabawar cikakkiyar-leximin ta musamman tana ba da {1,1,1} ga wakili na farko da {3} ga wakilai na biyu, amma sai wakili na biyu ya yi kishi. : 32 
• Rarrabawar dangi-leximin bazai zama EF1 ga wakilai uku ko fiye ba. Misali, a ce akwai kayayyaki huɗu da wakilai uku waɗanda ke darajar su a {30,0,0,0} {20,5,0} da {0,12,6}. Lura cewa kimantawa an daidaita su (cikakken darajar shine 30). A cikin rabon leximin, dole ne a rarraba abu na farko ga wakili 1. Sa'an nan kuma, dole ne a rarraba kayan na biyu da na uku ga wakili 2, kuma mai kyau ya kasance ga wakili 3. Amma wakili 3 yana kishin wakili 2 koda bayan cire wani abu. : 22 

3. Lokacin da duk wakilai suna da kimantawa waɗanda ke da matsayi na matroid (watau, submodular tare da binary marginals), saitin rabon cikakke-leximin daidai yake da saitin rabawa na mafi-samfur; duk irin waɗannan rabon sune max-sum da EF1.

4. A cikin mahallin rarraba ayyukan gida (abubuwa tare da kayan aiki marasa kyau), tare da wakilai 3 ko 4 tare da ƙididdigar ƙididdiga, duk wani rabon leximin-mafi kyau shine PROP1 da PO; tare da wakili n tare da ƙimar iri ɗaya, duk wani rarraba leximin-mai kyau shine EFX.

Matsakaicin rabon

Lokacin da duk wakilai ke da kimantawa iri ɗaya, rabon daidaito, ta hanyar ma'anar, yana ba kowane wakili aƙalla rabonsa mafi girma.

Koyaya, lokacin da wakilai ke da ƙididdiga daban-daban, matsalolin sun bambanta. Rarrabawar mafi girma matsala ce ta gamsuwa: burin shine tabbatar da cewa kowane wakili yana karɓar darajar sama da ƙimar ƙimar ƙididdiga iri ɗaya. Sabanin haka, rabon daidaito matsala ce ta ingantawa: burin shine ba kowane wakili babban darajar yadda ya yiwu. A wasu lokuta, sakamakon rabon zai iya zama daban-daban. Misali, a ce akwai kayayyaki huɗu da wakilai uku waɗanda ke darajar su a {3,0,0,0}, {3-2ε,ε,0} da {1-2ε,1,2ε} (inda ε ƙaramin tabbatacce ne). Lura cewa kimantawa sun daidaita (cikakken darajar shine 3), don haka cikakkiyar-leximin da dangi-leximin daidai ne.

• Rabon leximin yana samar da bayanin martaba (3, 2ε, 2ε): abu na farko dole ne ya tafi wakili 1 - in ba haka ba mafi ƙanƙanta mai amfani shine 0. Sa'an nan, abubuwa na biyu da na uku dole ne su je ga wakili 2 - in ba haka ba mafi ƙanƙanta mai amfani na gaba shine ε ko ƙasa da haka; don haka wakili 3 yana samun abu na ƙarshe kawai.
• Matsakaicin rabon wakilai shine 0, ε, 1. Sabili da haka, rabon rabon mafi girma dole ne ya ba wakili 3 daya daga cikin abubuwa uku na farko; wasu bayanan amfani a wannan yanayin sune (0, 2ε, 1) ko (3, ε, 1+2ε).

Ana iya fadada misalin zuwa 1-daga-k MMS don k k>3. Ak k k + 1 da wak uk waɗanda ke darajar su a {k, 0, ..., 0}, {k- (k-1) ε, 'ε, ... , ε, 0} da {1-kε, 1, ..., kε}. Sakamakon amfani na leximin dole ne ya zama (k, kε, kε) yayin da 1-daga-k MMS na wakili 3 shine 1.

Aikace-aikacen duniya

An yi amfani da dokar leximin don rarraba ɗakunan da ba a yi amfani da su ba a makarantun jama'a zuwa makarantun sasantawa.