K-urish to'plamining K-yaqinlashishi - K-approximation of k-hitting set

Yilda Kompyuter fanlari, k-urish to'plamining k-yaqinlashishi bu taxminiy algoritm vazn uchun urish to'plami. Kirish a to'plam S ning pastki to'plamlar ba'zi olamning T va a xaritalash V dan T ning elementlari og'irliklari deb nomlangan manfiy bo'lmagan sonlarga T. Yilda k-urish to'plami to'plamlarning hajmi S dan kattaroq bo'lishi mumkin emas k. Anavi, ${displaystyle forall iin S: | i | leq k}$. Muammo endi biron bir kichik to'plamni tanlashda T"ning T shunday qilib har bir o'rnatilgan S ning ba'zi bir elementlari mavjud T'va shunga o'xshash barcha elementlarning umumiy og'irligi T'imkon qadar kichikroq.

Algoritm

Har bir to'plam uchun ${displaystyle j}$ yilda S saqlanadi a narx, ${displaystyle p_ {j}}$, bu dastlab 0. Element uchun a yilda T, ruxsat bering S(a) dan to'plamlar to'plami bo'lishi mumkin S o'z ichiga olgan a. Algoritm davomida quyidagi invariant saqlanadi

${displaystyle for all ain T: sum _ {jin S (a)} p_ {j} leq W (a).,}$

Biz aytamizki, element, a, dan T bu qattiq agar ${displaystyle Sigma _ {jin S (a)} p_ {j} = W (a)}$. Algoritmning asosiy qismi tsikldan iborat: agar u erda o'rnatilgan bo'lsa S tarkibida hech qanday element yo'q T qat'iy bo'lgan ushbu to'plamning narxi yuqoridagi invariantni buzmasdan iloji boricha oshiriladi. Ushbu tsikl chiqqandan so'ng, barcha to'plamlarda bir nechta qattiq element mavjud. Barcha qattiq elementlarni tanlab oling.

To'g'ri

Algoritm har doim tugatiladi, chunki tsiklning har bir takrorlanishida ba'zi birlari o'rnatiladi S yana bitta element hosil qilish uchun yetarli darajada oshiriladi T qattiq. Agar u biron bir narxni oshira olmasa, u chiqadi. U polinom vaqtida ishlaydi, chunki tsikl barcha to'plamlarning birlashmasidagi elementlar sonidan ko'proq takrorlanmaydi. S. U urilgan to'plamni qaytaradi, chunki tsikl chiqqandan keyin hamma o'rnatiladi S dan qattiq elementni o'z ichiga oladi Tva ushbu qattiq elementlarning to'plami qaytariladi.

Har qanday zarba to'plami uchun unutmang T * va har qanday narxlar ${displaystyle p_ {1}, ldots, p_ {| S |}}$ agar algoritmdan o'zgarmas bo'lsa, urish to'plamining umumiy og'irligi barcha a'zolar bo'yicha yig'indining yuqori chegarasidir. T * ushbu elementni o'z ichiga olgan to'plamlar narxi yig'indisi, ya'ni: ${displaystyle Sigma _ {ain T ^ {*}} Sigma _ {jin S (a)} p_ {j} leq Sigma _ {ain T ^ {*}} W (a)}$. Bu o'zgarmas mulkdan kelib chiqadi. Bundan tashqari, har bir to'plamning narxi kamida bir marta chap tomonda bo'lishi kerakligi sababli, biz olamiz ${displaystyle Sigma _ {jin S} p_ {j} leq Sigma _ {ain T ^ {*}} W (a)}$. Ayniqsa, bu xususiyat eng yaxshi zarba to'plami uchun to'g'ri keladi.

Keyinchalik, urish to'plami uchun H yuqoridagi algoritmdan qaytdi, bizda ${displaystyle Sigma _ {ain H} Sigma _ {jin S (a)} p_ {j} = Sigma _ {ain H} W (a)}$. Har qanday narxdan beri ${displaystyle p_ {j}}$ eng ko'p paydo bo'lishi mumkin k chap tomonda marta (ning pastki to'plamlaridan beri S o'z ichiga olishi mumkin k element T) olamiz ${displaystyle Sigma _ {ain H} W (a) leq kcdot Sigma _ {jin S} p_ {j}}$ Oldingi paragraf bilan birgalikda biz olamiz ${displaystyle Sigma _ {ain H} W (a) leq kcdot Sigma _ {ain T ^ {*}} W (a)}$, qayerda T * eng yaxshi urish to'plami. Bu k ning taxminiy algoritmi ekanligining aniq kafolati.

Lineer dasturlash bilan bog'liqlik

Ushbu algoritm. Ning misoli ibtidoiy-dual usul deb nomlangan narxlash usuli. Sezgi bu ikkilamchi a chiziqli dasturlash algoritm. Izoh uchun qarang http://algo.inria.fr/seminars/sem00-01/vazirani.html.

Adabiyotlar

• Klaynberg, J.; Tardos, E. (2006). Algoritm dizayni. ISBN  0-321-29535-8..
• Yetti; R. Bar-Yehuda (1981). "Vertikal qopqoqning og'irligi muammosini chiziqli vaqtga yaqinlashtirish algoritmi". J. Algoritmlar. 2 (2): 198–203. doi:10.1016/0196-6774(81)90020-1.
• Goemans, M. X.; Uilyamson, D. P. (1997). "Yaqinlashtirish algoritmlari uchun primal-dual usul va uni tarmoq dizaynidagi muammolarga qo'llash". Yilda Xoxbaum, Dorit S. (tahrir). NP-qattiq muammolar uchun taxminiy algoritmlar. PWS nashriyot kompaniyasi. ISBN  0-534-94968-1..