Почему коэффициенты дифференциальной аппроксимации недостаточно хорошо изучены по сравнению со стандартными, несмотря на заявленные преимущества?

16

Существует стандартная теория приближений, в которой коэффициент приближения равен вирAОпT (для задач сMяNзадачами),A- значение, возвращаемое некоторым алгоритмомAаОпT- оптимальное значение. И еще одна теории, что издифференциального приближениягде отношение приближенияинфΩ-AΩ-ОпT ,Ω - наихудшее значение допустимого решения для данного случая. В Авторы этой теории утверждают , что она имеет определенные преимущества по сравнению с классическим. Например:

  • он дает тот же коэффициент аппроксимации для таких задач, как минимальное покрытие вершин и максимальный независимый набор, которые, как известно, являются просто различными реализациями одной и той же задачи;
  • это дает одинаковое соотношение для максимальной и минимальной версий одной и той же проблемы. В то же время мы знаем, что в стандартной теории MIN TSP и MAX TSP имеют очень разные соотношения.
  • Он измеряет расстояние не только до оптимального, но и до пессимума Ω . Таким образом, в случае стандартного приближения Vertex Cover говорит, что 2 является лучшей верхней границей. Но важно 2 - это максимальное соотношение между пессимумом и оптимумом. Таким образом, такой алгоритм гарантирует вывод решения с наихудшим значением.

Мой аргумент "за": в асимптотическом анализе мы не учитываем константы и термины низкого порядка (здесь я вспомнил цитату Ави Виджерсона: "Мы успешны, потому что мы используем правильный уровень абстракции"), и это уровень абстракции для сравнения использования ресурсов алгоритмом. Но когда мы изучаем приближение, мы почему-то вводим разницу в тех местах, где мы можем этого избежать.

Мой вопрос

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

Александр бондаренко
источник
2
Я никогда раньше не видел этого понятия и думаю, что оно хотя бы интересно. Очень любопытно за ответы! (хотя истинная причина может быть такой же тривиальной, как «До, я никогда не думал об этом» или «Доказательства становятся сложнее» или «Не могу сравнить это с другими результатами, когда я начинаю»)
Рафаэль

Ответы:

3

Существуют две интерпретации утверждения «алгоритм находит α- приближение задачи P »Aαп :

  1. Проблема является легко решить достаточно хорошо, так как у нас есть алгоритм , который находит хорошее приближение.п
  2. Алгоритм это хорошо , так как он находит хорошее приближение.A

Я думаю, что классическое определение фактора приближения подчеркивает первую интерпретацию. Мы классифицируем проблемы по тому, насколько легко их решить.

Дифференциальный коэффициент аппроксимации, кажется, придает немного больше веса второй интерпретации: мы не хотим «вознаграждать» тривиальные алгоритмы (например, алгоритмы, которые просто выводят пустой набор, или набор всех узлов).

Конечно, оба являются действительными точками зрения, но они являются разными точками зрения.


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

  • Оболочка вершины: узлы - это компьютеры, а ребра - каналы связи; мы хотим контролировать все каналы связи и, следовательно, по крайней мере, одна конечная точка каждого ребра должна запускать специальный процесс.

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

Теперь обе задачи имеют тривиальное решение: множество всех узлов является покрытием вершин, а пустое множество - независимым множеством.

Основное отличие состоит в том, что с проблемой покрытия вершин тривиальное решение выполняет свою работу . Конечно, мы используем больше ресурсов, чем необходимо, но, по крайней мере, у нас есть решение, которое мы можем использовать на практике. Однако в случае задачи с независимым множеством тривиальное решение совершенно бесполезно . Мы не делаем никакого прогресса вообще. Никто ничего не делает. Задача никогда не завершена.

Кроме того , мы можем сравнить почти тривиальные решения: вершина крышка , которая состоит из концов паросочетания максимального и независимое множество I , которое является дополнением C . Опять же, C, безусловно, выполняет свою работу в нашем приложении, и на этот раз мы не тратим ресурсы более чем на два фактора. Однако яСяССя мог бы снова быть пустым набором, который совершенно бесполезен.

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

