Задачи оптимизации на графах с интервальными параметрами

• Published in: Кибернетика и системный анализ
• Date: 2009
• Main Authors: Перепелица, В.А., Козин, И.В., Максишко, Н.К.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2009
• Subjects: Кибернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/44339
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Задачи оптимизации на графах с интервальными параметрами / В.А. Перепелица, И.В. Козин, Н.К. Максишко // Кибернетика и системный анализ. — 2009. — № 2. — С. 3-14. — Бібліогр.: 19 назв. — рос.

Розглянуто відомі задачі оптимізації на графах в умовах невизначеності, коли область значень параметрів задана у вигляді інтервалів. Обґрунтовано експоненційні оцінки обчислювальної складності досліджуваних задач, а також задач, що в класичній постановці є поліноміальними. Знайдено поліноміально розв’язувані підкласи задач конструктивно обгрунтовано достатні умови статистичної ефективності запропонованого наближеного алгоритму. The well-known optimization problems on graphs are considered under uncertainty, where the parameter domain is given as intervals. Exponential estimates of the computational complexity of the problem under study (and of the problem being polynomial in the classical formulation) are substantiated. Polynomially solvable subclasses are found, the sufficient statistic efficiency conditions of the proposed approximate algorithm are constructively substantiated.