Локальные аппроксимации задач об упаковке и покрытии: различия между версиями

Первые алгоритмы для решения задач линейного программирования о покрытии и упаковке общего вида были предложены в [1, 10]. В [1] было показано, что можно найти решение, которое не более чем на коэффициент <math>1 + \varepsilon</math> отличается от оптимального, за <math>O(log^3(\rho n) / \varepsilon^3)</math> раундов, где <math>\rho</math> – отношение между наибольшим и наименьшим ненулевым коэффициентами LP. Результат был [1] улучшен и обобщен в [6 , 7], где было доказано следующее положение:

Алгоритм, на котором основывается теорема 1, требует использования только небольших сообщений размером <math>O(log(\rho \Delta))</math> и чрезвычайно простых и эффективных локальных вычислений. Если допустить большие сообщения и более сложные (но все еще полиномиальные) локальные вычисления, то результат теоремы 1 можно улучшить: