К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации
Показано, що для реоптимізації задачі про покриття множинами при вставленні або звільненні елемента в довільну множину не існує поліноміально наближеної схеми. Подібний результат має місце для задачі «мінімальне розфарбування графа» при вставленні довільної вершини не більше ніж з двома інцидентними...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2011 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84200 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 3. — С. 42-50. — Бібліогр.: 13 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859478232987860992 |
|---|---|
| author | Михайлюк, В.А. |
| author_facet | Михайлюк, В.А. |
| citation_txt | К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 3. — С. 42-50. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Показано, що для реоптимізації задачі про покриття множинами при вставленні або звільненні елемента в довільну множину не існує поліноміально наближеної схеми. Подібний результат має місце для задачі «мінімальне розфарбування графа» при вставленні довільної вершини не більше ніж з двома інцидентними їй ребрами і задачі «мінімальне пакування в контейнери» при звільненні довільного предмета.
It is shown that no polynomial-time approximation scheme exists for the reoptimization of the set covering problem in inserting an element into or eliminating it from any set. A similar result is obtained for the minimum graph coloring problem in inserting a vertex with at most two incidence edges and for the minimal bin packing problem in eliminating any element.
|
| first_indexed | 2025-11-24T11:53:39Z |
| format | Article |
| fulltext |
ÓÄÊ 519.854
Â.À. ÌÈÕÀÉËÞÊ
Ê ÂÎÏÐÎÑÓ Î ÑÓÙÅÑÒÂÎÂÀÍÈÈ ÏÎËÈÍÎÌÈÀËÜÍÎ
ÏÐÈÁËÈÆÅÍÍÛÕ ÑÕÅÌ ÄËß ÐÅÎÏÒÈÌÈÇÀÖÈÈ ÄÈÑÊÐÅÒÍÛÕ
ÇÀÄÀ× ÎÏÒÈÌÈÇÀÖÈÈ
Êëþ÷åâûå ñëîâà: ðåîïòèìèçàöèÿ, r-ïðèáëèæåííûé àëãîðèòì, ïîëèíîìèàëüíî
ïðèáëèæåííûå ñõåìû.
Ïîíÿòèå ðåîïòèìèçàöèè [1–7] ñîñòîèò â ñëåäóþùåì. Ïóñòü Ï — íåêîòîðàÿ
NP-òðóäíàÿ (âîçìîæíî, NP-ïîëíàÿ) ïðîáëåìà, I — íà÷àëüíûé ýêçåìïëÿð ïðîáëåìû
Ï , îïòèìàëüíîå ðåøåíèå êîòîðîãî èçâåñòíî. Ïðåäëàãàåòñÿ íîâûé ýêçåìïëÿð I � çà-
äà÷è Ï , ïîëó÷åííûé íåêîòîðûìè «íåçíà÷èòåëüíûìè» èçìåíåíèÿìè ýêçåìïëÿðà I .
Âîçíèêàåò âîðîñ: êàê ìîæíî ýôôåêòèâíî èñïîëüçîâàòü çíàíèÿ îá îïòèìàëüíîì ðå-
øåíèè I äëÿ âû÷èñëåíèÿ òî÷íîãî èëè ïðèáëèæåííîãî ðåøåíèÿ ýêçåìïëÿðà I �?
Öåëü ðåîïòèìèçàöèè ïðè èñïîëüçîâàíèè ïðèáëèæåííûõ ìåòîäîâ — ïðèìåíåíèå
çíàíèé î ðåøåíèè íà÷àëüíîãî ýêçåìïëÿðà I ïðè óñëîâèè: ëèáî äîñòèæåíèÿ ëó÷øå-
ãî êà÷åñòâà ïðèáëèæåíèÿ (àïïðîêñèìàöèîííîãî îòíîøåíèÿ) I �; ëèáî ñîçäàíèÿ áî-
ëåå ýôôåêòèâíîãî (ïî âðåìåíè) àëãîðèòìà îïðåäåëåíèÿ îïòèìàëüíîãî èëè áëèçêîãî
ê íåìó ðåøåíèÿ I �; ëèáî âûïîëíåíèÿ ïåðâîãî è âòîðîãî ïóíêòîâ.
Èññëåäîâàíèÿ ïî ðåîïòèìèçàöèè ðàçëè÷íûõ çàäà÷ äèñêðåòíîé îïòèìèçàöèè
ïðîâåäåíû â ðàáîòàõ [1–7].
ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß Î ÏÐÈÁËÈÆÅÍÍÛÕ ÀËÃÎÐÈÒÌÀÕ È
ÀÏÏÐÎÊÑÈÌÀÖÈÎÍÍÛÕ ÊËÀÑÑÀÕ ÇÀÄÀ× ÄÈÑÊÐÅÒÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Ïðèâåäåì íåêîòîðûå íåîáõîäèìûå ïîíÿòèÿ äëÿ äàëüíåéøåãî èçëîæåíèÿ, ââå-
äåííûå â [7].
Îïðåäåëåíèå 1. NP-îïòèìèçàöèîííàÿ (NPO) ïðîáëåìà Ï îïðåäåëÿåòñÿ êàê
÷åòâåðêà ( , , , )E mSol opt òàêàÿ, ÷òî:
�E — ìíîæåñòâî ýêçåìïëÿðîâ Ï, ðàñïîçíàâàåìîå çà ïîëèíîìèàëüíîå âðåìÿ;
� äëÿ äàííîãî I E� Sol( )I — ìíîæåñòâî äîïóñòèìûõ ðåøåíèé I ; äëÿ êàæäî-
ãî S I S�Sol( ) | | (ðàçìåð S) ïîëèíîìèàëåí ïî | |I (ðàçìåð I ); äëÿ ëþáîãî äàííîãî I
è ëþáîãî S (ïîëèíîìèàëüíîãî ïî | |I ) çà ïîëèíîìèàëüíîå âðåìÿ ìîæíî îïðåäå-
ëèòü S I�Sol( );
� äëÿ äàííûõ I E� è S I�Sol( ) m I S( , ) — çíà÷åíèå (÷èñëîâîå) S; m — ïîëè-
íîìèàëüíî âû÷èñëèìàÿ âåëè÷èíà, íàçûâàåìàÿ öåëåâîé ôóíêöèåé;
� opt {min }� , max — òèï îïòèìèçàöèîííîé ïðîáëåìû.
Äëÿ NPO-ïðîáëåìû Ï { Sol opt}� E m, , , îïòèìàëüíîå ðåøåíèå ýêçåìïëÿðà I
ñ Ï îáîçíà÷èì S I* ( ), åãî âåëè÷èíó m I S I( , ( ) )* — êàê opt ( )I .
Îïðåäåëåíèå 2. Äëÿ NPO-ïðîáëåìû Ï Sol opt� ( , , , )E m ïðèáëèæåííûé (àï-
ïðîêñèìàöèîííûé) àëãîðèòì A — ýòî àëãîðèòì, êîòîðûé äëÿ äàííîãî ýêçåìïëÿ-
ðà I ñ Ï âûäàåò äîïóñòèìîå ðåøåíèå S I�Sol( ).
Åñëè A âûïîëíÿåòñÿ çà ïîëèíîìèàëüíîå âðåìÿ îòíîñèòåëüíî | |I , òî A íàçû-
âàåòñÿ ïîëèíîìèàëüíûì ïðèáëèæåííûì àëãîðèòìîì äëÿ Ï.
Êà÷åñòâî ïðèáëèæåííîãî àëãîðèòìà îáû÷íî îöåíèâàåòñÿ êàê îòíîøåíèå
� A I( ) (àïïðîêñèìàöèîííîå îòíîøåíèå) ìåæäó çíà÷åíèåì ïðèáëèæåííîãî ðåøå-
íèÿ m I A I( , ( )) è çíà÷åíèåì îïòèìàëüíîãî ðåøåíèÿ opt( )I . Òàêèì îáðàçîì, äëÿ
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 3
� Â.À. Ìèõàéëþê, 2011
ìèíèìèçàöèîííûõ ïðîáëåì àïïðîêñèìàöèîííîå îòíîøåíèå íàõîäèòñÿ â ïðåäåëå
[ , )1 � , äëÿ ìàêñèìèçàöèîííûõ — â [ , ]0 1 .
Îòíîñèòåëüíî êà÷åñòâà ïðèáëèæåííûõ àëãîðèòìîâ NPO-ïðîáëåìû êëàññè-
ôèöèðóþò ñëåäóþùèì îáðàçîì.
Îïðåäåëåíèå 3. NPÎ-ïðîáëåìà Ï ïðèíàäëåæèò êëàññó APX, åñëè ñóùåñòâóåò
ïîëèíîìèàëüíî ïðèáëèæåííûé àëãîðèòì A è ðàöèîíàëüíîå ÷èñëî r òàêîå, ÷òî
� A I r( ) � (ñîîòâåòñòâåííî � A I r( ) ) äëÿ äàííîãî I ñ
, åñëè Ï — ìèíèìèçàöèîí-
íàÿ (ìàêñèìèçàöèîííàÿ) ïðîáëåìà.  ýòîì ñëó÷àå A íàçûâàåòñÿ r-ïðèáëèæåííûì
(àïïðîêñèìàöèîííûì) àëãîðèòìîì (ïðîáëåìà Ï r-àïïðîêñèìèðóåìà àëãîðèòìîì A).
Äëÿ îòäåëüíûõ ïðîáëåì èç APX ìîæíî ââåñòè áîëåå ñèëüíóþ ôîðìó àï-
ïðîêñèìàöèîííîñòè. Äëÿ ëþáîãî ðàöèîíàëüíîãî r �1 (èëè r�( , )0 1 äëÿ ìàêñèìè-
çàöèîííûõ ïðîáëåì) ñóùåñòâóåò àëãîðèòì Ar è òðåáóåìûé ïîëèíîì p òàêîé, ÷òî
Ar — r-àïïðîêñèìàöèîííûé (ïðèáëèæåííûé) àëãîðèòì ñî âðåìåíåì, èçìåðÿå-
ìûì êàê p îò | |I . Ñåìåéñòâî àëãîðèòìîâ Ar (ïàðàìåòðèçîâàííîå ñ ïîìîùüþ r)
íàçûâàåòñÿ ïîëèíîìèàëüíî ïðèáëèæåííîé ñõåìîé (Polynomial Time Approximation
Scheme — PTAS).
Îïðåäåëåíèå 4. NPO-ïðîáëåìà Ï ïðèíàäëåæèò êëàññó PTAS, åñëè äëÿ ëþ-
áîãî ðàöèîíàëüíîãî r �1 (ñîîòâåòñòâåííî r�( , )0 1 ) è ëþáîãî ýêçåìïëÿðà I ñ Ï
ñóùåñòâóåò òàêàÿ ïîëèíîìèàëüíî ïðèáëèæåííàÿ ñõåìà Ar , ÷òî � Ar
I r( ) � (ñîîò-
âåòñòâåííî � Ar
I r( ) ) äëÿ Ï-ìèíèìèçàöèîííîé (Ï-ìàêñèìèçàöèîííîé) ïðîáëåìû.
Çàìå÷àíèå 1. Îïðåäåëåíèå 4 ýêâèâàëåíòíî ñëåäóþùåìó. NPO-ïðîáëåìà Ï
ïðèíàäëåæèò êëàññó PTAS, åñëè äëÿ ëþáîãî ðàöèîíàëüíîãî �� 0 è ëþáîãî ýêçåì-
ïëÿðà I ñ Ï ñóùåñòâóåò òàêàÿ ïîëèíîìèàëüíî ïðèáëèæåííàÿ ñõåìà A� , ÷òî
� �
�A I( ) � �1 (ñîîòâåòñòâåííî � �
�A I( )
1 ) äëÿ Ï-ìèíèìèçàöèîííîé (Ï-ìàêñèìè-
çàöèîííîé) ïðîáëåìû.
Çàìåòèì, ÷òî â îïðåäåëåíèè PTAS âðåìÿ àëãîðèòìà Ar ïîëèíîìèàëüíî îò-
íîñèòåëüíî ðàçìåðà âõîäà, îäíàêî îíî ìîæåò áûòü ýêñïîíåíöèàëüíî îòíîñè-
òåëüíî 1/ � . Ëó÷øàÿ ñèòóàöèÿ âîçíèêàåò, êîãäà âðåìÿ âûïîëíåíèÿ ïîëèíîìèàëü-
íî êàê ïî ðàçìåðó âõîäà, òàê è îòíîñèòåëüíî 1/ � .  ýòîì ñëó÷àå àëãîðèòì íàçû-
âàåòñÿ ïîëíîñòüþ ïîëèíîìèàëüíîé ïðèáëèæåííîé ñõåìîé (Fully Polynomial Time
Approximation Scheme — FPTAS).
Îïðåäåëåíèå 5. NPO-ïðîáëåìà ïðèíàäëåæèò êëàññó FPTAS, åñëè îíà äîïóñ-
êàåò ïîëíîñòüþ ïîëèíîìèàëüíóþ ïðèáëèæåííóþ ñõåìó.
Åñëè P � NP, òî èìååò ìåñòî âêëþ÷åíèå FPTAS PTAS APX NPO� � � .
Èçâåñòíû ñëåäóþùèå äàííûå î ñóùåñòâîâàíèè ïðèáëèæåííûõ ïîëèíîìèàëü-
íûõ ñõåì äëÿ ðåîïòèìèçàöèè äèñêðåòíûõ çàäà÷ îïòèìèçàöèè [10]. Â ïðåäïîëîæå-
íèè P � NP íå ñóùåñòâóåò FPTAS äëÿ çàäà÷è î êîììèâîÿæåðå íà ìèíèìóì ñ íåðà-
âåíñòâîì òðåóãîëüíèêà ïðè óâåëè÷åíèè (óìåíüøåíèè) çíà÷åíèÿ âåñà åäèíñòâåííîãî
ðåáðà. Åñëè P � NP, òî ñóùåñòâóåò PTAS äëÿ çàäà÷è î êîììèâîÿæåðå íà ìàêñèìóì
ñ íåðàâåíñòâîì òðåóãîëüíèêà òàêæå ïðè óâåëè÷åíèè (óìåíüøåíèè) çíà÷åíèÿ âåñà
åäèíñòâåííîãî ðåáðà, îäíàêî äëÿ ýòîé æå çàäà÷è íå ñóùåñòâóåò FPTAS. Íå ñóùå-
ñòâóåò FPTAS äëÿ çàäà÷è «ìèíèìàëüíîå äåðåâî Øòåéíåðà» ñ íåðàâåíñòâîì òðåó-
ãîëüíèêà ïðè óìåíüøåíèè âåñà åäèíñòâåííîãî ðåáðà, åñëè P � NP.
ÏÎËÈÍÎÌÈÀËÜÍÎ ÏÐÈÁËÈÆÅÍÍÛÅ ÑÕÅÌÛ ÄËß «ÍÀÑËÅÄÑÒÂÅÍÍÛÕ» ÏÐÎÁËÅÌ
Ïóñòü G V E� ( , ) — ãðàô ñ ìíîæåñòâîì âåðøèí V è ìíîæåñòâîì ðåáåð E. Áó-
äåì ñ÷èòàòü íåêîòîðîå ñâîéñòâî íà ãðàôàõ «íàñëåäñòâåííûì» ïðè âûïîëíåíèè
ñëåäóþùèõ óñëîâèé. Åñëè G V E� ( , ) óäîâëåòâîðÿåò òàêîìó ñâîéñòâó, òî äëÿ
ëþáîãî V V�� ïîäãðàô G V[ ]� , èíäóöèðîâàííûé V �, óäîâëåòâîðÿåò ýòîìó æå
ñâîéñòâó, íàïðèìåð, íåçàâèñèìîñòü, äâóäîëüíîñòü, ïëàíàðíàñòü — òðè «íà-
ñëåäñòâåííûõ» ñâîéñòâà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 3 43
Îïðåäåëåíèå 6. Ïóñòü G V E w� ( , , ) — âçâåøåííûé âåðøèííûé ãðàô. Íàçî-
âåì Hered (íàñëåäñòâî) êëàññ ïðîáëåì íàõîæäåíèÿ äëÿ ãðàôà G V E� ( , ) ïîäìíî-
æåñòâà âåðøèí S òàêèõ, ÷òî:
à) G S[ ] óäîâëåòâîðÿåò «íàñëåäñòâåííîìó» ñâîéñòâó;
á) çíà÷åíèå w S w v
v S
( ) ( )�
�
� ìàêñèìàëüíî.
Íàïðèìåð, Max Weighted Independent Set (ìàêñèìàëüíîå âçâåøåííîå íåçàâè-
ñèìîå ìíîæåñòâî), Max Weighted Bipartite Subgraph (ìàêñèìàëüíûé âçâåøåííûé
äâóäîëüíûé ïîäãðàô), Max Weighted Planar Subgraph (ìàêñèìàëüíûé âçâå-
øåííûé ïëàíàðíûé ïîäãðàô) — òðè èçâåñòíûå ïðîáëåìû Hered, êîòîðûå ñî-
îòâåòñòâóþò òðåì «íàñëåäñòâåííûì» ñâîéñòâàì.
Òåîðåìà 1 [7]. Ïóñòü Ï — ïðîáëåìà èç Hered. Ïðè âñòàâêå âåðøèíû ðåîïòè-
ìèçàöèÿ Ï àïïðîêñèìèðóåìà ñ îòíîøåíèåì 1 2/ (â êîíñòàíòíîå âðåìÿ).
Ðàññìîòðèì íåâçâåøåííûå ïðîáëåìû, ò.å. êîãäà âñå âåðøèíû èìåþò âåñ
åäèíèöà. Ïóñòü I — íà÷àëüíûé ýêçåìïëÿð Ï, I � — îêîí÷àòåëüíûé ýêçåìïëÿð Ï
(âñòàâëÿåòñÿ íîâàÿ âåðøèíà v), S * — îïòèìàëüíîå ðåøåíèå íà I , S I �
* — îïòè-
ìàëüíîå ðåøåíèå íà I �. Åñëè âñòàâëÿåòñÿ òîëüêî îäíà âåðøèíà, íà÷àëüíîå îïòè-
ìàëüíîå ðåøåíèå èìååò àáñîëþòíóþ îøèáêó, íå áîëüøóþ åäèíèöû â îêîí÷à-
òåëüíîì ýêçåìïëÿðå, ò.å. èìååò ìåñòî
| | | |* *S S I
� 1 .
Ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2 [7]. Ïðè âñòàâêå íîâîé âåðøèíû ðåîïòèìèçàöèÿ ëþáîé íåâçâå-
øåííîé ïðîáëåìû èç Hered ïðåäïîëàãàåò ñóùåñòâîâàíèå PTAS.
Äîêàçàòåëüñòâî. Ïóñòü �� 0 ôèêñèðîâàíî, ïîëîæèì k � [ / ]1 � . Ðàññìîòðèì
ñëåäóþùèé àëãîðèòì.
1. Ïðîòåñòèðîâàòü âñå ïîäìíîæåñòâà V ðàçìåðà íå áîëüøå k è ïóñòü S1 —
íàèáîëüøåå èç íèõ òàêîå, ÷òî G S[ ]1 óäîâëåòâîðÿåò «íàñëåäñòâåííîìó» ñâîéñòâó.
2. Âûâåñòè òàêîå ðåøåíèå S èç S1 è S *, êîòîðîå èìååò áîëüøåå ÷èñëî
âåðøèí. Òîãäà, åñëè S I �
* èìååò ðàçìåð, íå áîëüøèé 1/ � , íàéäåì åãî íà øàãå 1.
Èíà÷å, | |*S I �
1
�
è
| |
| |
| |
| |
*
*
*
*
S
S
S
SI
I
I�
�
�
1
1 � .
Àëãîðèòì ïîëèíîìèàëåí ïðè � � const.
 äàííîì ñëó÷àå ñóùåñòâîâàíèå PTAS ñëåäóåò èç äâóõ ñâîéñòâ: àáñîëþòíàÿ
