Citeseer/Packing a Knapsack of Unknown Capacity (2014) 10.1.1.744.7611 — различия между версиями

«Packing a Knapsack of Unknown Capacity (2014) 10.1.1.744.7611»^{скачать}

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

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

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

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

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

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

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

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

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