И.А. Близнец, "Приближенные алгоритмы"
Много естественных оптимизационных задач, включая те, что возникают на практике,
являются NP-трудными. В предположении гипотезы о неравенстве классов P и NP, точные
решения для таких задач требуют значительное количество времени. В связи с этим
возникает большой теоретический и практический интерес к приближенным алгоритмам,
работающих за полиномиальное время, для подобных задач. В курсе мы опишем теорию,
посвященную построению приближенных алгоритмов.
Предположительно курс будет состоять из трех частей. В первой части мы будем рассматривать комбинаторные алгоритмы для целого ряда важных задач (задача о рюкзаке, задача о коммивояжере, задача об упаковке, дерево Штейнера и другие). Вторая часть будет посвящена алгоритмам, основанным на линейном программировании. В заключительной части мы поговорим о сложности приближения для некоторых задач.
