Научная тема: «ЗАДАЧИ ОПТИМИЗАЦИИ И АППРОКСИМАЦИИ НА НАСЛЕДСТВЕННЫХ СИСТЕМАХ»
Специальность: 01.01.09
Год: 2010
Основные научные положения, сформулированные автором на основании проведенных исследований:
  1. Исследована структура наследственных систем и их частных случаев - коматроидов. Предложены различные аксиоматизации коматроидов. Получена характеризация графов циклов коматроидов и целочисленных полиматроидов.
  2. Дано новое эквивалентное определение наследственной системы в терминах замыкания. Для наследственных систем графов доказан ана­лог теоремы Биркгофа-Уитни о представлении геометрических решеток. Доказана теорема, устанавливающая связь между коматроидами и ре­шетками, двойственными геометрическим.
  3. Получена гарантированная оценка погрешности жадного алгоритма в терминах параметров допустимой области и целевой функции задачи максимизации аддитивной функции на наследственной системе, уточняющая известную оценку Дженкинса-Корте-Хаусмана. Предложена ха-рактеризация класса целевых функций задач на матроидах, разрешимых жадным алгоритмом, и доказано обобщение теоремы Радо-Эдмондса для задачи максимизации функции из этого класса.
  4. Аналогичные оценки доказаны для задачи минимизации аддитив­ной функции на наследственной системе. Как следствие получены оцен­ки погрешности обратного жадного алгоритма для задачи о минималь­ном двусвязном остовном подграфе и задачи о наименьшей раскраске графа. Установлена эквивалентность задачи минимизации аддитивной функции на наследственной системе и задачи о минимальном покрытии множества.
  5. Получены оценки погрешности обратного жадного алгоритма для задачи минимизации невозрастающей супермодулярной функции на ко-матроиде. Как следствие получены оценки погрешности этого алгоритма для общей задачи о pмедиане на минимум. Исследована задача миними­зации неубывающей супермодулярной функции на матроиде, к которой сведена известная задача аппроксимации графа.
  6. Предложена постановка задачи матроидной аппроксимации, част­ным случаем которой является задача аппроксимации графа. Получена оценка аппроксимационной сложности графа для одного варианта зада­чи аппроксимации графа. Доказано, что задача аппроксимации графами с заданным числом компонент связности ЖР-трудна.
  7. Предложены алгоритмы приближенного решения задачи аппрок­симации графа, получены гарантированные оценки погрешности этих алгоритмов. Показано, что жадный алгоритм является гарантированно асимптотически точным алгоритмом аппроксимации неплотных графов. Доказано существование полиномиальной приближенной схемы для од­ного варианта задачи.
Список опубликованных работ
1.[43] Агеев А.А., Ильев В.П., Кононов А.В., Талевнин А.С. Вычислитель¬ная сложность задачи аппроксимации графов // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13, N 1. С. 3-15.

2.[44] Выплов М.Ю., Ильев В.П. О гиперграфах, соответствующих опе¬раторам слабого замыкания // Эл. сб. материалов VIII Междунар. конф. "Дискретные модели в теории управляющих систем". Москва. 2009. С. 30-34.

3.[45] Ильев В.П., Фридман Г.Ш. К задаче аппроксимации графами с фик¬сированным числом компонент // Докл. АН СССР. 1982. Т. 264, N 3. С. 533-538.

4.[46] Ильев В.П., Фридман Г.Ш., Филичкина М.А. Об аппроксимации ориентированных графов графами с фиксированным числом биком-понент // Моделирование и оптимизация структурных систем. Бар¬наул. 1982. С. 54-61.

5.[47] Ильев В.П., Фридман Г.Ш. К задаче аппроксимации трехкомпонент-ными графами // Численные методы и задачи оптимизации. Томск. 1983. С. 80-95.

6.[48] Ильев В.П. О базисных графах полиматроидов // Методы дискрет¬ного анализа в изучении реализаций логических функций. Сб. науч. тр. Новосибирск: Институт математики СО АН СССР. 1984. Вып. 41. С. 35-48.

7.[49] Ильев В.П. Одна задача матроидной аппроксимации // Методы решения и анализа задач дискретной оптимизации. Омск. 1992. С. 42-51.

8.[50] Ильев В.П. Оценка погрешности градиентного алгоритма для систем независимости // Дискрет, анализ и исслед. операций. 1996. Т. 3, N 1. С. 9-22.

