Алгоритмы для набора упаковки

Похоже, что для некоторых задач NP-Hard много работы по разработке быстрых экспоненциальных алгоритмов с точным временем (т. Е. Результатов вида: Алгоритм A решает задачу за время O (c ^ n), причем c мало). Похоже, что для решения некоторых сложных задач (например, « Измерить и победить»: простой алгоритм независимых множеств. SODA'06 ) проделана большая работа в этом направлении, но я не был удалось найти аналогичную работу для поставленной задачи упаковки. Похоже, что есть аналогичная работа над некоторыми ограничениями проблемы упаковки множеств (например, параметризованный алгоритм для упаковки с 3 наборами), но я не нашел ни одного для общей упаковки множеств. проблема.$x$$O(2^{0.288n})$$O^{*}(3.523^{k})$

Итак, мой вопрос: какова лучшая временная сложность для точного решения проблемы упаковки взвешенных множеств, где есть множеств, взятых из юниверса из элементов?$m$$n$

Меня также интересует связь между количеством наборов и размером вселенной. Например, была ли алгоритмическая работа в ситуациях, когда относительно велико по сравнению с (т. Е. Близко к )?$m$$n$$2^n$

$O(m2^n)$$[n]$$M$$O(M2^n)$$m$$2^n$

http://dx.doi.org/10.1137/070683933

$3$

http://arxiv.org/abs/1007.1161

за современный алгоритм и список предыдущих результатов по проблеме.

$O(2^{0.288n})$