Узагальнена задача про призначення

У прикладній математиці під узагальненою задачею про призначення розуміють задачу комбінаторної оптимізації, що є узагальненням задачі про призначення, в якій множина виконавців має розмір, не обов'язково рівний розміру множини робіт. При цьому виконавця можна призначити для виконання будь-яких робіт (не обов'язково однієї роботи, як у задачі про призначення). При призначенні виконавця для виконання роботи задається дві величини — ціна і дохід. Кожен виконавець має певний бюджет, так що сума всіх витрат не повинна перевищувати цього бюджету. Потрібно знайти таке призначення виконавців для виконання робіт, щоб максимізувати прибуток.

Особливі випадки

У разі, коли бюджети виконавців і всі вартості робіт дорівнюють 1, задача перетворюється на задачу про максимальне парування.

Якщо ціни і доходи для всіх призначень виконавців на роботи рівні, завдання зводиться до мультиплікативного рюкзака.

Якщо є всього один агент, задача зводиться до задачі про рюкзак.

Визначення

Є n робіт $x_1,\dots ,x_n$ і m виконавців $b_1,\dots ,b_m$. Кожен виконавець $b_i$ має бюджет $w_i$. Для кожної пари виконавець $b_i$ і робота $x_j$ задано дохід $p_{i,j}$ і вагу $w_{i,j}$. Розв'язком є підмножина робіт U і розподіл робіт з U за виконавцями. Розв'язок допустимий, якщо сума витрат на призначені роботи виконавця $b_i$ не перевершує бюджету $w_i$. Доходом від розв'язку є сума всіх доходів усіх розподілів робота-виконавець.

Математично узагальнену задачу про призначення можна сформулювати так:

максимізувати $\sum _{i=1}^m\sum _{j=1}^n{p}_{ij}{x}_{ij}.$

при $\sum _{j=1}^n{w}_{ij}{x}_{ij}\le w_{i}i=1,\dots ,m$;

$\sum _{i=1}^m{x}_{ij}\le 1j=1,\dots ,n$;

$x_{ij}\in \{0,1\}i=1,\dots ,m,j=1,\dots ,n$;

Узагальнена задача про призначення є NP-складною і навіть APX-складною.

Фляйшер, Гоманс, Мірокні і Свириденко запропонували комбінаторний алгоритм локального пошуку з апроксимацією $(2+\epsilon )$ та алгоритм на основі лінійного програмування з апроксимацією $(\frac{e}{e-1}+\epsilon )$.

Апроксимація $(\frac{e}{e-1}+ϵ)$ є кращою відомою апроксимацією узагальненої задачі про призначення.

Жадібний апроксимаційний алгоритм

Використовуючи алгоритм $\alpha$-апроксимації задачі про призначення, можна створити ($\alpha +1$)-апроксимацію для узагальненої задачі про призначення на зразок жадібного алгоритму, використовуючи концепцію залишку доходу. Алгоритм ітераційно створює попередню послідовність, в якій на ітерації $j$ передбачається закріпити роботи за виконавцем $b_j$. Вибір для виконавця $b_j$ може змінитися в подальшому при закріпленні робіт за іншими виконавцями. Залишок доходу роботи $x_i$ для виконавця $b_j$ дорівнює $p_{ij}$, якщо $x_i$ не віддано іншому виконавцю, і $p_{ij}$ — $p_{ik}$, якщо роботу віддано виконавцю $b_k$.

Формально: Використаємо вектор $T$ для попереднього вибору і в цьому векторі

$T[i]=j$ означає, що на роботу $x_i$ передбачається призначити виконавця $b_j$,

$T[i]=-1$ означає, що на роботу $x_i$ нікого не призначено.

Залишок доходу на ітерації $j$ позначається через $P_j$, де

$P_j[i]=p_{ij}$, якщо роботу $x_i$ не обрано (тобто $T[i]=-1$)

$P_j[i]=p_{ij}-p_{ik}$, якщо роботу $x_i$ передбачається віддати виконавцю $b_k$ (тобто $T[i]=k$).

Отже, алгоритм виглядає так:

Присвоюються початкові значення $T[i]=-1$ для всіх $i=1\dots n$

Для всіх $j=1...m$ виконати:

Використовується алгоритм апроксимації для отримання розподілу робіт для виконавця $b_j$, використовуючи функцію залишку доходу $P_j$. Позначаються вибрані роботи $S_j$.

Підправляється $T$, використовуючи $S_j$, тобто $T[i]=j$ для всіх $i\in S_j$.

кінець циклу

Див. також

• Задача про призначення

Посилання

• Reuven Cohen, Liran Katzir, Danny and Raz, «An Efficient Approximation for the Generalized Assignment Problem», Information Processing Letters, Vol. 100, Issue 4, pp.  162-166, November 2006.
• Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko, «Tight Approximation Algorithms for Maximum General Assignment Problems», SODA 2006, pp.  611-620.
• Hans Kellerer, Ulrich Pferschy, David Pisinger, Knapsack Problems , 2005. Springer Verlag ISBN 3-540-40286-1