В некотором смысле коэффициент дифференциальной аппроксимации пытается измерить «насколько нетривиальным» является решение, но имеет ли это значение в любом из этих приложений? (Это имеет значение в любом приложении?)

Юкка Суомела
источник
Я не понимаю вашу точку зрения во второй части. Любой переизбирающий выбор вершин является возможным покрытием вершин, нам не нужно знать, что алгоритм является 2-аппроксимацией для этого. С другой стороны, даже 2-приближение для независимого множества вполне может привести к неосуществимому решению. Таким образом, представляется, что опасность невозможности связана с проблемой, а не с (не) известными границами аппроксимации.
Рафаэль
@Raphael: 2-аппроксимация максимального независимого набора, по определению, является независимым набором (и довольно большим; конечно, не пустым набором).
Юкка Суомела
Не бери в голову, читай слишком быстро. Но все же, я думаю, что ваша точка зрения должна быть сформулирована так: алгоритм без гарантии приближения выполняет работу в случае VC, но не в IS. (Вы сравниваете яблоки и груши, не так ли?) Но как же это исследование связано с выбором гарантии? Любой из них будет делать, чтобы получить возможные решения.
Рафаэль
@ Рафаэль: Нет, я говорю, что тривиальный VC имеет гарантию конечного приближения (что-то вроде ), и он выполняет свою работу, в то время как тривиальный IS не имеет гарантии конечного приближения, и он не получает работа сделана Следовательно, аппроксимативные гарантии говорят хотя бы что-то о том, насколько полезно решение. O(Δ)
Юкка Суомела
1
+1 потому что примеры это весело. Я не думаю, что есть четкое различие между «проблема проста» и «есть хороший алгоритм», но я вроде понимаю это на неопределенном уровне.
Tsuyoshi Ito
3

Я не знаком с понятием дифференциальной аппроксимации, и у меня нет какой-либо теории, почему она недостаточно изучена. Однако я хотел бы отметить, что не всегда желательно описывать эффективность алгоритма аппроксимации с помощью одной меры. В этом смысле мне трудно согласиться с тем, что какая-то мера лучше одна другой.

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

Обратите внимание, что мы не всегда используем коэффициент аппроксимации для описания производительности алгоритмов аппроксимации. Например, чтобы сформулировать результат неприемлемости, основанный на теореме PCP, в его полной общности, нам нужна формулировка, основанная на проблемах пропусков. Смотрите мой ответ на другой вопрос для деталей. В этом случае ни использование стандартного отношения аппроксимации, ни использование дифференциального отношения аппроксимации не позволяют нам сформулировать результат в полной общности.

Цуёси Ито
источник
02ОпTN/2
@ Александр: «В случае покрытия вершины, хотя аппроксимация совпадает с наихудшим решением, когда OPT /n / 2, мы имеем соотношение 2.» Считаете ли вы это недостатком или нет, это точка зрения. Можно утверждать, что если каждое решение имеет объективное значение с коэффициентом 2, то не имеет большого значения, какое решение выдает алгоритм. Стандартный коэффициент аппроксимации моделирует ситуацию следующим образом.
Цуёси Ито
Если этот коэффициент 2 или любой другой небольшой фактор является худшим решением, то такой результат будет бесполезным.
Александр Бондаренко
1
@ Александр: Как я уже сказал, это точка зрения.
Цуёси Ито
3

Как указывает Цуёси, проблема может заключаться в том, какой аргумент вы хотите использовать полученную границу. Далее я попытаюсь развить две разные мотивации.

αзнак равноAОпT

αзнак равноΩ-AΩ-ОпTα100%

Таким образом, в зависимости от того, к какому утверждению относится производная граница, вы должны выбрать правильную альтернативу.

[Ω,ОпT]

Рафаэль
источник