Online Facility Location in Evolving Metrics
The Dynamic Facility Location problem is a generalization of the classic Facility Location problem, in which the distance metric between clients and facilities changes over time. Such metrics that develop as a function of time are usually called “evolving metrics”, thus Dynamic Facility Location can...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/3/73 |
| _version_ | 1797395335402749952 |
|---|---|
| author | Dimitris Fotakis Loukas Kavouras Lydia Zakynthinou |
| author_facet | Dimitris Fotakis Loukas Kavouras Lydia Zakynthinou |
| author_sort | Dimitris Fotakis |
| collection | DOAJ |
| description | The Dynamic Facility Location problem is a generalization of the classic Facility Location problem, in which the distance metric between clients and facilities changes over time. Such metrics that develop as a function of time are usually called “evolving metrics”, thus Dynamic Facility Location can be alternatively interpreted as a Facility Location problem in evolving metrics. The objective in this time-dependent variant is to balance the trade-off between optimizing the classic objective function and the <i>stability</i> of the solution, which is modeled by charging a switching cost when a client’s assignment changes from one facility to another. In this paper, we study the online variant of Dynamic Facility Location. We present a randomized <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mo form="prefix">log</mo><mi>m</mi><mo>+</mo><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>-competitive algorithm, where <i>m</i> is the number of facilities and <i>n</i> is the number of clients. In the first step, our algorithm produces a fractional solution, in each timestep, to the objective of Dynamic Facility Location involving a regularization function. This step is an adaptation of the generic algorithm proposed by Buchbinder et al. in their work “Competitive Analysis via Regularization.” Then, our algorithm rounds the fractional solution of this timestep to an integral one with the use of exponential clocks. We complement our result by proving a lower bound of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Ω</mi><mo>(</mo><mi>m</mi><mo>)</mo></mrow></semantics></math></inline-formula> for deterministic algorithms and lower bound of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Ω</mi><mo>(</mo><mo form="prefix">log</mo><mi>m</mi><mo>)</mo></mrow></semantics></math></inline-formula> for randomized algorithms. To the best of our knowledge, these are the first results for the online variant of the Dynamic Facility Location problem. |
| first_indexed | 2024-03-09T00:32:59Z |
| format | Article |
| id | doaj.art-ec05f5900e4b4b8eb0a0327b63b07177 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T00:32:59Z |
| publishDate | 2021-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-ec05f5900e4b4b8eb0a0327b63b071772023-12-11T18:24:16ZengMDPI AGAlgorithms1999-48932021-02-011437310.3390/a14030073Online Facility Location in Evolving MetricsDimitris Fotakis0Loukas Kavouras1Lydia Zakynthinou2School of Electrical and Computer Engineering, National Technical University of Athens, 15780 Athens, GreeceSchool of Electrical and Computer Engineering, National Technical University of Athens, 15780 Athens, GreeceKhoury College of Computer Science, Northeastern University, Boston, MA 02115, USAThe Dynamic Facility Location problem is a generalization of the classic Facility Location problem, in which the distance metric between clients and facilities changes over time. Such metrics that develop as a function of time are usually called “evolving metrics”, thus Dynamic Facility Location can be alternatively interpreted as a Facility Location problem in evolving metrics. The objective in this time-dependent variant is to balance the trade-off between optimizing the classic objective function and the <i>stability</i> of the solution, which is modeled by charging a switching cost when a client’s assignment changes from one facility to another. In this paper, we study the online variant of Dynamic Facility Location. We present a randomized <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mo form="prefix">log</mo><mi>m</mi><mo>+</mo><mo form="prefix">log</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>-competitive algorithm, where <i>m</i> is the number of facilities and <i>n</i> is the number of clients. In the first step, our algorithm produces a fractional solution, in each timestep, to the objective of Dynamic Facility Location involving a regularization function. This step is an adaptation of the generic algorithm proposed by Buchbinder et al. in their work “Competitive Analysis via Regularization.” Then, our algorithm rounds the fractional solution of this timestep to an integral one with the use of exponential clocks. We complement our result by proving a lower bound of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Ω</mi><mo>(</mo><mi>m</mi><mo>)</mo></mrow></semantics></math></inline-formula> for deterministic algorithms and lower bound of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Ω</mi><mo>(</mo><mo form="prefix">log</mo><mi>m</mi><mo>)</mo></mrow></semantics></math></inline-formula> for randomized algorithms. To the best of our knowledge, these are the first results for the online variant of the Dynamic Facility Location problem.https://www.mdpi.com/1999-4893/14/3/73dynamic facility locationonline convex optimizationcompetitive analysis |
| spellingShingle | Dimitris Fotakis Loukas Kavouras Lydia Zakynthinou Online Facility Location in Evolving Metrics Algorithms dynamic facility location online convex optimization competitive analysis |
| title | Online Facility Location in Evolving Metrics |
| title_full | Online Facility Location in Evolving Metrics |
| title_fullStr | Online Facility Location in Evolving Metrics |
| title_full_unstemmed | Online Facility Location in Evolving Metrics |
| title_short | Online Facility Location in Evolving Metrics |
| title_sort | online facility location in evolving metrics |
| topic | dynamic facility location online convex optimization competitive analysis |
| url | https://www.mdpi.com/1999-4893/14/3/73 |
| work_keys_str_mv | AT dimitrisfotakis onlinefacilitylocationinevolvingmetrics AT loukaskavouras onlinefacilitylocationinevolvingmetrics AT lydiazakynthinou onlinefacilitylocationinevolvingmetrics |