Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа
With the approximate solution of discrete optimization problems such idea arises: is it possible, taking into account the information about the optimal solution of an instance (or close to it), use this information to find the optimal (or close to it) solution of instance problem obtained as a resul...
Gespeichert in:
| Datum: | 2013 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2013
|
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/57494 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1867334253505675264 |
|---|---|
| author | Mikhailyuk, V. О. |
| author_facet | Mikhailyuk, V. О. |
| author_institution_txt_mv | [
{
"author": "V. О. Mikhailyuk",
"institution": "доцент кафедри прикладної математики та інформатики Волинського національного університету ім. Лесі Українки, Україна, Луцьк"
}
] |
| author_sort | Mikhailyuk, V. О. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-03-30T15:12:23Z |
| description | With the approximate solution of discrete optimization problems such idea arises: is it possible, taking into account the information about the optimal solution of an instance (or close to it), use this information to find the optimal (or close to it) solution of instance problem obtained as a result of minor local modifications of the initial instance. This approach, called reoptimization, allows, for example, in some cases, getting the best quality of approximation (which is defined as the ratio between the value of an approximate solution to the exact ratio and called approximation ratio) in locally modified instances than at initials. If for some tasks approximation ratio can not be improved (e.g. in class of all approximation algorithms with polynomial complexity), the ratio is called the threshold or optimal (algorithm which achieved this ratio is also called the threshold or optimal). The complexity of the algorithms is estimated by the number of hits (queries) to a special oracle. For reoptimization of minimum vertex cover problem (with addition of one vertex and some set of edges) (3/2)-approximation algorithm with additive error and sublinear (constant) complexity is received. It is shown that the approximation ratio of 3/2 is the threshold in the class of algorithms with constant complexity. |
| first_indexed | 2025-07-17T10:19:43Z |
| format | Article |
| fulltext |
© В.О. Михайлюк, 2013
Системні дослідження та інформаційні технології, 2013, № 1 79
TIДC
МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ
УПРАВЛІННЯ І ТЕОРІЯ ІГОР
УДК 519.854
СУБЛІНІЙНИЙ ОПТИМАЛЬНИЙ НАБЛИЖЕНИЙ
АЛГОРИТМ РЕОПТИМІЗАЦІЇ ДЛЯ ЗАДАЧІ ПРО
МІНІМАЛЬНЕ ВЕРШИННЕ ПОКРИТТЯ ГРАФА
В.О. МИХАЙЛЮК
За наближеного розв’язання дискретних задач оптимізації виникає така iдея:
чи можна, виходячи з інформації про оптимальний розв’язок екземпляра зада-
чі (або близького до нього), використовувати цю інформацію для знаходження
оптимального (або близького до нього) розв’язку екземпляра задачі, отримано-
го в результатi незначних локальних модифiкацiй вихiдного екземпляра. Цей
пiдхiд, названий реоптимізацією, дозволяє в деяких випадках отримати кращу
якiсть наближення (яке визначається як вiдношення значення наближеного
розв’язку до точного i називається вiдношенням апроксимацiї) у локально мо-
дифiкованих екземплярах, нiж у вихiдних. Якщо для деяких оптимiзацiйних
задач вiдношення апроксимацiї не можна покращити (наприклад, у класi всiх
наближених алгоритмiв із полiномiальною складнiстю), то таке вiдношення
називають пороговим або оптимальним (алгоритм на якому досягається це
вiдношення також називають пороговим або оптимальним). Складність алго-
ритмів оцінюється кількістю звернень (запитів) до спеціального оракулу. Для
реоптимізації задачі про мінімальне вершинне покриття графа (за добавлення
однієї вершини і деякої множини ребер) отриманий (3/2)-наближений алго-
ритм із адитивною помилкою з сублінійною (константною) складністю. Пока-
зано, що відношення апроксимації 3/2 є пороговим у класі алгоритмів із конс-
тантною складністю.
ВСТУП
Поняття сублінійних алгоритмів виникло завдяки необхідності обробки
величезних масивів інформації, що має місце в багатьох прикладненнях.
Кажуть, що алгоритм має сублiнiйну складнiсть, якщо час його роботи
оцiнюється величиною )(no , де n — розмiрнiсть входу. Для того, щоб
сублiнiйний алгоритм був точним треба, щоб вiн використовував паралель-
ну (некласичну) обробку даних або враховував спецiальнi обмеження на
вхiднi данi (наприклад, логарифмiчний бiнарний пошук у вiдсортованих ма-
сивах). Iнакше такий алгоритм не в змозi прочитати весь вхiд, щоб забезпе-
чити деякий результат роботи. Тому сублiнiйнi алгоритми мають видавати
результат без читання всього входу та мати доступ до нього тiльки деякими
обмеженими порцiями i бути випадковими, видаючи тільки наближенi
розв’язки. Ефективнiсть таких алгоритмiв вимiрюється так званою складнiстю
В.О. Михайлюк
ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 80
запитiв (query complexity) — кiлькiстю доступiв до деякого оракулу, що об-
робляє вхiд (порцiями).
Сублiнiйнi алгоритми знайшли широке застосування в роздiлi теоретич-
ної iнформатики, який називається «перевiрка властивостей проблем»
(property testing) [1, 2]. Перевiрка властивостей проблем (релаксацiя проблем
розпiзнавання) пов’язана з розробкою алгоритмiв (сублiнiйних), що
розрiзняють об’єкти із заданою властивiстю вiд об’єктiв, якi далекi вiд цiєї
властивості ε( -далекi, ε -far). Наприклад, для задач теорiї графiв із n вер-
шинами i обмеженою ступінню вершин d (ступінь вершини — число ребер
їй інцидентних) властиво: бути ε -далекими вiд деякої властивостi P озна-
чає добавити або видалити dnε ребер, щоб граф мав цю властивiсть .P
Сублiнiйнi алгоритми перевiрки властивостей (тестери) використовують у
теорiї навчання i теорiї наближення.
Задачу про мiнiмальне вершинне покриття графа (Min-Vertex-Cover)
сформулюємо так. Вершинним покриттям (vertex cover) неорiєнтованого
графа ),( EVG = називається така пiдмножина його вершин ,VV ⊂′ що для
довiльного ребра Evu ∈),( хоча б одна з вершин u або v мiститься в .V ′
Пiд розмiром покриття розумiється число його елементiв. Вимагається знай-
ти покриття мiнiмального розмiру. Через GVC будемо позначати оптималь-
ний розв’язок цiєї задачi, а через C ′ — наближений, GVC — число елемен-
тів у множині GVC (розмір), n число вершин в графi.
Задача про мiнiмальне вершинне покриття графа з обмеженою ступін-
ню const)( =d у контексті перевірки властивостей визначає чи існує сублі-
нійний алгоритм, що з високою ймовірністю встановлює чи має граф
вершинне покриття розміру ,nρ або цей граф є ε -далеким від цієї влас-
тивості. Останнє означає, що не менше ніж dn⋅ε ребер треба виключити
з графа, щоб він мав вершинне покриття розміром .nρ У [2] відмічено, що
результати по NP -складності наближення мінімального вершинного по-
криття розповсюджуються і на цю задачу.
У випадку графів із обмеженою ступінню постановка задачі субліній-
ного наближення мінімального вершинного покриття є наступне розширен-
ня задачі перевірки властивостей. Мета цієї задачі полягає у розрізненні ви-
падку, коли граф має вершинне покриття розміру ,nρ і випадку, коли граф
є ε -далеким від властивості мати вершинне покриття розміром .nρα ⋅ У [3]
показано, що будь-який наближений алгоритм для задачі про мінімальне
вершинне покриття з мультиплікативною помилкою не більше 7/6 вимагає
)(nΩ запитів.
При наближеному розв’язанні дискретних задач оптимізації виникає
така iдея: виходячи з оптимального розв’язку екземпляра задачі (або близь-
кого до нього) чи можна використати цю iнформацiю для знаходження оп-
тимального (або близького до нього) розв’язку екземпляра проблеми,
отриманого в результатi незначних локальних модифiкацiй вихiдного
екземпляра. Цей пiдхiд названо реоптимiзацiєю (вперше запропоновано
в [4]) дозволяє, наприклад, у деяких випадках отримати кращу якiсть набли-
ження (яке визначається як вiдношення значення наближеного розв’язку до
Сублінійний оптимальний наближений алгоритм реоптимізації для задачі …
Системні дослідження та інформаційні технології, 2013, № 1 81
точно модифiкованих екземплярах, нiж у вихiдних. Якщо для деяких оп-
тимiзацiйних задач вiдношення апроксимацiї не можна покращити (наприклад,
у класi всiх наближених алгоритмiв із полiномiальною складнiстю), то таке
вiдношення називають пороговим або оптимальним (алгоритм на якому до-
сягається це вiдношення також називають пороговим або оптимальним).
У [5] вдалося отримати точне значення порогового вiдношення апроксимацiї
для реоптимiзацiї узагальнених проблем про виконуванiсть спецiального
класу для алгоритмiв полiномiальної складностi.
Мета роботи — отримання точного значення порогового відношення
апроксимації для реоптимiзацiї задачi про мiнiмальне вершинне покриття
в графi в класi сублiнiйних алгоритмiв, зокрема константної складностi.
ОСНОВНІ ОЗНАЧЕННЯ І ПОНЯТТЯ
Розглянемо задачу про мiнiмальне вершинне покриття графа ).,( EVG =
Діаметр графа — це максимальна з відстаней між парами його вершин. Від-
стань між вершинами визначається як найменше число ребер, які необхідно
пройти, щоб дістатися з однієї вершини в іншу. Інакше кажучи, діаметр —
це відстань між двома вершинами графа, максимально віддаленими одна від
одної.
Означення 1. Нехай 1≥α та .10 ≤≤ ε Значення 'C є ),( εα — набли-
женням || GVC , якщо .|||| nVCCVC GG εα +≤′≤ Алгоритм, який для даного
0>ε в якостi вхiдного параметра обчислює з ймовiрнiстю не меншою нiж
2/3 ),( εα -наближення || GVC для деякого значення ,α називається
),( εα -наближеним алгоритмом або α -наближеним алгоритмом із адитив-
ною помилкою.
Складність алгоритмів будемо оцінювати кількістю звернень (запитів)
до спеціального оракулу. Два ребра є сусідніми, якщо вони мають спільну
вершину (дві вершини є сусідніми, якщо вони з’єднані ребром). На запит
),( iv відповіддю є i -й сусід вершини v або спеціальний символ у випадку,
коли v має менше ніж i сусідів. Іноді дозволяються оракули визначення
ступені вершин, коли для довільної вершини v видається її ступінь.
Означення 2. Будемо говорити, що для задачі про мінімальне вершин-
не покриття графа існує оптимальний ),( εα -наближений алгоритм із конс-
тантною складністю, якщо виконуються такі умови:
• для довільного 0>ε для задачі існує ),( εα -наближений алгоритм із
константною складністю;
• для довільного 0>ε існує таке ,0>δ що для задачі не існує
),( δεα − -наближеного алгоритму з константною складністю.
При цьому α називається порогом відношення апроксимації наближе-
ного алгоритму, а сам алгоритм — оптимальним α -наближеним алгорит-
мом із адитивною помилкою з константною складністю.
Будемо використовувати поняття розподіленого алгоритму (distributed
algorithm) [6, 7]. В основі розподіленої обчислювальної моделі лежить син-
В.О. Михайлюк
ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 82
хронна мережа ,G в якій вершини представляють процесори, а ребра — ко-
мунікаційні канали. Один раунд розподіленого алгоритму полягає в переси-
лці повідомлень від кожної вершини до сусідніх вершин. Після k раундів
кожна вершина закінчує свої обчислення і вся мережа досягає деякої глоба-
льної мети. Наприклад, якщо мета полягає в обчисленні вершинного по-
криття, кожна вершина має вирішити чи належить вона до вершинного по-
криття. У локальній обчислювальній моделі кожна вершина виконує своє
завдання, виходячи з локальної інформації, якщо k менше діаметра графа.
СУБЛІНІЙНЕ (КОНСТАНТНЕ) НАБЛИЖЕННЯ РОЗМІРУ
МІНІМАЛЬНОГО ВЕРШИННОГО ПОКРИТТЯ ГРАФУ
У [6] показано зведенiсть вiд локальних розподiлених наближених алго-
ритмiв (distributed algorithms) до сублiнiйних наближених алгоритмів (конс-
тантної складності). Коротко опишемо суть результатів.
Наведемо розподілений алгоритм для мінімального вершинного по-
криття графа. Для ребра e позначимо )(eΓ множину його сусідів та )(ed
розмір ).(eΓ Наведемо випадковий розподілений алгоритм, що знаходить
вершинне покриття розміром не більше ніж у )2( δ+ раз більше від міні-
мального з високою константною ймовірністю.
Алгоритм 1 (розподілене наближення мінімального вершинного по-
криття).
1. Кожне ребро активізує само себе.
2. Для i від 1 до ))/((log δdr Θ= виконати:
a) кожне активоване ребро e вибирає себе з ймовірністю
)(4
1
ed
. Якщо
0)( =ed , то e вибирається з ймовірністю 1;
б) кожні два сусідніх ребра, що були вибрані, відміняють свій вибір;
в) кожна вершина інцидентна вибраному ребру додає себе до вершин-
ного покриття;
г) вибрані ребра і сусіди вибраних ребер дезактивують себе;
д) активні ребра оновлюють свої степені, щоб вони були рівні числу
своїх активних сусідів.
3. Одна вершина кожного раніше активованого ребра додає себе до вер-
шинного покриття.
Має місце наступне твердження.
Теорема 1 [6]. Для довільного 0>δ та кожного графа ),( EVG =
з максимальною степінню d алгоритм 1 знаходить вершинне покриття
VC ⊆ таке, що з ймовірністю не меншою ніж 5/6 ≤≤ CVCG ||
||)2( GVCδ+≤ . При цьому складність алгоритму є .))/(log( δdOd
Алгоритм 2 (сублінійне наближення для GVC ).
1. Рівномірно і незалежно генерується 2/4 δ=s вершин графа .G Не-
хай S множина цих вершин.
Сублінійний оптимальний наближений алгоритм реоптимізації для задачі …
Системні дослідження та інформаційні технології, 2013, № 1 83
2. Для кожного Sv∈ розглядається підграф )(vGr індукований
)1( +r -сусідством ,v де ,log ⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛Θ=
δ
dr як в алгоритмі 1.
3. Для )(vG
Sv r∪ ∈
застосовується алгоритм 1 (у послідовному поряд-
ку). Для кожного Sv∈ нехай ,1=vχ якщо алгоритм додає v до покриття,
інакше — .0=vχ
4. Виведення .∑ ∈
= Sv vs
nVC χ
Встановлено такий результат.
Теорема 2 [6]. Для довільного 0>δ та кожного графу G алгоритм 2
виводить із ймовірністю не меншою ніж 2/3 оцінку ,VC що задовольняє
nVCVCnVC GG δδ +⋅≤≤− ||2|| .
Складність алгоритму є .))/(log( δdOd
Таким чином, алгоритм 2 є ),2( δ -наближеним алгоритмом для Min-
Vertex-Cover.
У [7] встановлено таку нижню оцiнку якостi наближення.
Теорема 3 [7]. Для довiльних двох даних констант γ та ε знайдеться
константа d така, що визначення з константною ймовiрнiстю ),2( εγ− -
наближення мiнiмального вершинного покриття графа з n вершинами сту-
пенi d вимагає )(nΩ запитiв.
З теореми 3 випливає, що не iснує β -наближеного сублiнiйного алго-
ритму (з константною складнiстю) для задачi Min-Vertex-Cover із вiдношен-
ням апроксимацiї β строго меншим 2. З врахуванням означення 2 отримає-
мо твердження.
Наслiдок 1. Для задачi Min-Vertex-Cover iснує оптимальний 2-набли-
жений алгоритм із адитивною помилкою з константною складнiстю.
ПОРІГ ВІДНОШЕННЯ АПРОКСИМАЦІЇ НАБЛИЖЕНОГО АЛГОРИТМУ
З КОНСТАНТНОЮ СКЛАДНІСТЮ ДЛЯ РЕОПТИМІЗАЦІЇ
MIN-VERTEX-COVER
Приведемо реоптимізаційний варіант для задачі Min-Vertex-Cover. Нехай
),( EVGI == — довільний екземпляр задачі Min-Vertex-Cover, екземпляр
)','('' EVGI == отримується з I добавленням довільної вершини newv
( }{' newvVV ∪= ), з деякою множиною ребер }{ newe інцидентних newv
( }{' neweEE ∪= ). Через )(vN будемо позначати множину всіх сусідніх
вершин вершини .Vv∈
Задача Ins-Min-Vertex-Cover. Вхідні дані. Екземпляр I задачі Min-
Vertex-Cover, оптимальний розв’язок GVC екземпляра .I
В.О. Михайлюк
ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 84
Результат. Використовуючи GVC , знайти оптимальний розв’язок *
GVC ′
екземпляра ,I ′ описаного вище.
Мета. Мінімізувати число вершин у вершинному покритті .GI ′=′
Теорема 4. Якщо для задачi Min-Vertex-Cover існує ),( δρ -наближений
алгоритм із константною складністю, то для задачі Ins-Min-Vertex-Cover
(реоптимізація Min-Vertex-Cover) існує )),(( 1δρϕ -наближений алгоритм
із константною складністю, де ρρϕ /12)( −= , а ./1 ρδδ =
Доведення. Якщо *
'GVC містить newv , то }{ newvVCG ∪ оптимальний
розв’язок .I ′
Нехай *
'GVC не містить newv . Щоб бути допустимим, *
GVC ′ має містити
всі сусідні вершини )( newvN і, отже, )( newvNVCG ∪ — допустимий
розв’язок .I ′ Оскільки |||| *
GG VCVC ′≤ , то
)(||)( new
*
new vNVCvNVC GG +≤∪ ′ . (1)
Побудуємо ще один допустимий розв’язок :1VC
а) видалимо newv і всі сусідні вершини ;)( newvN
б) застосуємо ),( δρ -наближений алгоритм із константною складністю
до вершин, що залишилися;
в) добавимо вершини .)( newvN
У результаті отримаємо:
=++−≤ ′ |)(||))(|||(|| newnew
*1 vNnvNVCVC G δρ
.|)(|)1(|| new
* nvNVCG δρρ +−−= ′ (2)
Помножимо (1) на 1−ρ та складаючи з (2), отримаємо:
+−+−≤+∪− )()1(||)1(||)()1( new
*
'
1
new vNVCVCvNVC GG ρρρ
nVCnvNVC GG δρδρρ +−=+−−+ ||)12()()1(|| *
'new
*
' .
Звідси .||)12(|}|,)({min)11( *
'
1 nVCVCvNVC GnewG δρρ +−≤∪+−
З розв’язків )( newvNVCG ∪ та 1VC виберемо кращий, тобто з меншим
числом елементів і позначимо його VC . Остаточно отримаємо
nVCVC G ρ
δ
ρ
ρ
+
−
≤ ′ ||12|| * або nVCVC G 1
*
' ||)(|| δρϕ +≤ , де ρρϕ /12)( −= ,
а ./1 ρδδ = Таким чином, для для задачі Ins-Min-Vertex-Cover отримали
)),(( 1δρϕ -наближений алгоритм із константною складністю.
Наслiдок 2. Для задачі Ins-Min-Vertex-Cover існує (3/2)-наближений
алгоритм із адитивною помилкою з константною складнiстю.
Сублінійний оптимальний наближений алгоритм реоптимізації для задачі …
Системні дослідження та інформаційні технології, 2013, № 1 85
Доведення. Згідно з теоремою 2 (або із наслідком 1) треба покласти в
умовах теореми 4 2=ρ і застосувати в доведенні алгоритм 2 в п. б).
Теорема 5. Нехай A — будь-який γ -наближений алгоритм із адитив-
ною помилкою з константною складністю для задачі Ins-Min-Vertex-Cover,
тоді .2/3≥γ
Доведення. Згідно з теоремою 4, маючи ),( δρ -наближений алгоритм із
константною складністю для задачi Min-Vertex-Cover, отримаємо
)),(( 1δρϕ -наближений алгоритм із константною складністю для задачі
Ins-Min-Vertex-Cover, де ρρϕ /12)( −= , а ./1 ρδδ = Отже маємо
)(ρϕ -наближений алгоритм із адитивною помилкою з константною склад-
ністю для задачі Ins-Min-Vertex-Cover. Доведення теореми проведемо від
супротивного. Нехай ).2(2/3)( ϕρϕγ =<= Оскільки функція )(ρϕ є зрос-
таючою функцією свого аргументу, звідси будемо мати 2<ρ . Таким чи-
ном, у теоремі 4 застосовувався ρ -наближений алгоритм із константною
складністю при 2<ρ , що суперечить теоремі 3 (та наслідку 1).
Теорема 6. Для задачi Ins-Min-Vertex-Cover iснує оптимальний (3/2)-
наближений алгоритм із адитивною помилкою з константною складнiстю.
Доведення слідує з теорем 4 та 5.
Зауваження. Вiдмiтимо, що якiсть наближення алгоритму з теореми 6
краща (менша) нiж якiсть наближення (2) оригiнального алгоритма задачi
Min-Vertex-Cover.
ВИСНОВКИ
Як правило знаходження порогових значень відношень апроксимації (зок-
рема нижніх оцінок) наближених алгоритмів розв’язування дискретних
задач оптимізації здійснюється за допомогою деяких загально прийнятих
гіпотез теоретичної інформатики. Наприклад, завдяки гіпотезі співвідношення
класів складності задач по включенню )( NPP ≠ вдалося отримати порогові
значення апроксимації для наближених алгоритмів широкого класу задач
про узагальнену виконуваність [8]. Завдяки унікальній ігровій гіпотезі
(Unique Games Conjecture, UGC) вдалося розповсюдити ці результати на ін-
ші класи задач (наприклад, Max Cut) [9,10]. Подібні результати (отримання
нижніх оцінок відношення апроксимації завдяки використанню гіпотез) на-
зивають результатами по умовній неапроксимованості. У цій роботі наведе-
но приклад результатів з безумовної неапроксимованості для реоптимізації
задачі про мінімальне вершинне покриття графа.
ЛІТЕРАТУРА
1. Goldreich O., Goldwasser S., Ron D. Property testing and its connection to learning
and approximation // Journal of the ACM. — 1998. — 45(4). — P. 653–750.
2. Goldreich O., Ron D. Property testing in bounded degree graphs // Algorithmica. —
1997. — 32(2). — P. 302–343.
В.О. Михайлюк
ISSN 1681–6048 System Research & Information Technologies, 2013, № 1 86
3. Bogdanov A., Obata Kenji, Trevisan L. A lower bound for testing 3-colorability in
bounded-degree graphs // In Proceedings of the Forty-Third Annual Symposium
on Foundations of Computer Science. — 2002. — P. 93–102.
4. Archetti C., Bertazzi L., Speranza M.G. Reoptimizing the traveling salesman prob-
lem // Networks. — 2003. — 42 (3). — P. 154–159.
5. Михайлюк В.А., Сергиенко И.В. Реоптимизация обобщенных проблем о выпол-
нимости с аппроксимационно-устойчивыми предикатами // Кибернетика
и системый анализ. — 2012. — 48, № 1. — С. 89–104.
6. Marko S., Ron D. Distance approximation in bounded-degree and general sparse
graphs // In Proceedings of the Tenth International Workshop on Randomization
and Computation (APPROX-RANDOM). Lecture Notes in Computer Sci-
ence. — 2006. — 4110. — P. 475–486
7. Parnas M., Ron D. Approximating the minimum vertex cover in sublinear time
and a connection to distributed algorithms // Theoretical Computer Science. —
2007. — 381(1–3). — P.183–196.
8. Hastad J. Some optimal inapproximability results // Journal of the ACM. —
2001. — 48, № 4. — P. 798–859.
9. Khot S., KIndler G., Mossel E., O’Donnell R. Optimal Inapproximability Results for
Max-Cut and Other 2-Variable CSPs? // In FOCS. — 2004. — P.146–154.
10. Khot S. On the Unique Games Conjecture // In Proc. of the 25-th Annual IEEE
Conference on Computational Complexity. — 2010. — P. 99–121.
Поступила 25.05.2012
|
| id | journaliasakpiua-article-57494 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:19:43Z |
| publishDate | 2013 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/ae/e4ea8e525770fa39002e05928b452dae.pdf |
| spelling | journaliasakpiua-article-574942018-03-30T15:12:23Z Sublinear optimal approximate algorithm of reoptimization for minimum vertex cover problem Cублинейный оптимальный приближенный алгоритм реоптимизации для задачи о минимальном вершинном покрытии графа Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа Mikhailyuk, V. О. With the approximate solution of discrete optimization problems such idea arises: is it possible, taking into account the information about the optimal solution of an instance (or close to it), use this information to find the optimal (or close to it) solution of instance problem obtained as a result of minor local modifications of the initial instance. This approach, called reoptimization, allows, for example, in some cases, getting the best quality of approximation (which is defined as the ratio between the value of an approximate solution to the exact ratio and called approximation ratio) in locally modified instances than at initials. If for some tasks approximation ratio can not be improved (e.g. in class of all approximation algorithms with polynomial complexity), the ratio is called the threshold or optimal (algorithm which achieved this ratio is also called the threshold or optimal). The complexity of the algorithms is estimated by the number of hits (queries) to a special oracle. For reoptimization of minimum vertex cover problem (with addition of one vertex and some set of edges) (3/2)-approximation algorithm with additive error and sublinear (constant) complexity is received. It is shown that the approximation ratio of 3/2 is the threshold in the class of algorithms with constant complexity. При приближенном решении дискретных задач оптимизации возникает такая идея: можно ли, исходя из информации об оптимальном решении экземпляра задачи (или близкого к нему), использовать эту информацию для нахождения оптимального (или близкого к нему) решения экземпляра задачи, полученного в результате незначительных локальных модификаций исходного экземпляра. Данный подход, названный реоптимизацией, позволяет, например, в некоторых случаях получить лучшее качество приближения (которое определяется как отношение значения приближенного решения к точному и называется отношением аппроксимации) в локально модифицированных экземплярах, чем в исходных. Если для некоторых оптимизационных задач отношение аппроксимации нельзя улучшить (например, в классе всех приближенных алгоритмов с полиномиальной сложностью), то такое отношение называют пороговым или оптимальным (алгоритм на котором достигается это отношение также называют пороговым или оптимальным). Сложность алгоритмов оценивается количеством обращений (запросов) к специальному оракулу. Для реоптимизации задачи о минимальном вершинном покрытии графа (при добавлении одной вершины и некоторого множества ребер) получен (3/2)-приближенный алгоритм с аддитивной ошибкой с сублинейной (константной) сложностью. Показано, что отношение аппроксимации 3/2 является пороговым в классе алгоритмов с константной сложностью. За наближеного розв’язання дискретних задач оптимізації виникає така iдея: чи можна, виходячи з інформації про оптимальний розв’язок екземпляра задачі (або близького до нього), використовувати цю інформацію для знаходження оптимального (або близького до нього) розв’язку екземпляра задачі, отриманого в результатi незначних локальних модифiкацiй вихiдного екземпляра. Цей пiдхiд, названий реоптимізацією, дозволяє в деяких випадках отримати кращу якiсть наближення (яке визначається як вiдношення значення наближеного розв’язку до точного i називається вiдношенням апроксимацiї) у локально модифiкованих екземплярах, нiж у вихiдних. Якщо для деяких оптимiзацiйних задач вiдношення апроксимацiї не можна покращити (наприклад, у класi всiх наближених алгоритмiв із полiномiальною складнiстю), то таке вiдношення називають пороговим або оптимальним (алгоритм на якому досягається це вiдношення також називають пороговим або оптимальним). Складність алгоритмів оцінюється кількістю звернень (запитів) до спеціального оракулу. Для реоптимізації задачі про мінімальне вершинне покриття графа (за добавлення однієї вершини і деякої множини ребер) отриманий (3/2)-наближений алгоритм із адитивною помилкою з сублінійною (константною) складністю. Показано, що відношення апроксимації 3/2 є пороговим у класі алгоритмів із константною складністю. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2013-03-19 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/57494 System research and information technologies; No. 1 (2013); 79-86 Системные исследования и информационные технологии; № 1 (2013); 79-86 Системні дослідження та інформаційні технології; № 1 (2013); 79-86 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/57494/53778 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Mikhailyuk, V. О. Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа |
| title | Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа |
| title_alt | Sublinear optimal approximate algorithm of reoptimization for minimum vertex cover problem Cублинейный оптимальный приближенный алгоритм реоптимизации для задачи о минимальном вершинном покрытии графа |
| title_full | Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа |
| title_fullStr | Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа |
| title_full_unstemmed | Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа |
| title_short | Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа |
| title_sort | cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа |
| url | https://journal.iasa.kpi.ua/article/view/57494 |
| work_keys_str_mv | AT mikhailyukvo sublinearoptimalapproximatealgorithmofreoptimizationforminimumvertexcoverproblem AT mikhailyukvo cublinejnyjoptimalʹnyjpribližennyjalgoritmreoptimizaciidlâzadačiominimalʹnomveršinnompokrytiigrafa AT mikhailyukvo cublíníjnijoptimalʹnijnabliženijalgoritmreoptimízacíídlâzadačípromínímalʹneveršinnepokrittâgrafa |