îøèáêà íå áîëüøå åäèíèöû; ïðîñòîòà ðàññìàòðèâàåìûõ ïðîáëåì. Ïðîáëåìà íà-
çûâàåòñÿ ïðîñòîé [11], åñëè äëÿ ôèêñèðîâàííîé êîíñòàíòû k îïðåäåëèòü, ÷òî
îïòèìàëüíîå ðåøåíèå èìååò çíà÷åíèå íå áîëüøå k (ìàêñèìèçàöèÿ), ìîæíî çà ïî-
ëèíîìèàëüíîå âðåìÿ. Ýòîò ðåçóëüòàò êîððåêòåí äëÿ Min Vertex Cover (ìèíèìàëü-
íîå âåðøèííîå ïîêðûòèå) è íå ïðàâîìåðåí äëÿ Minimum Edge Coloring (ìèíè-
ìàëüíàÿ ðåáåðíàÿ ðàñêðàñêà).
ÏÎËÈÍÎÌÈÀËÜÍÎ ÏÐÈÁËÈÆÅÍÍÛÅ ÑÕÅÌÛ È ÐÅÎÏÒÈÌÈÇÀÖÈß NPO-ÏÐÎÁËÅÌ
Ïðåäñòàâëÿþò èíòåðåñ âîïðîñû äîêàçàòåëüñòâà íåñóùåñòâîâàíèÿ PTAS äëÿ
NPO-ïðîáëåì (NPO-ïðîáëåìû — îïòèìèçàöèîííûå âåðñèè NP-ïîëíûõ ïðîáëåì
ðàñïîçíàâàíèÿ ñâîéñòâ) â ïðåäïîëîæåíèè P � NP. Íàèáîëåå ïðîñòîé òåõíèêîé
òàêèõ äîêàçàòåëüñòâ ÿâëÿåòñÿ òåõíèêà «ùåëè» (gap technique), âïåðâûå èñ-
ïîëüçîâàííàÿ â ñåðåäèíå 1970-õ ãîäîâ (íàïðèìåð, â [12]). Åå èäåÿ ñîñòîèò
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 3
â äîêàçàòåëüñòâå NP-òðóäíîñòè ñ ïîìîùüþ ïîëèíîìèàëüíûõ ñâîäèìîñòåé, ÷òî
ñïîñîáñòâóåò îáðàçîâàíèþ «ùåëè» ìåæäó öåëåâûìè çíà÷åíèÿìè íåò-ýêçåìïëÿ-
ðîâ è öåëåâûìè çíà÷åíèÿìè äà-ýêçåìïëÿðîâ. Íàèáîëåå ïîëíî ýòî áóäåò âûðà-
æåíî ïðè óñòàíîâëåíèè êðèòåðèÿ íåñóùåñòâîâàíèÿ PTAS äëÿ ðåîïòèìèçà-
öèè NPO-ïðîáëåì.
Ïóñòü
— NPO-ïðîáëåìà è ñîãëàñíî îïðåäåëåíèþ 1 I E� (I — ýêçåì-
ïëÿð
), S I�Sol ( ) — äîïóñòèìîå ðåøåíèå, m I S( , ) — çíà÷åíèå (÷èñëîâîå)
öåëåâîé ôóíêöèè, opt � min (äëÿ îïðåäåëåííîñòè), S I* ( ) — îïòèìàëüíîå ðåøåíèå
Ï ñ I , opt( )I — ÷èñëîâîå çíà÷åíèå m I S I( , ( ))* .
Ïóñòü I � — íåêîòîðîå «íåçíà÷èòåëüíîå» èçìåíåíèå ýêçåìïëÿðà I .
Ðåîïòèìèçàöèîííóþ ïðîáëåìó, ñîîòâåòñòâóþùóþ I �, îáîçíà÷èì
( , ( ,I m I�
S I( )), S I I I*( ) ) ( , )� �
. Ðåîïòèìèçàöèîííûé àëãîðèòì äëÿ
( , )I I� ñîñòîèò â ðå-
øåíèè çàäà÷è Ï ñ I � è öåëåâîé ôóíêöèåé m I S I( , ( )) ñ èñïîëüçîâàíèåì îïòèìàëü-
íîãî ðåøåíèÿ I (S I*( )). Äîïóñòèì, ÷òî äëÿ ìèíèìèçàöèîííîé NPO-ïðîáëåìû
âñå äîïóñòèìûå ðåøåíèÿ âñåõ ýêçåìïëÿðîâ èìåþò öåëûå íåîòðèöàòåëüíûå çíà-
÷åíèÿ öåëåâîé ôóíêöèè.
Òåîðåìà 3. Ïóñòü X — NP-òðóäíàÿ ïðîáëåìà ðàñïîçíàâàíèÿ ñâîéñòâ,
( , )I I� — ìèíèìèçàöèîííàÿ ðåîïòèìèçàöèîííàÿ ïðîáëåìà è T — ïîëèíîìèàëü-
íî âû÷èñëèìîå ïðåîáðàçîâàíèå ìíîæåñòâà ýêçåìïëÿðîâ X âî ìíîæåñòâî ýêçåì-
ïëÿðîâ
( , )I I� òàêîå (a b� — ôèêñèðîâàííûå íåîòðèöàòåëüíûå öåëûå), ÷òî:
1) êàæäûé äà-ýêçåìïëÿð X îòîáðàæàåòñÿ íà ýêçåìïëÿð
( , )I I� ñî çíà÷åíèåì
öåëåâîé ôóíêöèè, íå áîëüøèì a;
2) êàæäûé íåò-ýêçåìïëÿð X îòîáðàæàåòñÿ íà ýêçåìïëÿð
( , )I I� ñî çíà÷åíè-
åì öåëåâîé ôóíêöèè, íå ìåíüøèì b.
Òîãäà äëÿ ðåîïòèìèçàöèè
( , )I I� íå ñóùåñòâóåò ïîëèíîìèàëüíîãî �-ïðèáëè-
æåííîãî àëãîðèòìà ñ êîýôôèöèåíòîì ��
b
a
, åñëè P � NP. Ýòî îçíà÷àåò, ÷òî äëÿ
ðåîïòèìèçàöèè
( , )I I� íå ñóùåñòâóåò PTAS, åñëè P � NP.
Äîêàçàòåëüñòâî. Äîïóñòèì, ÷òî ñóùåñòâóåò ïîëèíîìèàëüíûé �-ïðèáëèæåí-
íûé àëãîðèòì ñ êîýôôèöèåíòîì ��
b
a
. Ïóñòü I — ïðîèçâîëüíûé ýêçåìïëÿð ïðî-
áëåìû X ; ïðèìåíèì ïîëèíîìèàëüíîå ïðåîáðàçîâàíèå T . Äëÿ ýêçåìïëÿðà
I T I� � ( ) èñïîëüçóåì ïîëèíîìèàëüíûé ïðèáëèæåííûé àëãîðèòì (äëÿ ïðîáëåìû
( , )I I� ). Åñëè I ÿâëÿåòñÿ äà-ýêçåìïëÿðîì, òî çíà÷åíèå ôóíêöèè öåëè T I( ) íå
áîëüøå a è ïðèáëèæåííûé àëãîðèòì äàñò ðåøåíèå ñî çíà÷åíèåì, ñòðîãî ìåíü-
øèì, ÷åì
b
a
a b
�
�
�
�
�
� � . Åñëè I — íåò-ýêçåìïëÿð, òî çíà÷åíèå ôóíêöèè öåëè T I( ) íå
ìåíüøå b è ïðèáëèæåííûé àëãîðèòì íå ìîæåò äàòü ðåøåíèå ñî çíà÷åíèåì,
ìåíüøèì îïòèìàëüíîãî b. Òàêèì îáðàçîì, ìîæíî ðàçëè÷èòü çà ïîëèíîìèàëüíîå
âðåìÿ äà-ýêçåìïëÿðû (ïðèáëèæåííîå çíà÷åíèå T I b( )� ) è íåò-ýêçåìïëÿðû (ïðè-
áëèæåííîå çíà÷åíèå T I b( ) ) NP-òðóäíîé ïðîáëåìû X . Ýòî îçíà÷àåò ñóùåñòâî-
âàíèå ïîëèíîìèàëüíîãî àëãîðèòìà äëÿ ðàñïîçíàâàíèÿ NP-òðóäíîé çàäà÷è, ñëåäîâà-
òåëüíî, P � NP.
ÇÀÄÀ×À Î ÏÎÊÐÛÒÈÈ ÌÍÎÆÅÑÒÂÀÌÈ
Ðàññìîòðèì NPO-çàäà÷ó î ïîêðûòèè ìíîæåñòâàìè â ñëåäóþùåé ïîñòàíîâêå
(çàäà÷à Ï( , )A c ):
min ( ) | ( )f x c x x Q Ai i
i
n
� �
�
�
�
�
�
��
�
1
, Q A x B a x i mn
ij j
j
n
( ) | , , ,� � �
�
�
�
��
�
�
�
���
� 1 1
1
� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 3 45
Çäåñü B n n� { }0 1, ; A aij� { }, i m j n� �1 1, , , , ,� � ; A m n
( , ) — áóëåâà ìàòðèöà
( )m n� ; ci � 0, i n�1, ,� .
Ìàòðèöà A íå ñîäåðæèò íóëåâûõ ñòðîê è ñòðîê ñ îäíîé åäèíèöåé (óñëîâèå A).
Åñëè ci � 0 — öåëûå, i n�1, ,� , òî çàäà÷ó
( , )A c íàçîâåì âçâåøåííîé; åñëè
c i ni � �1 1, , ,� , òî çàäà÷ó
( , )A 1 íàçîâåì íåâçâåøåííîé (1 — n-ìåðíûé âåêòîð,
ñîñòîÿùèé èç åäèíèö).
Áóäåì ïîëüçîâàòüñÿ ñëåäóþùèìè ðåçóëüòàòàìè.
Èçâåñòíî [8], ÷òî æàäíûé àëãîðèòì ðåøàåò çàäà÷ó
( , )A c ñ îöåíêîé òî÷íîñòè
1
1
1 t
m
t
c A
�
� � �
( )
ln ,
ãäå c A( ) — ìàêñèìàëüíîå ÷èñëî åäèíèö â ñòîëáöå ìàòðèöû A, ò.å. æàäíûé àë-
ãîðèòì — ýòî (ln )m�1 -ïðèáëèæåííûé (àïïðîêñèìàöèîííûé) àëãîðèòì äëÿ ðå-
øåíèÿ
( , )A c .
 [9] ïîêàçàíî, ÷òî åñëè NP TIME loglog ( )( )nO n , òî äëÿ ïðîèçâîëüíîãî �� 0
