Об онлайновых алгоритмах для задач упаковки в контейнеры и полосы, их анализе в худшем случае и в среднем

В работе рассмоторены онлайновые алгоритмы для классических задач упаковки Bin Packing и Strip Packing и их обобщений: задач Multidimensional Bin Packing, Multiple Strip Packing и задаче об упаковке в полосы различной ширины. Для последней задачи описан анализ в худшем случае; для остальных задач приведен как анализ в худшем случае, так и анализ в среднем (вероятностный анализ). Рассмотрены лучшие известные нижние и верхние оценки. Приведены основные алгоритмы и описаны методы их анализа.