Комбинаторная сложность одного класса задачи линейного раскроя

В статье рассмотрена классическая задача одномерной упаковки (1dCSP), которая является NP-трудной. Приведен один из возможных комбинаторных алгоритмов ее решения, основанный на методе ветвей и границ. Оценена сложность представленного алгоритма для одного класса задач, который назван плотным. Выявлены примеры, наиболее трудные для решения комбинаторными алгоритмами. Этот результат согласуется с экспериментальными данными и может быть использован для генерации трудных тестовых задач, а также для прогнозирования времени работы алгоритма.