íå ñóùåñòâóåò ïîëèíîìèàëüíîãî àëãîðèòìà, êîòîðûé ìîæåò àïïðîêñèìèðîâàòü
çàäà÷ó î ïîêðûòèè ìíîæåñòâàìè ñ êîýôôèöèåíòîì ( ) ln1
� m.
Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ äëÿ èçìåíåííûõ ýêçåìïëÿðîâ çàäà÷è
( , )A c :
( , , )A c Aj
� (ñîîòâåòñòâåííî
( , , )A c Aj
) îáîçíà÷èì çàäà÷ó
( , )A c
ñ çàìåíîé â ñòîëáöå j ìàòðèöû A ïðîèçâîëüíîãî 0 íà 1 (1 íà 0);
( , , )A Aj
� 1 (ñî-
îòâåòñòâåííî
( , , )A Aj
1 ) îáîçíà÷èì
( , )A Aj
� (ñîîòâåòñòâåííî
( , )A Aj
).
Äîïóñòèìîå ðåøåíèå S j jk� { }1, ,� çàäà÷è
( , )A c áóäåì èíòåðïðåòèðîâàòü
êàê ñîâîêóïíîñòü ñòîëáöîâ { }j jk1, ,� (ïîäìíîæåñòâ ìíîæåñòâà { }1, ,� m ), êîòî-
ðûå ñîñòàâëÿþò ïîêðûòèå ìàòðèöû A (ò.å. S j jk� { }1, ,� ñîîòâåòñòâóåò äîïóñòè-
ìûé âåêòîð x x x Q An� �( , , ) ( )1 � òàêîé, ÷òî x x xj j jk1 2
1� � � �� ; îñòàëüíûå
êîìïîíåíòû ðàâíû íóëþ). Ïîä âåñîì c S( ) ðåøåíèÿ S áóäåì ïîíèìàòü
c S c cj jk
( ) � � �
1
� .
Ðàññìîòðèì NP-ïîëíóþ (à çíà÷èò, NP-òðóäíóþ) çàäà÷ó ðàñïîçíàâàíèÿ
ñâîéñòâ «Ìèíèìàëüíîå ïîêðûòèå» (ÌÏ) [13], êîòîðàÿ ñîîòâåòñòâóåò íåâçâåøåí-
íîé NPO-çàäà÷å î ïîêðûòèè ìíîæåñòâàìè.
Óñëîâèå. Çàäàíî ñåìåéñòâî Å ( | |E n� ) ïîäìíîæåñòâ ìíîæåñòâà S S m(| | )� è
ïîëîæèòåëüíîå öåëîå ÷èñëî a.
Âîïðîñ. Ñîäåðæèò ëè Å ïîêðûòèå ìíîæåñòâà S ðàçìåðà íå áîëåå a, ò.å. íàé-
äåòñÿ ëè ïîäìíîæåñòâî E E�� òàêîå, ÷òî | |E a� � è e S
e E
�
� �
� ?
Òåîðåìà 4. Åñëè P � NP, òî äëÿ ðåîïòèìèçàöèè çàäà÷è
( , )A Aj
� íå ñó-
ùåñòâóåò PTAS.
Äîêàçàòåëüñòâî. Ïðèìåíèì òåîðåìó 3.  êà÷åñòâå X — NP-òðóäíîé ïðîáëåìû
ðàñïîçíàâàíèÿ ñâîéñòâ — ðàññìîòðèì çàäà÷ó ÌÏ, â êà÷åñòâå
( , )I I� — çàäà÷ó
( , )A Aj
� . Ïóñòü T A( ) — ïðåîáðàçîâàíèå ìàòðèöû A, ñîñòîÿùåå â çàìåíå ïðîèç-
âîëüíîãî ýëåìåíòà 0 â ñòîëáöå j íà 1, ò.å. A T Aj
� � ( ). ßñíî, ÷òî T — ïîëèíîìèàëüíî
âû÷èñëèìîå ïðåîáðàçîâàíèå ýêçåìïëÿðîâ X âî ìíîæåñòâî ýêçåìïëÿðîâ
( , )A Aj
� .
Ïîëîæèì b a� �1 è ïîêàæåì, ÷òî âûïîëíÿþòñÿ óñëîâèÿ 1, 2 òåîðåìû 3.
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 3
Ïóñòü E E E Ej j jk
� � { }
1 2
, , ,� — ïîêðûòèå ìíîæåñòâà S , ÷òî ñîîòâåòñòâóåò
äà-ýêçåìïëÿðó çàäà÷è X èç ï. 1 òåîðåìû 3 ( | |E k a� � � ). Ýòîò ýêçåìïëÿð îòîáðà-
æàåòñÿ íà äîïóñòèìîå ðåøåíèå x x xn� ( , , )1 � çàäà÷è
( , )A Aj
� òàêîå, ÷òî
x xj j1 2
� �� �� �x jk
1 (äîïóñòèìîå ðåøåíèå â ñèëó ïðåîáðàçîâàíèÿ T) ñî çíà-
÷åíèåì öåëåâîé ôóíêöèè c k aj
j j jk
� �
�
�
{ }1, ,�
(ci �1, i n�1, , )� , è ï. 1 òåîðåìû 3
âûïîëíåí.
Ïóñòü E E E Ej j jk
� � { }
1 2
, , ,� — ïîêðûòèå ìíîæåñòâà S , ÷òî ñîîòâåòñòâóåò
íåò-ýêçåìïëÿðó çàäà÷è X èç ï. 2 ( | |E k a� � �1). Ýòîò ýêçåìïëÿð îòîáðàæàåòñÿ
íà äîïóñòèìîå ðåøåíèå x x xn� ( , , )1 � çàäà÷è
( , )A Aj
� òàêîå, ÷òî
x x xj j jk1 2
1� � � �� (äîïóñòèìîå ðåøåíèå â ñèëó ïðåîáðàçîâàíèÿ T) ñî çíà÷å-
íèåì öåëåâîé ôóíêöèè c k aj
j j jk
� �
�
� 1
1{ }, ,�
, è ï. 2 âûïîëíåí.
Òàêèì îáðàçîì, óñëîâèÿ òåîðåìû 3 âûïîëíåíû. Ñëåäîâàòåëüíî, äëÿ ðåîïòè-
ìèçàöèè
( , )A Aj
� íå ñóùåñòâóåò ïîëèíîìèàëüíîãî �-ïðèáëèæåííîãî àëãîðèòìà
ñ êîýôôèöèåíòîì ��
�
� �
a
a a
1
1
1
, åñëè P � NP. Ýòî îçíà÷àåò, ÷òî äëÿ ðåîïòèìè-
çàöèè
( , )A Aj
� íå ñóùåñòâóåò PTAS, åñëè P � NP.
Òåîðåìà äîêàçàíà.
Òåîðåìà 5. Åñëè P � NP, òî äëÿ ðåîïòèìèçàöèè çàäà÷è
( , )A Aj
íå ñóùåñ-
òâóåò PTAS.
Äîêàçàòåëüñòâî. Ïðèìåíèì òåîðåìó 3.  êà÷åñòâå X — NP-òðóäíîé ïðîáëå-
ìû ðàñïîçíàâàíèÿ ñâîéñòâ — ðàññìîòðèì çàäà÷ó ÌÏ, â êà÷åñòâå
( , )I I� — çàäà÷ó
( , )A Aj
. Ïóñòü T A( ) — ïðåîáðàçîâàíèå ìàòðèöû A, ñîñòîÿùåå â çàìåíå ïðîèç-
âîëüíîãî ýëåìåíòà 1 â ñòîëáöå j íà 0, ò.å. A T Aj
� ( ). Î÷åâèäíî, ÷òî T — ïîëèíîìè-
àëüíî âû÷èñëèìîå ïðåîáðàçîâàíèå ýêçåìïëÿðîâ X âî ìíîæåñòâî ýêçåìïëÿðîâ
( , )A Aj
. Ïîëîæèì b a� �1è ïîêàæåì, ÷òî âûïîëíÿþòñÿ óñëîâèÿ 1 è 2 òåîðåìû 3.
Ïóñòü E E E Ej j jk
� � { }
1 2
, , ,� — ïîêðûòèå ìíîæåñòâà S , ÷òî ñîîòâåòñòâóåò
äà-ýêçåìïëÿðó çàäà÷è X èç ï. 1 òåîðåìû 3 ( | |E k a� � � ). Åñëè x x xn� ( , , )1 � òà-
êîå, ÷òî x x xj j jk1 2
1� � � �� — äîïóñòèìîå ðåøåíèå çàäà÷è
( , )A Aj
, òî äå-
éñòâóåì, êàê ïðè äîêàçàòåëüñòâå òåîðåìû 4. Èíà÷å, ïóñòü ýëåìåíò 1 ìàòðèöû A,
êîòîðûé çàìåíÿåòñÿ íà 0, íàõîäèòñÿ â ñòðîêå i m1 1�{ }, ,� è ñòîëáöå
j j js k�{ }1, ,� . Òàêèì îáðàçîì, ðåøåíèå x x xn� ( , , )1 � , òàêîå, ÷òî
x x xj j jk1 2
1� � � �� , íå ïîêðûâàåò ñòðîêó i1. Òîãäà â ñèëó óñëîâèÿ À ñóùåñòâó-
åò òàêîå js1
, ÷òî ai js1 1
1� .  ýòîì ñëó÷àå E E j j j jj k s� � �{ { } }� ��: , , \1
{ }E js1
� ñîñòàâëÿåò ïîêðûòèå A T Aj
� ( ), ïðè÷åì | |E k a� � � . Ïîñòðîèì ïîêðû-
òèå, ñîîòâåòñòâóþùåå
( , )A Aj
. Â ñèëó óñëîâèÿ À ñóùåñòâóåò òàêîå js1
, ÷òî ýëå-
ìåíò ìàòðèöû a
i js1 1
1� . Òîãäà x x xn� ( , , )1 � , òàêîå, ÷òî x j �1 ïðè j j�( ,{ 1 �
... , \ )j j j Jk s s} { }
1� � , ÿâëÿåòñÿ ïîêðûòèåì
( , )A Aj
òàêèì, ÷òî c k aj
j J
� �
�
� , è
ï. 1 âûïîëíåí.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 3 47
Äëÿ äîêàçàòåëüñòâà âûïîëíåíèÿ ï. 2 äåéñòâóåì àíàëîãè÷íî. Ïðè ýòîì
íåò-ýêçåìïëÿð çàäà÷è X (| |E a� �1) îòîáðàæàåòñÿ íà äîïóñòèìîå ðåøåíèå
( , )A Aj
ñî çíà÷åíèåì öåëåâîé ôóíêöèè, íå ìåíüøèì a �1 . Òàêèì îáðàçîì, âñå
óñëîâèÿ òåîðåìû 3 âûïîëíåíû. Ñëåäîâàòåëüíî, äëÿ ðåîïòèìèçàöèè
( , )A Aj
íå
ñóùåñòâóåò ïîëèíîìèàëüíîãî �-ïðèáëèæåííîãî àëãîðèòìà ñ êîýôôèöèåíòîì
��
�
� �
a
a a
1
1
1
, åñëè P � NP. Ýòî îçíà÷àåò, ÷òî äëÿ ðåîïòèìèçàöèè
( , )A Aj
íå
ñóùåñòâóåò PTAS, åñëè P � NP.
Òåîðåìà äîêàçàíà.
Çàìå÷àíèå 2. Àíàëîãè÷íîå äîêàçàòåëüñòâî êîððåêòíî è äëÿ ëþáîé âçâå-
øåííîé çàäà÷è î ïîêðûòèè ìíîæåñòâàìè, îäíàêî «ùåëü» áóäåò áîëåå øèðî-
êîé (b a� �1).
ÇÀÄÀ×À «ÐÀÑÊÐÀØÈÂÀÅÌÎÑÒÜ ÃÐÀÔÀ»
Ðàññìîòðèì çàäà÷ó «Ðàñêðàøèâàåìîñòü ãðàôà» (ÐÃ) [13].
Óñëîâèå. Çàäàíû ãðàô G V E� ( , ) è ïîëîæèòåëüíîå öåëîå ÷èñëî K K V( | | )� .
Âîïðîñ. Âåðíî ëè, ÷òî ãðàô G K-ðàñêðàøèâàåì? (Ãðàô íàçûâàåòñÿ K-ðàñ-
êðàøèâàåìûì, åñëè ñóùåñòâóåò íåêàÿ ôóíêöèÿ f V K: , , ,! { }1 2 � òàêàÿ, ÷òî åñëè
{ }u v E, � , òî f u f v( ) ( )� .)
Çàäà÷à Ðà — NP-ïîëíà (à çíà÷èò, NP-òðóäíà) äëÿ K 3 [13].
Ñ çàäà÷åé Ðà ñîïîñòàâèì NPO-çàäà÷ó «ìèíèìàëüíàÿ ðàñêðàøèâàåìîñòü ãðà-
ôà» (Min ÐÃ) — íàõîæäåíèå ìèíèìàëüíîãî K òàêîãî, ÷òî ãðàô G V E� ( , ) K-ðàñ-
êðàøèâàåì. Çàäà÷ó Min ÐÃ çàïèøåì â âèäå G V E w� ( , , ), ãäå w — öåëåâàÿ
ôóíêöèÿ (÷èñëî êðàñîê), w! min. Ðàññìîòðèì ñëåäóþùóþ ðåîïòèìèçàöèîí-
íóþ çàäà÷ó. Ïóñòü ãðàô G V E w� � � �( , , ) ïîëó÷åí èç ãðàôà G V E w� ( , , ) âñòàâêîé
ïðîèçâîëüíîé âåðøèíû ñ íå áîëåå ÷åì äâóìÿ ðåáðàìè, èíöèäåíòíûìè åé. Çàäà÷à
ðåîïòèìèçàöèè G� ñîñòîèò â íàõîæäåíèè åå ðåøåíèÿ (ïðèáëèæåííîãî), èñõîäÿ èç
îïòèìàëüíîãî ðåøåíèÿ G ñî çíà÷åíèåì wmin .
Òåîðåìà 6. Åñëè P � NP, òî äëÿ ðåîïòèìèçàöèè çàäà÷è G V E w� � � �( , , ) íå ñó-
ùåñòâóåò PTAS.
Äîêàçàòåëüñòâî. Ïðèìåíèì òåîðåìó 3.  êà÷åñòâå X — NP-òðóäíîé ïðî-
áëåìû ðàñïîçíàâàíèÿ ñâîéñòâ — ðàññìîòðèì çàäà÷ó Ðà ñ K � 3, â êà÷åñòâå
( , )I I� — çàäà÷ó G�. Ïóñòü T — ïðåîáðàçîâàíèå, ñîïîñòàâëÿþùåå ìíîæåñòâàì
V E, ñîîòâåòñòâåííî ìíîæåñòâàV E� �, è ðåøåíèþ G (äîïóñòèìîìó) — ðåøåíèå G �
(äîïóñòèìîå), êîòîðîå òîæäåñòâåííî ñîâïàäàåò ñ ðåøåíèåì G; T — ïîëèíîìè-
àëüíî âû÷èñëèìîå ïðåîáðàçîâàíèå. Ïîêàæåì âûïîëíåíèå óñëîâèé 1, 2 òåîðåìû 3
(ïîëîæèì a b� �3 4, ).
Äà-ýêçåìïëÿð çàäà÷è G V E� ( , ) — ýòî 3-ðàñêðàñêà ãðàôà G. Äîêàæåì, ÷òî
îíà áóäåò 3-ðàñêðàñêîé ãðàôà G�. Äåéñòâèòåëüíî, èñõîäÿ èç 3-ðàñêðàñêè G,
ìîæíî ðàñêðàñèòü âåðøèíó v ãðàôà G� (äîáàâëåííóþ, ñ íå áîëåå ÷åì äâóìÿ èíöè-
äåíòíûìè åé ðåáðàìè) öâåòîì, îòëè÷íûì îò äâóõ öâåòîâ (åñëè äîáàâëåíû äâà
ðåáðà), êîòîðûìè ðàñêðàøåíû â G ñîîòâåòñòâóþùèå âåðøèíû. Òàêèì îáðàçîì,
ïîëó÷èëè 3-ðàñêðàñêó ãðàôà G�, ò.å. ýêçåìïëÿð G V E w� � � �( , , ) ñî çíà÷åíèåì
w a� � 3, è ï. 1 âûïîëíåí.
Íåò-ýêçåìïëÿð çàäà÷è X — ýòî ðàñêðàñêà ãðàôà G íå ìåíåå ÷åòûðüìÿ öâåòà-
ìè, ÷òî ñîãëàñíî ï. 1 äàåò âîçìîæíîñòü ðàñêðàñèòü G� òàêæå íå ìåíåå ÷åòûðüìÿ
öâåòàìè, ò.å. ïîëó÷èëè ýêçåìïëÿð G V E w� � � �( , , ) ñî çíà÷åíèåì w 4, è ï. 2 âû-
ïîëíåí. Òîãäà ñîãëàñíî òåîðåìå 3 äëÿ ðåîïòèìèçàöèè G V E w� � � �( , , ) íå ñóùåñò-
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 3
âóåò ïîëèíîìèàëüíîãî �-ïðèáëèæåííîãî àëãîðèòìà ñ êîýôôèöèåíòîì �� �
b
a
4
3
,
åñëè P � NP. Ýòî îçíà÷àåò, ÷òî äëÿ ðåîïòèìèçàöèè G V E w� � � �( , , ) íå ñóùåñòâóåò
PTAS, åñëè P � NP.
Ïóñòü G V E w1 1 1� ( , , ) ïîëó÷àåòñÿ èç ãðàôà G V E w� ( , , ) óäàëåíèåì ïðîèç-
âîëüíîé âåðøèíû ñî âñåìè èíöèäåíòíûìè åé ðåáðàìè.
Òåîðåìà 7. Åñëè P � NP, òî äëÿ ðåîïòèìèçàöèè çàäà÷è G V E w1 1 1� ( , , ) íå ñó-
ùåñòâóåò PTAS.
Äîêàçàòåëüñòâî àíàëîãè÷íî ïðåäûäóùåìó è ñëåäóåò èç òîãî ôàêòà, ÷òî ïðà-
âèëüíàÿ ðàñêðàñêà ãðàôà — «íàñëåäñòâåííîå» ñâîéñòâî, à èìåííî, èç 3-ðàñêðàñêè
ãðàôà G V E w� ( , , ) âûòåêàåò 3-ðàñêðàñêà ãðàôà G V E w1 1 1� ( , , ) è èç íå ìåíåå ÷åì
4-ðàñêðàñêè ãðàôà G — íå ìåíåå ÷åì 4-ðàñêðàñêà ãðàôà G1.
ÇÀÄÀ×À «ÓÏÀÊÎÂÊÀ  ÊÎÍÒÅÉÍÅÐÛ»
Ðàññìîòðèì çàäà÷ó «Óïàêîâêà â êîíòåéíåðû» (ÓÊ) [13].
Óñëîâèå. Çàäàíû êîíå÷íîå ìíîæåñòâî U ïðåäìåòîâ, ðàçìåð s u Z( )� � êàæ-
äîãî ïðåäìåòà u U� , ïîëîæèòåëüíîå öåëîå ÷èñëî B — âìåñòèìîñòü êîíòåéíåðà,
ïîëîæèòåëüíîå öåëîå ÷èñëî K.
Âîïðîñ. Ñóùåñòâóåò ëè òàêîå ðàçáèåíèå ìíîæåñòâà U íà íåïåðåñåêàþùèåñÿ
ïîäìíîæåñòâà U U U K1 2, , ,� , ÷òî ñóììà ðàçìåðîâ ïðåäìåòîâ èç êàæäîãî ïîä-
ìíîæåñòâà U i íå ïðåâîñõîäèò B?
Ïðè K 2 ýòà çàäà÷à NP-ïîëíà [13]. NPO-âåðñèÿ çàäà÷è ÓÊ (Minimum Bin
Packing, Min ÓÊ) ñîñòîèò â ìèíèìèçàöèè K çàäà÷è ÓÊ (îáîçíà÷àåòñÿ
Min_ ÓÊ( , , , )U s B K , K ! min). Ðàññìîòðèì çàäà÷ó Min_ÓÊ (U s B K�, , , ), êîòîðàÿ
ïîëó÷àåòñÿ èç çàäà÷è Min_ÓÊ ( , , , )U s B K óäàëåíèåì ïðîèçâîëüíîãî ïðåäìåòà
u U� .
Òåîðåìà 8. Åñëè P � NP, òî äëÿ ðåîïòèìèçàöèè Min_ÓÊ ( , , , )U s B K� íå ñó-
ùåñòâóåò PTAS.
Äîêàçàòåëüñòâî. Ïðèìåíèì òåîðåìó 3.  êà÷åñòâå X — NP-òðóäíîé ïðî-
áëåìû ðàñïîçíàâàíèÿ ñâîéñòâ — ðàññìîòðèì çàäà÷ó ÓÊ ñ K � 2, â êà÷åñòâå
( , )I I� — çàäà÷ó Min_ÓÊ ( , , , )U s B K� . Ïóñòü T — ïîëèíîìèàëüíî âû÷èñëèìîå
ïðåîáðàçîâàíèå, êîòîðîå ñîïîñòàâëÿåò ìíîæåñòâó U ìíîæåñòâî U �, äîïóñòèìîìó
ðåøåíèþ U — äîïóñòèìîå ðåøåíèå U � èç ïï. 1 è 2 òåîðåìû 3 ñëåäóþùèì îáðàçîì
(ïîëîæèì a � 2 , b � 3).
Äà-ýêçåìïëÿðó çàäà÷è ÓÊ ñîîòâåòñòâóåò ðàçáèåíèå U íà äâà íåïåðåñåêàþ-
ùèõñÿ ïîäìíîæåñòâà — U U1 2, (òàêèõ, ÷òî ñóììà ðàçìåðîâ ïðåäìåòîâ èç êàæäî-
ãî ïîäìíîæåñòâà íå ïðåâîñõîäèò B). Ýòî ñîîòâåòñòâóåò ðàçáèåíèþ U � èç Min ÓÊ
òàêæå íà äâà ïîäìíîæåñòâà — U U1 2, (ýëåìåíò u óäàëÿåòñÿ ëèáî èç U 1, ëèáî èç
U 2) ñî çíà÷åíèåì öåëåâîé ôóíêöèè K � 2 , è ï. 1 âûïîëíåí.
Íåò-ýêçåìïëÿðó çàäà÷è ÓÊ ñîîòâåòñòâóåò ðàçáèåíèå U íà íå ìåíåå ÷åì òðè
íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà (òàêèõ, ÷òî ñóììà ðàçìåðîâ ïðåäìåòîâ èç êàæ-
äîãî ïîäìíîæåñòâà íå ïðåâîñõîäèò B). Ýòî ñîîòâåòñòâóåò ðàçáèåíèþ U � èç Min
ÓÊ òàêæå íà íå ìåíåå ÷åì òðè íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà (ïóòåì óäàëå-
íèÿ èç îäíîãî èç íèõ ýëåìåíòà u U� ) ñî çíà÷åíèåì öåëåâîé ôóíêöèè K 3, è ï. 2
âûïîëíåí.
Òîãäà ñîãëàñíî òåîðåìå 3 äëÿ ðåîïòèìèçàöèè Min_ÓÊ (U s B K�, , , ) íå ñóùåñ-
òâóåò ïîëèíîìèàëüíîãî �-ïðèáëèæåííîãî àëãîðèòìà ñ êîýôôèöèåíòîì
�� �
b
a
3
2
, åñëè P � NP. Ýòî îçíà÷àåò, ÷òî äëÿ ðåîïòèìèçàöèè Min_ÓÊ (U s B K�, , , )
íå ñóùåñòâóåò PTAS, åñëè P � NP.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 3 49
Çàìå÷àíèå 3. Ëåãêî âèäåòü, ÷òî òåîðåìà, àíàëîãè÷íàÿ òåîðåìå 8, èìååò ìåñ-
òî äëÿ ðåîïòèìèçàöèè Min_ÓÊ (U s B K, , , )� , ãäå s� ïîëó÷àåòñÿ ñ ïîìîùüþ s
óìåíüøåíèåì íà íåêîòîðîå ïîëîæèòåëüíîå öåëîå ÷èñëî äëÿ íåêîòîðûõ ýëåìåí-
òîâ u U� .
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A u s i e l l o G . , E s c o f f i e r B . , M o n n o t J . , a n d P a s c h o s V . T h . Reoptimization of
minimum and maximum traveling salesman’s tours // Algorithmic theory. SWAT 2006; Lect. Notes
Comput. Sci. — Berlin: Springer, 2006. — 4059. — P. 196–207.
2. O n t h e a p p r o x i m a b i l i t y of TSP on local modifications of optimal solved instances /
H.J. Bockenhauer, L. Forlizzi, J. Hromkovic, et al. // Algorithmic Oper. Res. — 2007. — 2 (2). —
P. 83–93.
3. B o c k e n h a u e r H . J . , H r o m k o v i c J . , M o m k e T . , a n d W i d m a y e r P . On the hard-
ness of reoptimization // Proc. of the 34 th Intern. Conf. on Current Trends in Theory and Practice of
Computer Science (SOF – SEM 2008); Lect. Notes Comput. Sci. — Berlin: Springer, 2008. —
4910. — P. 50–65.
4. E s c o f f i e r B . , M i l a n i c M . , a n d P a s c h o s V . T h . Simple and fast reoptimizations for
the Steiner tree problem // Algorithmic Oper. Res. — 2009. — 4 (2). — P. 86–94.
5. A r c h e t t i C . , B e r t a z z i L . , a n d S p e r a n z a M . G . Reoptimizing the travelling salesman
problem // Networks. — 2003. — 42 (3). — P. 154–159.
6. A r c h e t t i C . , B e r t a z z i L . , a n d S p e r a n z a M . G . Reoptimizing the 0-1 knapsack prob-
lem. — Manuscript, 2008.
7. A u s i e l l o G . , B o n i f a c i V . , a n d E s c o f f i e r B . Complexity and approximation in
reoptimization // Chapter of the book Computability in Context: Computation and Logic in the Real
World. — Imperial College Press, members of the 2007 Computability Europe conference CiE 2007:
Logic and Computation in the Real World (June, 2007). — P. 24–33.
8. C h v a t a l V . A . A greedy heuristic for the set covering problem // Math. Oper. Res. — 1979. —
4, N 3. — P. 233–235.
9. F e i g e U . A threshold of lnn for approximating set cover // J. ACM. — 1998. — 45, N 4. —
P. 634–652.
10. B e r g T . a n d H e m p e l H . Reoptimization of TSP and Steiner tree: Changing single
edge-weights // Lect. Notes Comput. Sci. — 2009. — 5457. — P. 141–151.
11. P a z A . , a n d M o r a n S . Non deterministic polynomial optimization problems and their ap-
proximations // Theoret. Comput. Sci. — 1981. — 15. — P. 251–277.
12. L e n s t r a J . K . , a n d R e n o o y K a n A . H . G . Complexity of scheduling under precedence
constraints // Oper. Res. — 1978. — 26. — P. 22–35.
13. à ý ð è Ì . , Ä æ î í ñ î í Ä . Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è. — Ì.:
Ìèð, 1982. — 416 ñ.
Ïîñòóïèëà 12.08.2010
50 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 3
|
| id | nasplib_isofts_kiev_ua-123456789-84200 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-24T11:53:39Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.А. 2015-07-03T16:20:49Z 2015-07-03T16:20:49Z 2011 К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 3. — С. 42-50. — Бібліогр.: 13 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84200 519.854 Показано, що для реоптимізації задачі про покриття множинами при вставленні або звільненні елемента в довільну множину не існує поліноміально наближеної схеми. Подібний результат має місце для задачі «мінімальне розфарбування графа» при вставленні довільної вершини не більше ніж з двома інцидентними їй ребрами і задачі «мінімальне пакування в контейнери» при звільненні довільного предмета. It is shown that no polynomial-time approximation scheme exists for the reoptimization of the set covering problem in inserting an element into or eliminating it from any set. A similar result is obtained for the minimum graph coloring problem in inserting a vertex with at most two incidence edges and for the minimal bin packing problem in eliminating any element. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации До питання про існування поліноміально наближених схем для реоптимізації дискретних задач оптимізації On the question of the existence of polynomial-time approximation schemes for reoptimization of discrete optimization problems Article published earlier |
| spellingShingle | К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации Михайлюк, В.А. Кибернетика |
| title | К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации |
| title_alt | До питання про існування поліноміально наближених схем для реоптимізації дискретних задач оптимізації On the question of the existence of polynomial-time approximation schemes for reoptimization of discrete optimization problems |
| title_full | К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации |
| title_fullStr | К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации |
| title_full_unstemmed | К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации |
| title_short | К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации |
| title_sort | к вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84200 |
| work_keys_str_mv | AT mihailûkva kvoprosuosuŝestvovaniipolinomialʹnopribližennyhshemdlâreoptimizaciidiskretnyhzadačoptimizacii AT mihailûkva dopitannâproísnuvannâpolínomíalʹnonabliženihshemdlâreoptimízacíídiskretnihzadačoptimízacíí AT mihailûkva onthequestionoftheexistenceofpolynomialtimeapproximationschemesforreoptimizationofdiscreteoptimizationproblems |