Оптимальные жадные алгоритмы для NP-сложных задач

38

Жадность, из-за отсутствия лучшего слова, это хорошо. Одной из первых алгоритмических парадигм, изучаемых в курсе вводных алгоритмов, является жадный подход . Жадный подход приводит к простым и интуитивно понятным алгоритмам для многих задач в P. Более интересно, что для некоторых NP-трудных задач очевидный и естественный жадный / локальный алгоритм приводит к (доказуемо) оптимальному коэффициенту аппроксимации (при подходящих теоретических предположениях сложности). Классическим примером является проблема Set Cover . Естественный жадный алгоритм дает коэффициент аппроксимации O (ln n), который является оптимальным, если P = NP.

Назовите некоторые естественные жадные / локальные алгоритмы для NP-сложных задач, которые доказуемо оптимальны при подходящих теоретических предположениях сложности.

Шива Кинтали
источник
Суреш (или) Райан, не могли бы вы добавить тег с именем «твердость приближения» и отметить этот вопрос. Я не могу добавить новые теги с моей текущей репутацией :( Кроме того, поскольку длинные теги (> 20 символов) не разрешены, я полагаю, что это должна быть приблизительная твердость.
Шива Кинтали
Привет, Шива, я добавил тэг твердости приближения, как ты и предлагал, но лично я считаю, что твердость аппроксимации звучит лучше и должна быть возможной, поскольку она короче алгоритмов приближения.
Каве
6
Красиво выбранное первое предложение. ;)
AlcubierreDrive

Ответы:

19

Метод условных ожиданий (для дерандомизации алгоритмов «случайного назначения» для Max-Cut и Max-SAT) можно рассматривать как жадную стратегию: для вы выбираете значение переменной x i, например что ожидаемое количество ограничений, удовлетворяющих в результирующем уменьшенном экземпляре, превышает ожидаемое количество ограничений, удовлетворяемых в текущем экземпляре. (На самом деле, жадный алгоритм для 1 / 2- аппроксимации Max-Cut такой же, как алгоритм «метода условных ожиданий» для 1 / 2- аппроксимации Max-Cut.)i=1,,nxi1/21/2

Поскольку метод также работает для Max-E3-SAT и достигает -аппроксимации, это пример жадного алгоритма , который является оптимальным приближением , если P = N P (ср Hastad и Moshkovitz-Рац результатов inapproximability для Max -E3-сБ).7/8P=NP

Райан Уильямс
источник
16

Покрытие вершин: лучший алгоритм аппроксимации постоянным множителем включает (жадно) поиск максимального соответствия и выбор всех задействованных вершин в качестве приближенного решения. Это дает 2-приближенное решение, и лучшая аппроксимация с постоянным коэффициентом невозможна, если гипотеза об уникальных играх не ложна.

Субхаш Хот и Одед Регев, Покрытие вершин может быть трудно приблизить с точностью до 2-ε , JCSS 74 (3), 2008.

Не по теме: я думаю, что это действительно симпатичный алгоритм аппроксимации, тем более что он очень простой с точки зрения задним числом.

gphilip
источник
1
алгоритм максимального соответствия действительно жадный?
Суреш Венкат
Да, так как это делает локально оптимальный выбор на каждом этапе. Алгоритм фактически делает локальный / выполнимый / выбор, но поскольку ребра не взвешены, это также оптимальный выбор.
gphilip
11

По заданному графу найдите ациклический подграф с максимальным числом ребер.

Тривиальный алгоритм 2-аппроксимации: выберите произвольный порядок вершин и возьмите либо передние ребра, либо задние ребра.

Известно, что победить в 2-аппроксимации сложно в уникальных играх (хотя это может быть и не NP-сложная игра).

  • Сложно победить случайный порядок: неприемлемость максимального ациклического подграфа Венкатесан Гурусвами, Раджсекар Манокаран и Прасад Рагхавендра.
Jagadish
источник
11

Субмодульная максимизация с учетом ограничения мощности имеет жадное приближение 1-1 / e. Алгоритм принадлежит Немхаузеру, Волси, Фишеру. Твердость NP следует из np-твердости установленного покрытия, так как максимальное покрытие является частным случаем субмодульной максимизации.

Ашвинкумар Б.В.
источник
1
Анализ Жадного алгоритма, предложенный Nemhauser-Wolsey-Fisher, предназначен только для случая максимизации с учетом простого ограничения мощности. Жадные дает только -аппроксимации даже для простого раздела матроиды. ( 1 - 1 / е ) -аппроксимация для максимизации субмодулярных функции при произвольной матроиду является недавний результат за счет Вондрак и других ( в том числе и сам). Он опирается на несколько инструментов и не является жадным алгоритмом. 1/2(11/e)
Чандра Чекури
Конечно, моя ошибка. Отредактировал ответ, чтобы отразить исправление.
Ashwinkumar BV
10

