|
Дискретный анализ и исследование операций, 2008, том 15, выпуск 1, страницы 44–57
(Mi da521)
|
|
|
|
Оценки погрешности жадных алгоритмов для задач на наследственных системах
В. П. Ильев Омский государственный университет им. Ф. М. Достоевского
Аннотация:
Исследуются задачи максимизации и минимизации аддитивных функций на наследственных системах, которые являются обобщениями многих сложных в вычислительном отношении задач комбинаторной оптимизации. Доказана оценка погрешности жадного алгоритма в терминах параметров допустимой области и целевой функции задачи максимизации, уточняющая известную оценку Дженкинса–Корте–Хаусмана. Аналогичный результат получен для задачи минимизации аддитивной функции на наследственной системе. Библ. 6.
Статья поступила: 30.10.2007
Образец цитирования:
В. П. Ильев, “Оценки погрешности жадных алгоритмов для задач на наследственных системах”, Дискретн. анализ и исслед. опер., 15:1 (2008), 44–57; J. Appl. Industr. Math., 3:1 (2009), 68–77
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da521 https://www.mathnet.ru/rus/da/v15/i1/p44
|
Статистика просмотров: |
Страница аннотации: | 300 | PDF полного текста: | 114 | Список литературы: | 38 | Первая страница: | 1 |
|