Анализ алгоритмов дискретной оптимизации, использующих неполную информацию

Рассматриваются задачи дискретной оптимизации с неопределенностью в исходных данных. Вводится понятие $\Sigma$-точного алгоритма – наилучшего в некотором естественном смысле среди всех приближенных алгоритмов, использующих неполную информацию. Выясняется связь между свойствами $\Sigma$-точного алгоритма и принципиальной возможностью построения точного алгоритма. В качестве иллюстрации приводится анализ двух известных эвристических алгоритмов для задачи коммивояжера, лишь один из которых оказывается $\Sigma$-точным.