Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа

• Дата: 2013
• Автор: Михайлюк, В.О.
• Формат: Стаття
• Мова: Ukrainian
• Опубліковано: Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2013
• Назва видання: Системні дослідження та інформаційні технології
• Теми: Методи оптимізації, оптимальне управління і теорія ігор
• Онлайн доступ: http://dspace.nbuv.gov.ua/handle/123456789/50019
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Сублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа / В.О. Михайлюк // Систем. дослідж. та інформ. технології. — 2013. — № 1. — С. 79-86. — Бібліогр.: 10 назв. — укр.

За наближеного розв’язання дискретних задач оптимізації виникає така 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 є пороговим у класі алгоритмів із константною складністю.