Динамическое программирование никогда не бывает слабее, чем Greedy?

В сложности схемы у нас есть разделения между степенями различных моделей схемы.

В сложности доказательства мы имеем разделения между степенями различных систем доказательства.

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

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

У нас есть базовый набор элементов, и некоторые семейства его подмножеств объявлены как возможные решения. Мы предполагаем, что это семейство замкнуто вниз: подмножества выполнимого решения возможны. При задании неотрицательных весовых коэффициентов для основных элементов задача состоит в том, чтобы вычислить максимальный общий вес допустимого решения.

Жадный алгоритм начинается с пустого частичного решения и на каждом шаге добавляет еще не обработанный элемент с наибольшим весом, если это возможно, т. Е. Если расширенное решение все еще возможно. Хорошо известная теорема Радо-Эдмондса гласит, что этот алгоритм найдет оптимальное решение для всех входных весов, если семейство возможных решений является матроидом.

Грубо говоря, алгоритм DP прост , если он использует только операции Max и Sum (или Min и Sum). Чтобы быть более конкретным (как предложил Джошуа), под простым алгоритмом DP я буду понимать (max, +) схему с вентилями Fanin-2 Max и Sum. Входные данные являются переменными, $i$ из которых соответствует весу, данному $i$ му элементу. Такая схема может решить любую такую ​​проблему, просто вычисляя максимальный общий вес возможного решения. Но это может быть огромным преувеличением, если у нас экспоненциально много таких решений (как это почти всегда бывает).

Вопрос 1: Существуют ли матроиды, для которых любому простому алгоритму DP потребуется суперполиномиальное число операций для решения соответствующей задачи максимизации?

КОММЕНТАРИЙ (добавлено 24.12.2015): Этот вопрос уже ответил (см ниже): есть есть такие матроиды, даже в подавляющем большинстве.

Следующий вопрос состоит в том, чтобы отделить Greedy от простого DP для задач аппроксимации . В задаче сопоставления с максимальным весом семейство возможных решений состоит из всех сопоставлений в полном двудольном графе $n\times n$ . Для данного присвоения весов его ребрам цель состоит в том, чтобы вычислить максимальный вес сопоставления (это всегда будет идеальное сопоставление, так как вес неотрицателен).

Простой жадный алгоритм может аппроксимировать эту проблему с коэффициентом 2: просто всегда берите невидимый непересекающийся край максимального веса. Полученный вес будет составлять не менее половины оптимального веса.

Вопрос 2: Может ли простой алгоритм DP приблизить задачу согласования максимального веса с множителем 2, используя только полиномиально много операций Max и Sum?

Конечно, тривиальный алгоритм DP, который выводит умноженный на максимальный вес ребра, аппроксимирует эту проблему в пределах коэффициента n . Но мы хотим гораздо меньший фактор. Я думаю, что даже фактор n / log n не может быть достигнут, но, опять же: как это доказать ? $n$$n$$n/\log n$

СВЯЗАННЫЕ: двоюродный брат Макс-Вес соответствия задачей назначения : найдите минимальный вес идеального сопоставления. Эта проблема может быть решена (даже точно) с помощью линейного программирования (так называемый венгерский алгоритм), используя только операций. Но нижняя граница Разборова на размер монотонных логических схем, вычисляющих постоянную функцию, подразумевает (не совсем напрямую), что любая (min, +) схема, аппроксимирующая эту проблему в любом (!) Конечном множителе, должна использовать n Ω ( log n ) операций , Таким образом, для минимизации$O(n^3)$$n^{\Omega(\log n)}$проблемы, простые алгоритмы DP могут быть намного слабее, чем линейное программирование. Мои вопросы выше направлены на то, чтобы показать, что такие алгоритмы DP могут быть даже слабее, чем Greedy.

Кто-нибудь видел подобные вопросы, рассматриваемые кем-то?

---

ДОБАВЛЕНО (24.12.2015): Вопрос 2 направлен на то, чтобы показать, что одна конкретная проблема максимизации (проблема согласования максимального веса), которая может быть аппроксимирована жадным алгоритмом с коэффициентом $r=2$ , не может быть аппроксимирована простым множителем ДП с тем же коэффициентом $r$ . Между тем, я получил более слабое разделение между Greedy и простым DP: для каждого $r=o(n/\log n)$ существует явная проблема максимизации, которая может быть аппроксимирована жадным алгоритмом с фактором $r$ , но без простого DP с полиразмером Алгоритм может приблизить эту проблему с меньшимкоэффициент (см. здесь эскиз). Тем не менее, сам вопрос 2 (не обязательно для этой конкретной проблемы максимального веса) остается актуальным: было бы интересно нацелить один и тот же фактор на оба алгоритма.$< r/3$

Я думаю , что ответ на мой вопрос 1 утвердительный : есть в матроидах , на которых просто DP не удается плохо! То есть простой DP может быть намного хуже, чем Greedy, когда пытается точно решить задачу оптимизации .

$K_n$$K_n$$f$$f$$(\max,+)$

$2^{2^n/n^{3/2}}$$n$

$2$$k$$k$матроиды. С другой стороны, насколько мне известно, алгоритмы аппроксимации, основанные на DP, обычно используют своего рода «масштабирование» входных весов и применяются только к задачам типа «ранца» или к некоторым задачам планирования. Отрицательный ответ на вопрос 2 подтвердил бы эту кажущуюся слабость приближения DP.