Проблем максималне покривености

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Проблем максималне покривености је добро познат проблем у пољу информатике, теорије комплексности и операционом истраживању. Код овог проблема као улаз нам је дато неколико скупова и број к. Скупови могу имати неке заједничке елементе. Треба одабрати највише к тих скупова, тако да је максималан број елемената покривен, тј унија одабраних скупова има максималну величину.

Формална, (безтежинска верзија)проблема максималне покривеност је:

Улаз: Број к и колекција скупова С = С₁, С₂, ..., С_м.
Излаз: Пронађен је подскуп $S^{'}\subseteq S$ од скупова, такав да $\left|S^{'}\right|\leq k$ и да је број покривених елемената $\left|\bigcup _{S_{i}\in S^{'}}{S_{i}}\right|$ максималан.

Проблем максималне покривености је НП-тежак, и не може бити апроксимиран са $1-{\frac {1}{e}}+o(1)\approx 0.632$ под стандардним претпоставкама. Овај резултат у суштини одговара сложености добијеној помоћу генеричког похлепног алгоритма.^[1]

Формулација ИЛП(енгл. integer linear problem)

Проблем максималне покривености може бити формулисан као следећи линеарни програм са целим бројевима:

$\sum _{e_{j}\in E}y_{j}$ . (максимална сума покривених елемената).

$\sum {x_{i}}\leq k$ ; (не више од к скупова је одабрано).

$\sum _{\,e_{j}\in S_{i}}x_{i}\geq y_{j}$ ; (ако је $y_{j}>0$ онда је бар један скуп $e_{j}\in S_{i}$ је означен).

$0\leq y_{j}\leq 1$ ; (ако је $y_{j}=1$ онда је $e_{j}$ покривен)

$x_{i}\in \{0,1\}$ (ако је $x_{i}=1$ онда $S_{i}$ је одабран за прекривеност).

Похлепни алгоритам

Похлепни алгоритам за максималну покривеност бира скупове водећи се једним правилом: у сваком кораку, бирамо скуп са највише непокривених елемената. Може се показати да овај алгоритам достиже сложеност од $1-{\frac {1}{e}}$ ^[2]. Резултати показују да је похлепни алгоритам, најбољи могући алгоритам, полиномијалне временске сложености за проблем максималне покривености^[3].

Верзија са тежинама

У верзији са тежинама сваки елемент $e_{j}$ има тежину $w(e_{j})$ . Задатак је наћи максималну покривеност која има и максималну тежину. Специјалан случај је случај кад су све тежине 1.

$\sum _{e\in E}w(e_{j})\cdot y_{j}$ . (максимална сума са тежинама покривених елемената).

$\sum {x_{i}}\leq k$ ; (не више од к скупова је одабрано).

$\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}$ ; (ако је $y_{j}\geq 0$ онда је бар један скуп $e_{j}\in S_{i}$ одабран).

$0\leq y_{j}\leq 1$ ; (ако је $y_{j}=1$ онда је $e_{j}$ покривен)

$x_{i}\in \{0,1\}$ (ако је $x_{i}=1$ онда $S_{i}$ одабран за прекривеност).

Похлепни алгоритам у верзији са тежинама при проблему максималне покривености у сваком кораку бира скуп кој садржи максималну тежину непокривених елемената. Овај алгоритам постиже сложеност $1-{\frac {1}{e}}$ .^[1].

Максимална покривеност са ограничењем

У максималној покривености са ограничењем, сваки елемент $e_{j}$ има тежину $w(e_{j})$ , али и сваки скуп $S_{i}$ има цену $c(S_{i})$ . Уместо $k$ које означава ограничење броја скупова у покривености $a$ буџет $B$ је дат. Овај буџет $B$ ограничава тежину прекривености која може бити одабрана.

$\sum _{e\in E}w(e_{j})\cdot y_{j}$ . (максимална сума са тежинама покривених елемената).

$\sum {c(S_{i})\cdot x_{i}}\leq B$ ; (цена одабраних скупова која не може прећи $B$ ).

$\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}$ ; (ако је $y_{j}\geq 0$ онда је бар један скуп $e_{j}\in S_{i}$ обабран).

$0\leq y_{j}\leq 1$ ; (ако је $y_{j}=1$ онда је $e_{j}$ покривен)

$x_{i}\in \{0,1\}$ (ако је $x_{i}=1$ онда је $S_{i}$ одабран за покривеност).

Похлепан алгоритам нам неће више достављати решење са гарантованом добром преформансом. У најгорем могућем случају извођење овог алгоритма може бити далеко од оптималног решења. Алгоритам апроксимације проширујемо на следећи начин: Прво, после проналаска решења користећи похлепни алгоритам, враћа се најбоље од решења похлепног алгоритма и скуп највеће тежине. Ово можемо назвати модификовани похлепни алгоритам. Друго, почев од свих могућих фамилија скупова са величинама од 1 до бар 3, повећати решења уз помоћ модификованог похлепног алгоритма. Треће, врати најбољи од свих повећаних решења. Овај алгоритам достиже сложеност $1-1/e$ . Ово је најбољи могућа сложеност, осим ако $NP\subseteq DTIME$ ( $n^{O(\log \log n)}$ ).^[4]

