Naslov
Solving robust variants of the maximum weighted independent set problem

Autori
Klobučar, Ana

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Mjesto
Zagreb

Datum
16.12

Godina
2019

Stranica
92

Mentor
Robert Manger

Ključne riječi
robust optimization ; maximum weighted independent set problem ; minimum weighted vertex cover ; random graphs ; trees ; evolutionary computing ; algorithms

Sažetak
This work is concerned with robust variants of the maximum weighted independent set problem (MWIS problem). Three basic robustness criteria are used, i.e. absolute robustness, robust deviation and relative robust deviation. More general ordered weighted averaging criteria (OWA) are also considered. Problems are posed in a graph whose vertices are given weights. Uncertainty in vertex weights is expressed through a finite collection of explicitly given scenarios or by intervals. First we explore relationship between robust variants of our problem and robust variants of minimum weighted vertex cover problem (MWVC). In more detail, we explore whether the complement of a robustly optimal independent set must be a robustly optimal vertex cover, and vice-versa (as it is true for conventional optima). It turns out that the answer to this question is not straightforward. More precisely, the answer depends on the chosen criterion of robustness. Further, since solving the conventional MWIS problem is already NP-hard, finding the exact solution of its robust counterpart obviously cannot be any easier. Therefore, we propose an approximate algorithm for solving the considered robust variants, which is based on evolutionary computing and on various crossover and mutation operators. The algorithm is experimentally evaluated on appropriate problem instances. It is shown that satisfactory solutions can be obtained for the mentioned robust robustness criteria in reasonable time. Finally, we explore complexity of our robust variants on trees. It is well known that the conventional MWIS problem can be solved in polynomial time on trees. However, it turns out that almost all robust variants are NP-hard. Hence, we propose an approximative algorithm specially designed for trees which takes into consideration their special structure. More precisely, the algorithm combines good features from dynamic programming, evolutionary computing and greedy decision making. Again, the algorithm is experimentally evaluated on appropriate problem instances. It is shown that satisfactory solutions can be obtained for any of the three basic robustness criteria in reasonable time

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA