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

Материал из DISCOPAL
Версия от 06:38, 17 марта 2022; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

«

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

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

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

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

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

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

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

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

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

…»

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

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

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