Порада Складність пріоритетних алгоритмів SpringerLink
Анотація
Пріоритетну модель "жадібних" алгоритмів було представлено Бородіним, Нільсеном та Рацкофом у 2002 році. Ми доповнюємо цю модель, дозволяючи пріоритетним алгоритмам мати доступ до порад, тобто побічної інформації, попередньо обчисленої всемогутнім оракулом. Отримання нижчих меж у пріоритетній моделі без поради може бути складним завданням і може включати складні аргументи суперника. Оскільки пріоритетна модель з порадами ще потужніша, отримання нижчих меж представляє додаткові труднощі. Ми уникаємо цих труднощів, розробляючи загальну систему скорочень, яка робить докази нижньої межі відносно простими та рутинними. Ми починаємо з того, що вводимо проблему відповідності пар, для якої ми можемо довести сильні нижні межі в моделі пріоритетів за допомогою поради. Ми розробляємо шаблон для побудови скорочення від Pair Matching до інших проблем у пріоритетній моделі з порадами - ця частина є технічно складною, оскільки для скорочення потрібно визначити дійсну функцію пріоритету для Pair Matching, дотримуючись функцію пріоритету для іншої проблеми. Нарешті, ми застосовуємо шаблон для отримання нижчих меж для ряду стандартних дискретних задач оптимізації.