20.500.12556/RUL-138823 Problem zapiranja centrov magistrsko delo Center closing problem Predmet raziskovanja tega magistrskega dela je problem zapiranja centrov, ki spada med probleme razmeščanja ponudnikov. Predstavljene so osnovne lastnosti ter natančni algoritmi za reševanje problema. Zaradi NP-polnosti so predstavljeni tudi aproksimacijski algoritmi. Empirični testi na različnih omrežjih preverjajo časovno zahtevnost in kakovost rešitev aproksimacijskih algoritmov. Razmerje teh dveh lastnosti je prav tako primerjano. V namen testiranja algoritmov je razvito tudi poštno omrežje Slovenije, cilj katerega je reševanje problema zapiranja poštnih poslovalnic. The main topic of this thesis is the center closing problem, which is a facility location problem. Basic properties and exact algorithms for solving the problem are presented. Because the problem is NP-complete, approximation algorithms are also presented. Time complexity, the quality of results, and the ratio between the two are tested for approximation algorithms using empirical tests. For the purpose of testing the algorithms a postal network of Slovenia was constructed, the goal of which was to solve the post office closing problem. problemi razmeščanja NP-polnost aproksimacijski algoritmi algoritmi na grafih facility location NP-completeness approximation algorithms graph algorithms true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2022-08-20 08:15:01 2022-08-20 08:15:12 2025-09-17 13:19:04 0000-00-00 00:00:00 2022 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004 123889 118522371 4462.pdf 4462.pdf 1 E5A1661A34B58DBFDD4118D610E8F1B1 587fd98a707fdca75242af6729926c1f78d41dd8f3d9a4cc8eae6fd092f2a7d9 706f353e-204f-11ed-92af-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=159286 Fakulteta za matematiko in fiziko Fakulteta za računalništvo in informatiko 0 0 0