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

V. О. Mikhailyuk

Анотація


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

Повний текст:

PDF

Посилання


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.

Goldreich O., Ron D. Property testing in bounded degree graphs // Algorithmica. — 1997. — 32(2). — P. 302–343.

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.

Archetti C., Bertazzi L., Speranza M.G. Reoptimizing the traveling salesman problem // Networks. — 2003. — 42 (3). — P. 154–159.

Mikhaylyuk V.А., Sergiyenko I.V. Reoptimizatsiya obobshchennykh problem o vypolnimosti s approksimatsionno-ustoychivymi predikatami // Kibernetika i sistemyy analiz. — 2012. — 48, № 1. — S. 89–104.

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 Science. — 2006. — 4110. — P. 475–486

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.

Hastad J. Some optimal inapproximability results // Journal of the ACM. — 2001. — 48, № 4. — P. 798–859.

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.

Khot S. On the Unique Games Conjecture // In Proc. of the 25-th Annual IEEE Conference on Computational Complexity. — 2010. — P. 99–121.


Пристатейна бібліографія ГОСТ


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.

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 problem // 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 Science. — 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.

 



Посилання

  • Поки немає зовнішніх посилань.