Является ли сумма подмножества DAG приближенной?

13

Мы дали направленный ациклический граф с номером , связанным с каждой вершиной ( г : V N ), и целевым числом Т N .G=(V,E)g:VNTN

Проблема DAG подмножества суммы (может существовать под другим именем, ссылка будет большой) спрашивает , есть ли вершины , таким образом, что Σ v я г ( v я ) = Т и v 1. , v K представляет собой путь в G .v1,v2,...,vkΣvig(vi)=Tv1..vkG

Эта задача тривиально NP-полная, так как полный транзитивный граф дает классическую задачу о сумме подмножеств.

Алгоритм аппроксимации для задачи о сумме подмножеств DAG представляет собой алгоритм со следующими свойствами:

  1. Если существует путь с суммой T, алгоритм возвращает TRUE.
  2. Если для некоторого c ( 0 , 1 ) нет пути, суммирующего до числа между и T , алгоритм возвращает FALSE.(1c)TTc(0,1)
  3. Если есть путь, суммирующий число между и T , алгоритм может вывести любой ответ.(1c)TT

Известно, что сумма подмножеств аппроксимируется за полиномиальное время для всех .c>0

То же самое относится и к DAG-Subset-Sum?

RB
источник

Ответы:

14

Мне кажется, алгоритм псевдополиномиального динамического программирования для задачи Subset Sum также работает для этой задачи. Для каждой вершины мы вычисляем множество L i, состоящее из всех возможных значений путей, оканчивающихся на v i . Тогда мы имеем рекуррентное соотношение: L i = { g ( v i ) } { x + g ( v i ) x j p r e c ( i ) LviLivi . Следуя топологическому порядку, все L i можно вычислить за время O ( K m ) , где K - общий вес, а m - количество ребер.Li={g(vi)}{x+g(vi)xjprec(i)Lj}LiO(Km)Km

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

Bangye
источник