The K-server problem via a modern optimization lens
We consider the well-known K-server problem from the perspective of mixed integer, robust and adaptive optimization. We propose a new tractable mixed integer linear formulation of the K-server problem that incorporates both information from the past and uncertainty about the future. By combining ide...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129340 |
| _version_ | 1826210756678385664 |
|---|---|
| author | Bertsimas, Dimitris J Jaillet, Patrick Korolko, Nikita (Nikita E.) |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Bertsimas, Dimitris J Jaillet, Patrick Korolko, Nikita (Nikita E.) |
| author_sort | Bertsimas, Dimitris J |
| collection | MIT |
| description | We consider the well-known K-server problem from the perspective of mixed integer, robust and adaptive optimization. We propose a new tractable mixed integer linear formulation of the K-server problem that incorporates both information from the past and uncertainty about the future. By combining ideas from classical online algorithms developed in the computer science literature and robust and adaptive optimization developed in the operations research literature we propose a new method that (a) is computationally tractable, (b) almost always outperforms all other methods in numerical experiments, and (c) is stable with respect to potential errors in the assumptions about the future. |
| first_indexed | 2024-09-23T14:55:11Z |
| format | Article |
| id | mit-1721.1/129340 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:55:11Z |
| publishDate | 2021 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1293402022-10-01T23:19:44Z The K-server problem via a modern optimization lens Bertsimas, Dimitris J Jaillet, Patrick Korolko, Nikita (Nikita E.) Sloan School of Management Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Operations Research Center We consider the well-known K-server problem from the perspective of mixed integer, robust and adaptive optimization. We propose a new tractable mixed integer linear formulation of the K-server problem that incorporates both information from the past and uncertainty about the future. By combining ideas from classical online algorithms developed in the computer science literature and robust and adaptive optimization developed in the operations research literature we propose a new method that (a) is computationally tractable, (b) almost always outperforms all other methods in numerical experiments, and (c) is stable with respect to potential errors in the assumptions about the future. United States. Office of Naval Research (Grant N00014-12-1-0999 and N00014-16-1-2786) 2021-01-08T14:45:45Z 2021-01-08T14:45:45Z 2019-07 2020-12-21T18:18:46Z Article http://purl.org/eprint/type/JournalArticle 0377-2217 https://hdl.handle.net/1721.1/129340 Bertsimas, Dimitris, Patrick Jaillet and Nikita Korolko. “The K-server problem via a modern optimization lens.” European Journal of Operational Research, 276, 1 (July 2019): © 2019 The Author(s) en 10.1016/J.EJOR.2018.12.044 European Journal of Operational Research Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV MIT web domain |
| spellingShingle | Bertsimas, Dimitris J Jaillet, Patrick Korolko, Nikita (Nikita E.) The K-server problem via a modern optimization lens |
| title | The K-server problem via a modern optimization lens |
| title_full | The K-server problem via a modern optimization lens |
| title_fullStr | The K-server problem via a modern optimization lens |
| title_full_unstemmed | The K-server problem via a modern optimization lens |
| title_short | The K-server problem via a modern optimization lens |
| title_sort | k server problem via a modern optimization lens |
| url | https://hdl.handle.net/1721.1/129340 |
| work_keys_str_mv | AT bertsimasdimitrisj thekserverproblemviaamodernoptimizationlens AT jailletpatrick thekserverproblemviaamodernoptimizationlens AT korolkonikitanikitae thekserverproblemviaamodernoptimizationlens AT bertsimasdimitrisj kserverproblemviaamodernoptimizationlens AT jailletpatrick kserverproblemviaamodernoptimizationlens AT korolkonikitanikitae kserverproblemviaamodernoptimizationlens |