Citeseer/Packing a Knapsack of Unknown Capacity (2014) 10.1.1.744.7611

Материал из DISCOPAL
Перейти к: навигация, поиск

«

Мы изучаем проблему упаковки ранца, не зная его вместимости.

Всякий раз, когда мы пытаемся упаковать предмет, который не помещается, этот предмет отбрасывается; если предмет помещается, мы должны включить его в упаковку.

Мы показываем, что всегда существует политика, которая упаковывает ценность в пределах коэффициента 2 от оптимальной упаковки, независимо от фактической вместимости.

Если все предметы имеют единичную плотность, мы достигаем коэффициента, равного золотому сечению φ≈1,618.

Показано, что оба коэффициента являются оптимальными.

Фактически, мы получаем вышеуказанные коэффициенты с помощью упаковочных политик, которые являются универсальными в том смысле, что они фиксируют определенный порядок предметов и пытаются упаковать предметы в этом порядке, независимо от наблюдений, сделанных во время упаковки.

Мы приводим эффективные алгоритмы, вычисляющие эти политики.

С другой стороны, мы показываем, что для любого α > 1 проблема решения вопроса о том, достигает ли данная универсальная политика коэффициента α, является coNP-полной. Если α является частью входных данных, то та же проблема, как показано, является coNP-полной для элементов с единичной плотностью.

Наконец, мы показываем, что для заданного α решить, допускает ли набор предметов универсальную политику с коэффициентом α, даже если все предметы имеют единичную плотность, является coNP-трудной задачей, даже если все элементы имеют единичные плотности.

…»

Задача зарезервирована: Yakushev 13:40, 26 ноября 2021 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.