Problem zapiranja centrov
magistrsko delo
Abstract
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.
Keywords
problemi razmeščanja;NP-polnost;aproksimacijski algoritmi;algoritmi na grafih;
Data
| Language: | Slovenian |
|---|---|
| Year of publishing: | 2022 |
| Typology: | 2.09 - Master's Thesis |
| Organization: | UL FRI - Faculty of Computer and Information Science |
| Publisher: | [S. Metličar] |
| UDC: | 004.42 |
| COBISS: |
118522371
|
| Views: | 501 |
| Downloads: | 39 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | English |
|---|---|
| Secondary title: | Center closing problem |
| Secondary abstract: | 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. |
| Secondary keywords: | facility location;NP-completeness;approximation algorithms;graph algorithms; |
| Type (COBISS): | Master's thesis/paper |
| Study programme: | 0 |
| Embargo end date (OpenAIRE): | 1970-01-01 |
| Thesis comment: | Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Računalništvo in matematika - 2. stopnja |
| Pages: | IX, 80 str. |
| ID: | 16225623 |
Recommended works:
Problem zapiranja centrov
2022,
magistrsko delo
2-local distributed algorithms for generalized coloring of hexagonal graphs
2005,
no subtitle data available
Vector connectivity in graphs
2014,
no subtitle data available
Kombinatorična igra filozofov nogomet
2016,
no subtitle data available
Vertex cover at distance on H-free graphs
2021,
no subtitle data available