Исследуются геометрические свойства задач комбинаторной оптимизации, которые отражают их вычислительную сложность. Приводятся оценки плотности полиэдральных графов задач, которые служат нижней границей временной трудоемкости алгоритмов из широкого класса, включающего большинство известных комбинаторных методов. Изучается аффинная сводимость задач - аналог сводимости в смысле Кука-Карпа. Книга представляет интерес для студентов, аспирантов, научных работников, специализирующихся в области вычислительной математики.
Issledujutsja geometricheskie svojstva zadach kombinatornoj optimizatsii, kotorye otrazhajut ikh vychislitelnuju slozhnost. Privodjatsja otsenki plotnosti poliedralnykh grafov zadach, kotorye sluzhat nizhnej granitsej vremennoj trudoemkosti algoritmov iz shirokogo klassa, vkljuchajuschego bolshinstvo izvestnykh kombinatornykh metodov. Izuchaetsja affinnaja svodimost zadach - analog svodimosti v smysle Kuka-Karpa. Kniga predstavljaet interes dlja studentov, aspirantov, nauchnykh rabotnikov, spetsializirujuschikhsja v oblasti vychislitelnoj matematiki.
