За наближеного розв'язання дискретних задач оптимізації виникає така ідея: чи можна, виходячи з інформації про оптимальний розв'язок екземпляра задачі (або близького до нього), використовувати цю інформацію для знаходження оптимального (або близького до нього) розв'язку екземпляра задачі, одержаного в результаті незначних локальних модифікацій вихідного екземпляра. Цей підхід, названий реоптимізацією, дозволяє в деяких випадках одержати кращу якість наближення (яке визначається як відношення значення наближеного розв'язку до точного і називається відношенням апроксимації) у локально модифікованих екземплярах, ніж у вихідних. Якщо для деяких оптимізаційних задач відношення апроксимації не можна покращити (наприклад, у класі всіх наближених алгоритмів із поліноміальною складністю), то таке відношення називають пороговим або оптимальним (алгоритм на якому досягається це відношення також називають пороговим або оптимальним). Складність алгоритмів оцінено кількістю звернень (запитів) до спеціального оракулу. Для реоптимізації задачі про мінімальне вершинне покриття графа (за добавлення однієї вершини і деякої множини ребер) одержаний (3/2)-наближений алгоритм із адитивною помилкою з сублінійною (константною) складністю. Показано, що відношення апроксимації 3/2 є пороговим у класі алгоритмів із константною складністю.

  Повний текст PDF - 325.675 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"