Search For Maximal Quasi - Triclique Using Mixed Integer Programming

Student: Zamaletdinova Albina

Educational Programme: Mathematical Methods of Optimization and Stochastics (Master)

Year of Graduation: 2018

The problem of finding a maximum gamma-quasi-triclique is considered. Given a tripartite undirected graph and a constant gamma, gamma from 0 to 1, a subset of vertices is called a gamma-quasi-triclique if vertex induced subgraph has dnsity at least gamma for a fixed gamma. gamma-quasi-triclique can be countered as a relaxaion of a well-known triclique concept for gamma = 1. This problem is NP-hard. In this work a maximum gamma-quasi-triclique greedy algorithm was developed and tested. Also this problem was formulated in the context of mixed integer programming and solved using IMB CPLEX software. The results of two different approaches were compared on several realworld datasets. While greedy algorithm finds optimal gamma-quasi-triclique in a shorter time, the size of the triclique is always smaller than the one found by the mixed integer programming approach.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses