О проблеме труднорешаемости и анализ эвристик в дискретной оптимизации. II

Приводятся результаты качественного анализа основных эвристик, используемых для приближенного решения задач дискретной оптимизации – “жадного” алгоритма и метода локального поиска. Установлена, в частности, неулучшаемость “жадного” алгоритма в классе эвристик, основанных на упорядоченности координат вектора исходных данных.