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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 21: Строка 21:
 
}}
 
}}
 
{{enddiv}}
 
{{enddiv}}
 +
{{reserve-task|[[Участник:Yakushev|Yakushev]] 13:40, 26 ноября 2021 (UTC)}}
  
 
[[Категория:CiteSeerArticles]]
 
[[Категория:CiteSeerArticles]]

Версия 13:40, 26 ноября 2021

«

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

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

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

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

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

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

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

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

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

…»

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