Полиномиальная аппроксимация рюкзака по времени

задачу о рюкзаке можно решить за O(n²V) время, где V = max(v[i], i = 1,..,n) обозначает максимальное значение любого предмета. Если мы «изменим единицы измерения» с помощью параметра округления θ = ε/n * V и рассмотрим измененные значения y[i] = ceil(v[i]/θ), мы получим время выполнения O(n³/ε) для любого фиксированного ε > 0.

В книге Разработка алгоритмов Джона Кляйнберга они заявляют:

Зависимость от желаемой точности ε не является полиномиальной, поскольку время выполнения включает 1/ε, а не log 1/ε.

Во-первых, сама идея термина псевдополином мне не совсем понятна, хотя я читал о нем несколько статей. Однако, помимо этого пробела в знаниях, я в основном спрашиваю себя, почему зависимость от ε будет полиномиальной, если время выполнения будет включать log 1/ε вместо 1/ε.


algorithm knapsack-problem np complexity-theory
person 0xbadf00d    schedule 15.09.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Является ли проблема полиномиальной или нет, зависит от того, как закодированы ее экземпляры. Например, я могу определить задачу PADDED-SATISFIABILITY, допустимые экземпляры которой состоят из логической формулы с n переменными, за которыми следуют 2 ^ n мусорных битов. Благодаря заполнению PADDED-SATISFIABILITY решается за полиномиальное время (в отличие от, предположительно, SATISFIABILITY, которое является NP-трудным).

Когда экземпляры включают целые числа, обычно предполагается кодирование, при котором количество битов, используемых для представления положительного целого числа, составляет примерно log2 этого целого числа. Алгоритм псевдополиномиального времени в этом контексте означает, что, если мы переключаемся с двоичного представления положительных целых чисел на унарное, так что им требуется экспоненциально (!) Больше битов для представления, тогда алгоритм полиномиально-временной.

Если мы сделаем (частое) предположение, что 1 / ε является положительным целым числом, то Клейнберг указывает, что полиномиальная зависимость будет от log 1 / ε, поскольку это приблизительно количество битов, необходимых для указания этого параметра в двоичном формате. Количество битов в унарном представлении будет примерно 1 / ε.

person David Eisenstat    schedule 15.09.2014
comment
log 1/ε - это примерно количество бит, необходимое для хранения 1/ε в двоичном формате. Мне это абсолютно ясно, но почему это проблема? Разве мы не могли бы таким же образом спорить о любом n в O(n^k)? Даже когда n - это просто счетчик цикла, нам нужно сохранить это значение (как правило). Итак, что отличает n от 1/ε? [Более того, зачем нам рассматривать унарное представление любого параметра?] - person 0xbadf00d; 15.09.2014
comment
@ 0xbadf00d Если n - это, скажем, количество элементов в списке, то сами элементы списка занимают линейное количество битов, что делает неактуальным способ представления n. Если n - это просто число (например, для факторинга), то оно обрабатывается так же, как 1/ε. - person David Eisenstat; 15.09.2014
comment
@ 0xbadf00d Причина, по которой следует задуматься об унарных представлениях, заключается в том, что они формально определяют псевдополиномиальное время. Здесь, на Stack Overflow, люди часто спрашивают о вариантах рюкзака; один из комментариев или ответов часто бывает NP-трудным; не повезло тебе. Однако, поскольку рюкзак является NP-трудным лишь слабо, существует алгоритм, который хорошо работает с небольшими целочисленными входами, что очень полезно на практике. С другой стороны, 3-секционный вводить небольшие целые числа не проще. - person David Eisenstat; 15.09.2014