Задачи оптимизации на графах с интервальными параметрами - Перепелица, В.А.; Козин, И.В.; Максишко, Н.К. (Кибернетика и системный анализ, 2009)
Розглянуто відомі задачі оптимізації на графах в умовах невизначеності, коли область значень параметрів задана у вигляді інтервалів. Обґрунтовано експоненційні оцінки обчислювальної складності досліджуваних задач, а також задач, що в класичній постановці є поліноміальними. Знайдено поліноміально розв’язувані підкласи задач конструктивно обгрунтовано достатні умови статистичної ефективності запропонованого наближеного алгоритму.