* Снова о распределении нагрузки: более сложное применение LP

В этом разделе рассматривается более общая задача распределения нагрузки. Мы разработаем аппроксимирующий алгоритм по той же общей схеме, как и в случае с 2-аппроксимацией, только что разработанной для вершинного покрытия: мы ре- шаем соответствующую задачу линейного программирования, а затем округляем решение.
Впрочем, алгоритм и его анализ будут гораздо более сложными, чем тре- бовалось для вершинного покрытия. Как выясняется, экземпляр задачи линейного программирования, который придется решать, по сути, является задачей потока в сети. Используя этот факт, мы сможем гораздо лучше понять, как выглядят не- целые решения задач линейного программирования, и применить это понимание для правильного округления. Для этой задачи единственный аппроксимирующий алгоритм с постоянным множителем основан на округлении решения задачи ли- нейного программирования.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме * Снова о распределении нагрузки: более сложное применение LP:

  1. Проверка содержательности и достоверности информации является более сложным делом и требует другого аппарата и других методов проверки.
  2. Слова и эмоциональная нагрузка.
  3. Снова к Теме
  4. Снова глагол
  5. От писателя (снова!)
  6. И снова... экстраверты и интроверты
  7. ДИАПАЗОН РАСПРЕДЕЛЕНИЯ
  8. Завистливое зеленоглазое чудовище снова наносит удар
  9. Завистливое зеленоглазое чудовище снова наносит удар
  10. 4.2. Анализ одномерных распределений
  11. Закон нормального распределения
  12. Закон нормального распределения