Жадность дает приближение (1-1 / e) к Max-k-cover, и это нельзя улучшить, если P = NP.

Лев Рейзин
источник
Я думаю, что это та же проблема, что и ответ @ AshwinkumarBV, который, я думаю, был опубликован, когда я печатал свой ...
Лев Рейзин
7

Нахождение минимальной степени MST. Это сложно, так как поиск гамильтонова пути - это особый случай. Алгоритм локального поиска дает с точностью до аддитивной постоянной 1.

Ссылка

Аппроксимация дерева Штейнера минимальной степени с точностью до одного из оптимальных

Ашвинкумар Б.В.
источник
6

kG=(V,E)dij0i,jVk

kSV,|S|=kkkkrr

iVS|S|<kjVd(j,S)S|S|=k

2kρρ<2P=NPkk2

Юхо
источник
1

Возможно, это также вас заинтересует (адаптировано из методов для перевода глобальных ограничений в локальные )

Поскольку жадные методы (точнее локальные методы) используют только локальную информацию для достижения глобальной оптимизации, если найдены способы, которые могут преобразовывать глобальные условия в условия, которые можно использовать, используя только локальную информацию, это обеспечивает (глобально) оптимальное решение проблем используя только жадные / локальные методы.

Ссылки:

  1. Думай глобально, подгоняйся локально: неконтролируемое изучение низкоразмерных коллекторов (журнал Machine Learning Research 4 (2003))
  2. Глобальная оптимизация с использованием локальной информации с приложениями для управления потоком, Bartal, Y.
  3. Почему натуральный градиент ?, Амари С., Дуглас С.К.
  4. Локальная оптимизация глобальных задач: конкурентное решение распределенного тупика и распределение ресурсов, Awerbuch, Baruch, Azar, Y.
  5. Обучение с локальной и глобальной последовательностью
  6. Проблемы удовлетворения ограничений, решаемые методами локальной согласованности

Существует несколько ссылок, которые решают проблему перевода глобальных функций оценки (или ограничений) в локальные (с использованием локальной информации) и их согласованности (т.е. сходимости к одному и тому же глобальному оптимуму):

  1. Локальные функции оценки и глобальные функции оценки для вычислительной эволюции, ХАН Цзин, 2003
  2. Выход из локальной функции оценки, Хан Цзин и Цай Циншен, 2002

Аннотация (из 1. выше)

В данной статье представлен новый взгляд на вычислительную эволюцию с точки зрения локальности и глобальности функций оценки для решения классической комбинаторной задачи: проблема kcoloring (проблема решения) и задача минимальной раскраски (задача оптимизации). Сначала мы рассмотрим современные алгоритмы и смоделируем проблему раскраски как многоагентную систему. Затем мы покажем, что существенное различие между традиционными алгоритмами (локальный поиск, например, имитация отжига) и распределенными алгоритмами (такими как модель Alife & AER) заключается в функции оценки: имитация отжига использует глобальную информацию для оценки состояния всей системы, которая называется метод Глобальной функции оценки (ГЭФ); модель Alife & AER использует локальную информацию для оценки состояния одного агента, который называется методом локальной функции оценки (LEF). Мы сравниваем характеристики методов LEF и GEF для решения задач k-раскраски и задач минимальной раскраски. Результаты компьютерных экспериментов показывают, что LEF сопоставим с методами GEF (имитация отжига и жадности), во многих проблемных случаях LEF побеждает методы GEF. В то же время мы анализируем взаимосвязь между ГЭФ и ЛЭФ: последовательность и несогласованность. Теорема согласованности показывает, что равновесия по Нэшу LEF идентична локальным оптимумам GEF, когда LEF согласуется с GEF. Эта теорема частично объясняет, почему LEF может привести систему к глобальной цели. Предлагаются некоторые правила построения согласованного LEF. В дополнение к последовательности,

Specificaly методы бумажных адресов в determnine является ли локальная функцией (LEF) в соответствии с глобальной функцией (ГЭФ) и методой построить последовательный МЭФ из приведенных GEFs ( теорема Консистенции ).

Выдержка из раздела Заключение (из 1. выше)

Эта статья - только начало исследований LEF & GEF. В дополнение к отчету об исследованиях, приведенном выше, предстоит еще много работы: больше экспериментов с методами LEF; аналитическое исследование на LEF; достаточность местной информации для LEF; и наличие согласованного GEF для любого LEF; Достаточно ли концепции согласованности? Поскольку генетические алгоритмы также имеют функцию оценки (фитнес-функцию), можем ли мы применить LEF & GEF к генетическим алгоритмам? … Мы намерены изучить и попытаться ответить на все эти вопросы

Никос М.
источник