9.[51] Ильев В.П. Оценка точности алгоритма жадного спуска для зада¬чи минимизации супермодулярной функции // Дискрет, анализ и исслед. операций. Сер. 1. 1998. Т. 5, N 4. С. 45-60.

10.[52] Ильев В.П., Молдованов И.А. О градиентном алгоритме построе¬ния надежных коммуникационных сетей // Труды ИВМиМГ. Сер. "Информатика". Новосибирск. 1998. С. 60-69.

11.[53] Ильев В.П., Линкер Н.В. К задаче минимизации супермодулярной функции на коматроиде // Вестник Омского университета. 2002. N 1. С. 16-18.

12.[54] Ильев В.П., Талевнин А.С. Две задачи на наследственных систе¬мах // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10, N 3. С. 54-67.

13.[55] Ильев В.П. Оценки погрешности приближенного алгоритма для за¬дачи о раскраске графа // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск-Северобайкальск. 2005. Т. 1. С. 491-495.

14.[56] Ильев В.П. Алгоритмы с оценками для задачи о pмедиане и ее обоб¬щений // Материалы III Всероссийской конф. "Проблемы оптими¬зации и экономические приложения". Омск. 2006. С. 32-36.

15.[57] Ильев В.П. Задачи комбинаторной оптимизации на наследственных системах // Материалы Российской конф. "Дискретная оптимизация и исследование операций". Владивосток. 2007. С. 41-45.

16.[58] Ильев В.П., Навроцкая А.А., Талевнин А.С. Полиномиальная при¬ближенная схема для задачи аппроксимации неплотных графов // Вестник Омского университета. 2007. N 4. С. 24-27.

17.[59] Ильев В.П. Оценки погрешности жадных алгоритмов для задач на наследственных системах // Дискрет, анализ и исслед. операций. 2008. Т. 15, N 1. С. 44-57.

18.[60] Ильев В.П., Ильева С.Д. Оценка погрешности жадного алгоритма для задачи аппроксимации графа // Труды XIV Байкальской меж¬дународной школы-семинара "Методы оптимизации и их приложе¬ния". Иркутск-Северобайкальск. 2008. Т. 1. С. 396-404.

19.[61] Ильев В.П., Ильева С.Д., Навроцкая А.А. Оценки погрешности ал¬горитмов приближенного решения задачи аппроксимации графа // Труды VIII Междунар. конф. "Дискретные модели в теории управ¬ляющих систем". Москва. 2009. С. 120-127.

20.[62] Ильев В.П., Ильева С.Д. Задачи минимизации супермодулярных функций на матроидах и коматроидах // Материалы IV Всероссий¬ской конф. "Проблемы оптимизации и экономические приложения". Омск. 2009. С. 51-55.

21.[63] Ильев В.П., Ильева С.Д. 3-приближенный алгоритм для одного ва¬рианта задачи аппроксимации графа // Вестник Омского универси¬тета, 2009. N 4. С. 77-79.

22.[64] Кукина О.Г., Ильев В.П. Коматроиды и решетки их открытых мно¬жеств // Труды 37-й Региональной молодежной конф. "Пробле¬мы теоретической и прикладной математики". Екатеринбург. 2006. С. 53-57.

23.[65] Кукина О.Г., Ильев В.П. Наследственные системы и решетки // Ма¬териалы IX Междунар. семинара "Дискретная математика и ее при¬ложения". Москва. 2007. С. 228-231.

24.[66] Il´ev V.P., Ofenbakh I.V. Optimization models and algorithms of const¬ructing reliable networks // System Modelling and Optimization. Proc. 18th IFIP TC7 Conf. Detroit. 1997. Research Notes in Mathematics. London: Chapman к Hall/CRC. 1999. V. 396. P. 237-244.

25.[67] Il´ev V.P. An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function // Discrete Appl. Math. 2001. V. 114, N 1-3. P. 131-146.

26.[68] Il´ev V. Hereditary systems and greedy-type algorithms // Discrete Appl. Math. 2003. V. 132, N 1-3. P. 137-148.

27.[69] Il´ev V., Linker N. Steepest descent algorithm for minimizing a super-modular set function on comatroid // Proc. 2nd Intern. Workshop "Discrete Optimization Methods in Production and Logistics". Omsk-Irkutsk. 2004. P. 166-168.

28. Il´ev V., Linker N. Performance guarantees of a greedy algorithm for minimizing a supermodular set function // European J. Oper. Res. 2006. V. 171, N 2. P. 648-660.