Algorithmic Study of Online Multi-Facility Location Problems
Facility location (FL) is a well-known optimization problem that asks to optimally place facilities so as to serve clients at various locations, requesting a facility service, with minimum possible costs. Many variants of FL have been known, appearing as sub-problems in many applications in computer...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| التنسيق: | article |
| منشور في: |
2022
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/17645 https://doi.org/10.1007/s42979-022-01193-y http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/article/10.1007/s42979-022-01193-y |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513475665985536 |
|---|---|
| author | Markarian, Christine |
| author2 | Kassar, Abdul-Nasser Yunis, Manal |
| author2_role | author author |
| author_facet | Markarian, Christine Kassar, Abdul-Nasser Yunis, Manal |
| author_role | author |
| dc.creator.none.fl_str_mv | Markarian, Christine Kassar, Abdul-Nasser Yunis, Manal |
| dc.date.none.fl_str_mv | 2022 2022-05-19 2026-02-12T14:32:08Z 2026-02-12T14:32:08Z |
| dc.identifier.none.fl_str_mv | 2661-8907 http://hdl.handle.net/10725/17645 https://doi.org/10.1007/s42979-022-01193-y Markarian, C., Kassar, A. N., & Yunis, M. (2022). Algorithmic study of online multi-facility location problems. SN computer science, 3(4), 296. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/article/10.1007/s42979-022-01193-y |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | SN Computer Science |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Algorithmic Study of Online Multi-Facility Location Problems |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | Facility location (FL) is a well-known optimization problem that asks to optimally place facilities so as to serve clients at various locations, requesting a facility service, with minimum possible costs. Many variants of FL have been known, appearing as sub-problems in many applications in computer science, management science, and operations research. Most FL models studied thus far assume that clients need to be served by connecting each to one facility. To overcome facility failures and provide a robust solution, we investigate in this paper FL problems that require each client to be connected to multiple facilities, represented by an additional input parameter. The aim of the algorithm is then to provide a robust service to all clients while minimizing the total connecting and facility purchasing costs. This is known as the Multi-Facility Location problem (MFL) and has been studied in the offline setting, in which the entire input sequence is given to the algorithm at once. In this paper, we study MFL in the online setting, in which client requests are not known in advance but are revealed to the algorithm over time. We refer to it as the online multi-facility location problem (OMFL) and study its metric and non-metric variants. We propose the first online algorithms for these variants and measure their performance using the standard notion of competitive analysis. The latter is a worst-case analysis that compares the cost of the online algorithm to that of the optimal offline algorithm that is assumed to know all demands in advance. We further study OMFL in the leasing setting, in which facilities are leased, rather than bought, for different durations and prices, and each arriving client needs to be connected to multiple facilities leased at the time of its arrival. The aim is to minimize the total connecting and facility leasing costs. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_03b5f5cb6cd762d7aafd6a7abccbf1fa |
| identifier_str_mv | 2661-8907 Markarian, C., Kassar, A. N., & Yunis, M. (2022). Algorithmic study of online multi-facility location problems. SN computer science, 3(4), 296. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/17645 |
| publishDate | 2022 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Algorithmic Study of Online Multi-Facility Location ProblemsMarkarian, ChristineKassar, Abdul-NasserYunis, ManalFacility location (FL) is a well-known optimization problem that asks to optimally place facilities so as to serve clients at various locations, requesting a facility service, with minimum possible costs. Many variants of FL have been known, appearing as sub-problems in many applications in computer science, management science, and operations research. Most FL models studied thus far assume that clients need to be served by connecting each to one facility. To overcome facility failures and provide a robust solution, we investigate in this paper FL problems that require each client to be connected to multiple facilities, represented by an additional input parameter. The aim of the algorithm is then to provide a robust service to all clients while minimizing the total connecting and facility purchasing costs. This is known as the Multi-Facility Location problem (MFL) and has been studied in the offline setting, in which the entire input sequence is given to the algorithm at once. In this paper, we study MFL in the online setting, in which client requests are not known in advance but are revealed to the algorithm over time. We refer to it as the online multi-facility location problem (OMFL) and study its metric and non-metric variants. We propose the first online algorithms for these variants and measure their performance using the standard notion of competitive analysis. The latter is a worst-case analysis that compares the cost of the online algorithm to that of the optimal offline algorithm that is assumed to know all demands in advance. We further study OMFL in the leasing setting, in which facilities are leased, rather than bought, for different durations and prices, and each arriving client needs to be connected to multiple facilities leased at the time of its arrival. The aim is to minimize the total connecting and facility leasing costs.Published2026-02-12T14:32:08Z2026-02-12T14:32:08Z20222022-05-19Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article2661-8907http://hdl.handle.net/10725/17645https://doi.org/10.1007/s42979-022-01193-yMarkarian, C., Kassar, A. N., & Yunis, M. (2022). Algorithmic study of online multi-facility location problems. SN computer science, 3(4), 296.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://link.springer.com/article/10.1007/s42979-022-01193-yenSN Computer Scienceinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/176452026-02-17T14:38:00Z |
| spellingShingle | Algorithmic Study of Online Multi-Facility Location Problems Markarian, Christine |
| status_str | publishedVersion |
| title | Algorithmic Study of Online Multi-Facility Location Problems |
| title_full | Algorithmic Study of Online Multi-Facility Location Problems |
| title_fullStr | Algorithmic Study of Online Multi-Facility Location Problems |
| title_full_unstemmed | Algorithmic Study of Online Multi-Facility Location Problems |
| title_short | Algorithmic Study of Online Multi-Facility Location Problems |
| title_sort | Algorithmic Study of Online Multi-Facility Location Problems |
| url | http://hdl.handle.net/10725/17645 https://doi.org/10.1007/s42979-022-01193-y http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/article/10.1007/s42979-022-01193-y |