Генерализована максимална покривеност

У уопштеној верзији проблема максималне покривености сваки скуп $S_{i}$ има цену $c(S_{i})$ , а елемент $e_{j}$ има друкчију тежину и цену која зависи од скупа кој је покрива. Ако је $e_{j}$ покривен скупом $S_{i}$ тежина $e_{j}$ је $w_{i}(e_{j})$ и њена цена је $c_{i}(e_{j})$ . Буџет $B$ је дат за цену целокупног решења.

$\sum _{e\in E,S_{i}}w_{i}(e_{j})\cdot y_{ij}$ . (максимална сума са тежинама покривених елемената у скуповима у којима су покривени).

$\sum {c_{i}(e_{j})\cdot y_{ij}}+\sum {c(S_{i})\cdot x_{i}}\leq B$ ; (цена одабраних скупова не може да пређе $B$ ).

$\sum _{i}y_{ij}\leq 1$ ; (елемент $e_{j}=1$ можи бити покривен само једним скупом).

$\sum _{S_{i}}x_{i}\geq y_{ij}$ ; (ако је $y_{j}\geq 0$ онда је бар један скуп $e_{j}\in S_{i}$ одабран).

$y_{ij}\in \{0,1\}$ ; (ако је $y_{ij}=1$ онда је $e_{j}$ покривен скупом $S_{i}$ )

$x_{i}\in \{0,1\}$ (ако је $x_{i}=1$ онда је $S_{i}$ одабран за прекривеност).

Алгоритам

Алгоритам користи концепт остатка цене/тежине. Остатак цене/тежине је мерен са привременим решењем и то је разлика цене/тежине од цене/тежине добијене у привременом решењу.

Алгоритам има неколико корака. Прво, пронаћи решење коришћењем похлепног алгоритма. У свакој итерацији похлепног алгоритма привремено решење је додато скупу који садржи максимум остатак тежина елемената, подељеног са остатком цена ових елемената, заједно са остатком цене скупа. Друго, поредити решења добијена у првом кораку тако да се добије најбоље решење од њих које користи мали број скупова. Треће, врати најбољи од проверених решења. Овај алгоритам достиже сложеност од $1-1/e-o(1)$ .^[5]

Повезани проблеми

Проблем покривености скупа, покривање свих елемената са што мање скупова.

Референце

^ ^а ^б Г. L. Немхаусер, L. А. Wолсеy анд M. L. Фисхер. Ан аналyсис оф аппроxиматионс фор маxимизинг субмодулар сет фунцтионс I, Матхематицал Программинг 14 (1978), 265–294
^ Хоцхбаум, D. С. (1997), "Аппроxиматинг цоверинг анд пацкинг проблемс: Сет цовер, вертеx цовер, индепендент сет, анд релатед проблемс", ин Аппроxиматион алгоритхмс фор НП-хард проблемс, ПWС Публисхинг Цомпанy, Бостон, 94-143.
^ Феиге, У., "А тхресхолд оф лн н фор аппроxиматинг сет цовер", Ј. АЦМ 45, 634-652.
^ Кхуллер, С., Мосс, А., анд Наор, Ј. 1999. Тхе будгетед маxимум цовераге проблем. Инф. Процесс. Летт. 70, 1 (Апр. 1999), 39-45.
^ Цохен, Р. анд Катзир, L. 2008. Тхе Генерализед Маxимум Цовераге Проблем. Инф. Процесс. Летт. 108, 1 (Сеп. 2008), 15-22.

Вазирани, Вијаy V. (2001). Аппроxиматион Алгоритхмс. Спрингер-Верлаг. ИСБН 3-540-65367-8.
Уриел Феиге, А Тхресхолд оф лн $n$ фор Аппроxиматинг Сет Цовер, Јоурнал оф тхе АЦМ (ЈАЦМ). . 45 (4): 634 — 652,. Недостаје или је празан параметар |титле= (помоћ)Јулy 1998.

[jedan-1] а ^б Г. L. Немхаусер, L. А. Wолсеy анд M. L. Фисхер. Ан аналyсис оф аппроxиматионс фор маxимизинг субмодулар сет фунцтионс I, Матхематицал Программинг 14 (1978), 265–294

[2] Хоцхбаум, D. С. (1997), "Аппроxиматинг цоверинг анд пацкинг проблемс: Сет цовер, вертеx цовер, индепендент сет, анд релатед проблемс", ин Аппроxиматион алгоритхмс фор НП-хард проблемс, ПWС Публисхинг Цомпанy, Бостон, 94-143.

[3] Феиге, У., "А тхресхолд оф лн н фор аппроxиматинг сет цовер", Ј. АЦМ 45, 634-652.

[4] Кхуллер, С., Мосс, А., анд Наор, Ј. 1999. Тхе будгетед маxимум цовераге проблем. Инф. Процесс. Летт. 70, 1 (Апр. 1999), 39-45.

[5] Цохен, Р. анд Катзир, L. 2008. Тхе Генерализед Маxимум Цовераге Проблем. Инф. Процесс. Летт. 108, 1 (Сеп. 2008), 15-22.

[1]

[2]

[3]

[4]

[5]