Поиск максимальных квази-триклик с помощью смешанного целочисленного программирования

ФИО студента: Замалетдинова Альбина Арслановна

Кампус/факультет: Факультет компьютерных наук

Программа: Математические методы оптимизации и стохастики (Магистратура)

Год защиты: 2018

Рассматривается задача поиска максимальной гамма-квази-триклики в трех- дольном графе. Гамма-квази-триклика - это такой под- граф графа с плотностью не менее, чем гамма для фиксированной гамма, гамма от 0 до 1. Понятие гамма-квази-триклики можно считать релаксацией триклики, которая при гамма = 1 соответствует концепту триклики. Данная задача является NP-сложной. В этой работе для поиска максималь- ной гамма-квази-триклики был разработан и отлажен жадный алгоритм. Также данная задача была сформулирована в терминах смешанного целочисленного программирования и решена с помощью вычилительного пакета CPLEX. За- тем было проведено сравнение результатов двух данных подходов на несколь- ких реальных наборах данных. В результате сравнения было показано, что жадный алгоритм находит клики меньшего размера, но за более оптимальное время,а метод смешанного целочисленного программирования - наоборот.

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Реестр дипломов НИУ ВШЭ