Книга посвящена вопросам алгоритмического анализа ряда актуальных комбинаторных задач, заданных на различных подмножествах симметрической группы перестановок и являющихся обобщениями классических задачи коммивояжера (TSP) и задачи об оптимальной маршрутизации транспорта (VRP).
В большинстве своем рассматриваемые в книге комбинаторные задачи NР-трудны и слабо аппроксимируемы в общей постановке, однако обладают эффективными приближенными и даже асимптотически точными алгоритмами при некоторых дополнительных ограничениях.
В работа обсуждаются как известные, так и совсем недавние результаты, полученные в области проектирования, обоснования и реализации полиномиальных приближенных алгоритмов с гарантированными оценками точности, рандомизированных асимптотически точных алгоритмов и полиномиальных приближенных схем для рассматриваемых задач.
Авторы надеются, что книга может оказаться полезной исследователям в области комбинаторной оптимизации, а также аспирантам и студентам, интересующимся вопросами алгоритмического анализа труднорешаемых задач.
