Жадность, из-за отсутствия лучшего слова, это хорошо. Одной из первых алгоритмических парадигм, изучаемых в курсе вводных алгоритмов, является жадный подход . Жадный подход приводит к простым и интуитивно понятным алгоритмам для многих задач в P. Более интересно, что для некоторых NP-трудных задач очевидный и естественный жадный / локальный алгоритм приводит к (доказуемо) оптимальному коэффициенту аппроксимации (при подходящих теоретических предположениях сложности). Классическим примером является проблема Set Cover . Естественный жадный алгоритм дает коэффициент аппроксимации O (ln n), который является оптимальным, если P = NP.
Назовите некоторые естественные жадные / локальные алгоритмы для NP-сложных задач, которые доказуемо оптимальны при подходящих теоретических предположениях сложности.
Ответы:
Метод условных ожиданий (для дерандомизации алгоритмов «случайного назначения» для Max-Cut и Max-SAT) можно рассматривать как жадную стратегию: для вы выбираете значение переменной x i, например что ожидаемое количество ограничений, удовлетворяющих в результирующем уменьшенном экземпляре, превышает ожидаемое количество ограничений, удовлетворяемых в текущем экземпляре. (На самом деле, жадный алгоритм для 1 / 2- аппроксимации Max-Cut такой же, как алгоритм «метода условных ожиданий» для 1 / 2- аппроксимации Max-Cut.)я = 1 , … , н Икся 1 / 2 1 / 2
Поскольку метод также работает для Max-E3-SAT и достигает -аппроксимации, это пример жадного алгоритма , который является оптимальным приближением , если P = N P (ср Hastad и Moshkovitz-Рац результатов inapproximability для Max -E3-сБ).7 / 8 п= Nп
источник
Покрытие вершин: лучший алгоритм аппроксимации постоянным множителем включает (жадно) поиск максимального соответствия и выбор всех задействованных вершин в качестве приближенного решения. Это дает 2-приближенное решение, и лучшая аппроксимация с постоянным коэффициентом невозможна, если гипотеза об уникальных играх не ложна.
Субхаш Хот и Одед Регев, Покрытие вершин может быть трудно приблизить с точностью до 2-ε , JCSS 74 (3), 2008.
Не по теме: я думаю, что это действительно симпатичный алгоритм аппроксимации, тем более что он очень простой с точки зрения задним числом.
источник
Тривиальный алгоритм 2-аппроксимации: выберите произвольный порядок вершин и возьмите либо передние ребра, либо задние ребра.
Известно, что победить в 2-аппроксимации сложно в уникальных играх (хотя это может быть и не NP-сложная игра).
источник
Субмодульная максимизация с учетом ограничения мощности имеет жадное приближение 1-1 / e. Алгоритм принадлежит Немхаузеру, Волси, Фишеру. Твердость NP следует из np-твердости установленного покрытия, так как максимальное покрытие является частным случаем субмодульной максимизации.
источник
Жадность дает приближение (1-1 / e) к Max-k-cover, и это нельзя улучшить, если P = NP.
источник
Нахождение минимальной степени MST. Это сложно, так как поиск гамильтонова пути - это особый случай. Алгоритм локального поиска дает с точностью до аддитивной постоянной 1.
Ссылка
Аппроксимация дерева Штейнера минимальной степени с точностью до одного из оптимальных
источник
источник
Условная твердость старшинства, ограниченная диспетчеризация на идентичных машинах Ола Свенссон
источник
Возможно, это также вас заинтересует (адаптировано из методов для перевода глобальных ограничений в локальные )
Поскольку жадные методы (точнее локальные методы) используют только локальную информацию для достижения глобальной оптимизации, если найдены способы, которые могут преобразовывать глобальные условия в условия, которые можно использовать, используя только локальную информацию, это обеспечивает (глобально) оптимальное решение проблем используя только жадные / локальные методы.
Ссылки:
Существует несколько ссылок, которые решают проблему перевода глобальных функций оценки (или ограничений) в локальные (с использованием локальной информации) и их согласованности (т.е. сходимости к одному и тому же глобальному оптимуму):
Аннотация (из 1. выше)
Specificaly методы бумажных адресов в determnine является ли локальная функцией (LEF) в соответствии с глобальной функцией (ГЭФ) и методой построить последовательный МЭФ из приведенных GEFs ( теорема Консистенции ).
Выдержка из раздела Заключение (из 1. выше)
источник