Дробно-линейные задачи об упаковке и покрытии: различия между версиями

Основным открытым вопросом является дальнейшее сокращение времени выполнения приближенных решений различных дробно-линейных задач. Одно потенциальное направление заключается в улучшении границ для конкретных задач, что было успешно проделано для задачи управления несколькими товарными потоками в серии статей, начатой работой Шарохи и Матулы [8]. Из той же отправной точки вышла серия результатов Григориадиса и Хачияна, независимо разработанных с [ ], начиная с работы [ ], в которой представлен алгоритм с числом вызовов, меньшим чем в теореме 1 на коэффициент log(m£~1)/log m. Значительные усилия были направлены на сокращение зависимости времени выполнения от ширины задачи или на уменьшение самой ширины (см, например, последовательные и параллельные алгоритмы для смешанной задачи упаковки и покрытия в [9]), так что это тоже может быть перспективным направлением для улучшения.

Остается открытой задача из [ ] по разработке схем аппроксимации для модели RAM, использующих только полилогарифмические по длине входных данных точность и работу для общего случая рассматриваемых задач.