Онлайн бин упаковка
Задача Online Bin-Packing - это вариант задачи о ранце. Нам дается неограниченное количество лотков, каждый из которых имеет размер 1. Мы получаем последовательность элементов один за другим (каждый размером не более 1), и должны размещать их в лотках по мере их поступления. Наша цель состоит в том, чтобы минимизировать количество корзин, которые мы используем, при условии, что ни одна корзина не должна быть заполнена больше, чем ее вместимость. В этом вопросе мы рассмотрим простой онлайн-алгоритм для этой задачи, который называется First-Fit (FF). FF упорядочивает корзины произвольно и помещает каждый элемент в первый контейнер, в котором достаточно места для хранения элемента.
(а) Показать, что FF не обеспечивает конкурентное соотношение лучше, чем 3/2.
(б) Докажите, что FF имеет конкурентное отношение не более 2.
a) отношение лучше, чем 3/2 => нет такой входной последовательности. st OBP Solution хуже в 1,5 раза, чем OPT Solution.
Предположим, что последовательная [0,5, 0,2, 0,8, 0,5] оперативная упаковка для бункеров позволяет получить 3 бункера с оптимальным решением 0,7, 0,8, 0,5: 1, 1
=> соотношение не может быть лучше 3/2
б) К сожалению, у меня нет подходов здесь, идея может заключаться в том, чтобы уменьшить проблему до соответствия.... редактировать: лучше нет!
Редактировать: Я утверждаю: у нас есть не более одного бина с заполненным меньше или равным 1/2 Доказательство: Если бы у нас были бина a и бина b с обоим значением <= 1/2, значение второго было бы добавлено к первый.
II Утверждение: оптимальное количество бинов ограничено нижним пределом ceil(сумма (значения)) Доказательство: в оптимальном решении каждый бин заполнен до 1, поэтому для суммы х нам нужно х + 1 бинов
III Утверждение: оптимальное количество бинов ограничено верхним числом n количеством элементов. Доказательство: каждому элементу со значением> 1/2 требуется один контейнер.
Таким образом, для онлайн-алгоритма необходимо, чтобы каждое значение равнялось максимум 2 бинам (I). =>
ONLINE <= 2 * OPT
Правильно ли мое предположение?