Zobecněný problém zadání

V aplikované matematice je zobecněný problém přiřazení chápán jako kombinatorický optimalizační problém , což je zobecnění problému přiřazení , ve kterém má množina umělců velikost, která se nemusí nutně rovnat velikosti množiny úloh. V tomto případě může být interpret přidělen k provedení jakékoli práce (ne nutně jedné práce, jako v problému zadání). Při přidělení exekutora k výkonu práce jsou nastaveny dvě hodnoty - náklady a příjmy. Každý účinkující má určitý rozpočet, takže součet všech nákladů by tento rozpočet neměl přesáhnout. Je třeba najít takové přidělení výkonných umělců k výkonu práce, aby se maximalizoval příjem.

Zvláštní příležitosti

V případě, že rozpočty interpretů a všechny náklady na práci jsou rovny 1, problém se změní v problém maximálního párování .

Pokud jsou ceny a příjmy pro všechny pracovní úkoly stejné, problém se zmenší na multiplikativní batoh .

Pokud existuje pouze jeden agent, problém se redukuje na problém s batohem .

Definice

Existuje n pracovních míst a m účinkujících . Každý účinkující má svůj rozpočet . Pro každou dvojici účinkujících a práce je uveden příjem a váha . Řešením je podmnožina úloh U a rozdělení úloh z U mezi účinkující. Rozhodnutí je přijatelné, pokud výše nákladů na svěřenou práci výkonného umělce nepřekročí rozpočet . Příjem z rozhodnutí je součtem všech příjmů všech rozdělení práce-exekutora. ${\displaystyle x_{1},\tečky ,x_{n))$ ${\displaystyle b_{1},\tečky ,b_{m))$ $bi}$ $w_{i}$ $bi}$ $x_{j}$ ${\displaystyle p_{i,j))$ $w_{i,j}$ $bi}$ $w_{i}$

Matematicky lze problém zobecněného zadání formulovat následovně:

maximalizovat

\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.

podléhat ;

\sum _{j=1}^{n}w_{ij}x_{ij}\leq w_{i}\qquad i=1,\ldots ,m

\sum _{i=1}^{m}x_{ij}\leq 1\qquad j=1,\ldots ,n

;

x_{ij}\in \{0,1\}\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n

;

Zobecněný problém přiřazení je NP-tvrdý a dokonce APX-tvrdý .

Fleischer, Gomans, Mirokni a Sviridenko navrhli kombinatorický lokální vyhledávací algoritmus s aproximací a algoritmus založený na lineárním programování s aproximací [1] . $(2+\varepsilon )$ $({\frac {e}{e-1}}+\varepsilon )$

Aproximace je nejznámější aproximací problému zobecněného zadání. $({\frac {e}{e-1))+\epsilon )$

Greedy Aproximation Algorithm

Pomocí algoritmu aproximace problému přiřazení lze vytvořit ( ) -aproximaci pro zobecněný problém přiřazení na způsob chamtivého algoritmu využívajícího koncept reziduálního příjmu. Algoritmus iterativně vytváří předběžnou sekvenci, ve které má při iteraci přidělit práci interpretovi . Volbu pro interpreta lze později změnit při zadávání práce jiným interpretům. Zbývající příjem z díla pro výkonného umělce je , není-li dílo předáno jinému výkonnému umělci, a - je-li dílo předáno výkonnému umělci . $\alpha$ $\alpha +1$ $j$ $b_{j}$ $b_{j}$ $x_{i}$ $b_{j}$ $p_{{ij}}$ $x_{i}$ ${\displaystyle p_{ij))$ ${\displaystyle p_{ik))$ $b_{k}$

Formálně:

Použijte vektor pro předvýběr a v tomto vektoru $T$

T[i]=j

znamená, že má k dílu přidělit vykonavatele ,

x_{i}

b_{j}

T[i]=-1

znamená, že k úkolu nebyl nikdo přiřazen.

x_{i}

Zbývající příjem na iteraci je označen , kde $j$ $P_{j}$

{\displaystyle P_{j}[i]=p_{ij))

pokud není vybrána žádná zakázka (tj .

x_{i}

T[i]=-1

{\displaystyle P_{j}[i]=p_{ij}-p_{ik))

, pokud má být dílo předáno výkonnému umělci (tedy ).

x_{i}

b_{k}

T[i]=k

Algoritmus tedy vypadá takto:

Přiřazené počáteční hodnoty pro všechny

T[i]=-1

i=1\ldots n

Pro všechny udělejte:

j=1...m

K získání rozdělení práce pro dodavatele pomocí funkce reziduálního příjmu se používá aproximační algoritmus . Vybraná díla jsou označena .

b_{j}

P_{j}

S_j

Opraveno pomocí , tedy pro všechny .

T

S_j

T[i]=j

{\displaystyle i\in S_{j))

konec cyklu

Viz také

Problém s přiřazením

Poznámky

↑ L. Fleischer, MX Goemans, VS Mirrokni a M. Sviridenko. Přísné aproximační algoritmy pro maximální obecné úlohy přiřazení. V SODA'06: Proc

Odkazy

Reuven Cohen, Liran Katzir a Danny Raz, "Efektivní aproximace pro problém zobecněného přiřazení" , Information Processing Letters, Vol. 100, číslo 4, str. 162–166, listopad 2006.
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni a Maxim Sviridenko, "Tight Aproximation Algorithms for Maximum General Assignment Problems" , SODA 2006, str. 611–620.
Hans Kellerer, Ulrich Pferschy, David Pisinger, Problémy s batohem , 2005. Springer Verlag ISBN 3-540-40286-1