NP-твердость частного случая задачи ортогональной упаковки

9

Позволять V быть набором Dпрямоугольные формы. Заd{1,...,D} а также vV, wd(v)Q+ описывает длину v в измерении d, То же обозначение используется для контейнераC, Dзадача об ортогональной упаковке (OPP-D) решить, V помещается в контейнер Cбез перекрытия. Формально говоря, проблема состоит в том, чтобы выяснить,d{1,...,D} существует функция fd:VQ+такой, что vV,fd(v)+wd(v)wd(C) а также v1,v2V, (v1v2), [fd(v1),fd(v1)+wd(v1))[fd(v2),fd(v2)+wd(v2))=,

Задача является NP-полной (см. Fekete SP, Schepers J. "О многомерной упаковке I: моделирование". Технический отчет 97–288, University of zu Köln, 1997). Проблема является NP-полной даже дляD=2, Мне интересно, является ли проблема ортогональной упаковки для ограниченного числа типов (т.е. размеров в каждом измерении) предметов до сих пор NP-полной или нет. До сих пор я нашел результат в какой-то статье о NP-полноте упаковки квадратов в квадрат (см. ДЖОЗЕФ Ю.Т. ЛЕНГ, ТОММИ В. ТАМ И С.С. ВОНГ, «Упаковка квадратов в квадрат», Журнал параллельных и распределенных вычислений, Том 10, выпуск 3, ноябрь 1990 г.), который уже является ограничением, но я до сих пор не знаю, что происходит, когда количество типов элементов ограничено.

Спасибо за ваш ответ,

Петр
источник
3
Можете ли вы указать исходную проблему?
Суреш Венкат
В чем проблема ортогональной упаковки?
Цуёси Ито
2
(1) Я не являюсь экспертом в данной области, но не является ли описание проблемы слишком схематичным, чтобы проанализировать его сложность? (2) Пожалуйста, попробуйте использовать комментарии других людей, чтобы улучшить свой вопрос, отредактировав его, а не добавляя больше комментариев. Большинство людей не хотят следить за обсуждениями в комментариях, просто чтобы понять вопрос.
Цуёси Ито
2
Возможно, попытайтесь точно определить, в чем проблема, отредактировав свой вопрос (нажмите кнопку редактирования выше), и добавьте несколько найденных ссылок. Это поможет сообществу понять, что вы знаете, и что вы хотите знать. Помогите нам помочь вам!
Сянь-Чжи Чанг 之 之
(Мой комментарий и комментарий Сянь-Цзи ссылались на предыдущий комментарий автора, в котором описывается, что такое проблема ортогональной упаковки, которая была удалена позже.)
Цуёси Ито

Ответы:

7

Я думаю, что статья Клауса Янсена и Роберто Солис-Обы « Алгоритм OPT + 1 для решения проблемы режущего материала с постоянным числом длин объекта » частично отвечает на ваш вопрос. Они рассматривают особый случай вашей проблемы, известный как проблема Cutting Stock, когда число различных типов объектов постоянно и определяется следующим образом:

В задаче обрезного материала нам дан наборT={T1,T2,,Td} типов объектов, где объекты типа Ti иметь положительную целую длину pi, Учитывая бесконечный набор бинов, каждый из целочисленной емкостиβпроблема состоит в том, чтобы упаковать набор O из nвозражает против минимально возможного количества бункеров таким образом, чтобы емкость бункеров не превышалась; в комплектеO есть ni объекты типа Ti, для всех i=1,,d,

Авторы утверждают, что

неизвестно, можно ли решить проблему режущего материала за полиномиальное время для каждого фиксированного значения d,

И они предлагают OPT+1 аппроксимационный алгоритм полиномиального времени, когда d фиксированный.

Поскольку не доказано, что этот особый случай Pэто доказательство того, что ваша проблема NP-жесткий.

Приложение: это известно , что в случае с двумя типами объектов (d=2) полиномиально разрешима, но для d=3 там известно только OPT+1-приближение.

Александр бондаренко
источник
Спасибо за ваш ответ. Это не было доказано вP, но ни NP-хард не так ли? В любом случае, как вы сказали, это дает мне частичный ответ и заставляет меня думать, что для OPP-2 он, скорее всего, не изучался.
Петру
Я думаю, вы, вероятно, правы, что ваша проблема не была изучена. Как вы сказали: «Это не было доказано в P, но ни в NP-hard», и я тоже так понимаю.
Александр Бондаренко
2
Может быть, эта проблема может быть добавлена ​​в список проблем "неизвестно, что они в P или NPC".
Сянь-Чжи Чанг 之 之