Citeseer/Packing a Knapsack of Unknown Capacity (2014) 10.1.1.744.7611
Мы изучаем проблему упаковки ранца, не зная его вместимости.
Всякий раз, когда мы пытаемся упаковать предмет, который не помещается, этот предмет отбрасывается; если предмет помещается, мы должны включить его в упаковку.
Мы показываем, что всегда существует политика, которая упаковывает ценность в пределах коэффициента 2 от оптимальной упаковки, независимо от фактической вместимости.
Если все предметы имеют единичную плотность, мы достигаем коэффициента, равного золотому сечению φ≈1,618.
Показано, что оба коэффициента являются оптимальными.
Фактически, мы получаем вышеуказанные коэффициенты с помощью упаковочных политик, которые являются универсальными в том смысле, что они фиксируют определенный порядок предметов и пытаются упаковать предметы в этом порядке, независимо от наблюдений, сделанных во время упаковки.
Мы приводим эффективные алгоритмы, вычисляющие эти политики.
С другой стороны, мы показываем, что для любого α > 1 проблема решения вопроса о том, достигает ли данная универсальная политика коэффициента α, является coNP-полной. Если α является частью входных данных, то та же проблема, как показано, является coNP-полной для элементов с единичной плотностью.
Наконец, мы показываем, что для заданного α решить, допускает ли набор предметов универсальную политику с коэффициентом α, даже если все предметы имеют единичную плотность, является coNP-трудной задачей, даже если все элементы имеют единичные плотности.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.