| Аннотац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дношення називають пороговим або оптимальним (алгоритм на якому досягається це вiдношення також називають пороговим або оптимальним). |
