[{"date_updated":"2022-08-02T08:07:30Z","author":[{"first_name":"Jannik","full_name":"Castenow, Jannik","id":"38705","last_name":"Castenow"},{"last_name":"Feldkord","id":"22704","full_name":"Feldkord, Björn","first_name":"Björn"},{"first_name":"Till","last_name":"Knollmann","orcid":"0000-0003-2014-4696","full_name":"Knollmann, Till","id":"39241"},{"first_name":"Manuel","last_name":"Malatyali","id":"41265","full_name":"Malatyali, Manuel"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm"}],"doi":"10.1145/3490148.3538595","publication_identifier":{"isbn":["9781450391467"]},"page":"345-356","citation":{"short":"J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide, in: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery, 2022, pp. 345–356.","mla":"Castenow, Jannik, et al. “The K-Server with Preferences Problem.” <i>Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures</i>, Association for Computing Machinery, 2022, pp. 345–56, doi:<a href=\"https://doi.org/10.1145/3490148.3538595\">10.1145/3490148.3538595</a>.","bibtex":"@inproceedings{Castenow_Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2022, title={The k-Server with Preferences Problem}, DOI={<a href=\"https://doi.org/10.1145/3490148.3538595\">10.1145/3490148.3538595</a>}, booktitle={Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures}, publisher={Association for Computing Machinery}, author={Castenow, Jannik and Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2022}, pages={345–356} }","apa":"Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., &#38; Meyer auf der Heide, F. (2022). The k-Server with Preferences Problem. <i>Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures</i>, 345–356. <a href=\"https://doi.org/10.1145/3490148.3538595\">https://doi.org/10.1145/3490148.3538595</a>","ama":"Castenow J, Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. The k-Server with Preferences Problem. In: <i>Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures</i>. Association for Computing Machinery; 2022:345-356. doi:<a href=\"https://doi.org/10.1145/3490148.3538595\">10.1145/3490148.3538595</a>","chicago":"Castenow, Jannik, Björn Feldkord, Till Knollmann, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “The K-Server with Preferences Problem.” In <i>Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures</i>, 345–56. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3490148.3538595\">https://doi.org/10.1145/3490148.3538595</a>.","ieee":"J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der Heide, “The k-Server with Preferences Problem,” in <i>Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures</i>, 2022, pp. 345–356, doi: <a href=\"https://doi.org/10.1145/3490148.3538595\">10.1145/3490148.3538595</a>."},"_id":"31847","project":[{"name":"SFB 901: SFB 901","_id":"1"},{"_id":"2","name":"SFB 901 - A: SFB 901 - Project Area A"},{"name":"SFB 901 - A1: SFB 901 - Subproject A1","_id":"5"}],"department":[{"_id":"63"}],"user_id":"39241","type":"conference","status":"public","publisher":"Association for Computing Machinery","date_created":"2022-06-10T09:06:42Z","title":"The k-Server with Preferences Problem","year":"2022","external_id":{"arxiv":["2205.11102"]},"keyword":["K-Server Problem","Heterogeneity","Online Caching"],"language":[{"iso":"eng"}],"publication":"Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures","abstract":[{"lang":"eng","text":"The famous $k$-Server Problem covers plenty of resource allocation scenarios, and several variations have been studied extensively for decades. However, to the best of our knowledge, no research has considered the problem if the servers are not identical and requests can express which specific servers should serve them. Therefore, we present a new model generalizing the $k$-Server Problem by *preferences* of the requests and proceed to study it in a uniform metric space for deterministic online algorithms (the special case of paging).\r\n\r\nIn our model, requests can either demand to be answered by any server (*general requests*) or by a specific one (*specific requests*). If only general requests appear, the instance is one of the original $k$-Server Problem, and a lower bound for the competitive ratio of $k$ applies. If only specific requests appear, a solution with a competitive ratio of $1$ becomes trivial since there is no freedom regarding the servers' movements. Perhaps counter-intuitively, we show that if both kinds of requests appear, the lower bound raises to $2k-1$.\r\n\r\nWe study deterministic online algorithms in uniform metrics and present two algorithms. The first one has an adaptive competitive ratio dependent on the frequency of specific requests. It achieves a worst-case competitive ratio of $3k-2$ while it is optimal when only general or only specific requests appear (competitive ratio of $k$ and $1$, respectively). The second has a fixed close-to-optimal worst-case competitive ratio of $2k+14$. For the first algorithm, we show a lower bound of $3k-2$, while the second algorithm has a lower bound of $2k-1$ when only general requests appear.\r\n    \r\nThe two algorithms differ in only one behavioral rule for each server that significantly influences the competitive ratio. Each server acting according to the rule allows approaching the worst-case lower bound, while it implies an increased lower bound for $k$-Server instances. In other words, there is a trade-off between performing well against instances of the $k$-Server Problem and instances containing specific requests. We also show that no deterministic online algorithm can be optimal for both kinds of instances simultaneously."}]},{"citation":{"ama":"Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. Managing Multiple Mobile Resources. <i>Theory of Computing Systems</i>. 2021;65:943–984. doi:<a href=\"https://doi.org/10.1007/s00224-020-10023-8\">10.1007/s00224-020-10023-8</a>","chicago":"Feldkord, Björn, Till Knollmann, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “Managing Multiple Mobile Resources.” <i>Theory of Computing Systems</i> 65 (2021): 943–984. <a href=\"https://doi.org/10.1007/s00224-020-10023-8\">https://doi.org/10.1007/s00224-020-10023-8</a>.","ieee":"B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der Heide, “Managing Multiple Mobile Resources,” <i>Theory of Computing Systems</i>, vol. 65, pp. 943–984, 2021, doi: <a href=\"https://doi.org/10.1007/s00224-020-10023-8\">10.1007/s00224-020-10023-8</a>.","short":"B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide, Theory of Computing Systems 65 (2021) 943–984.","mla":"Feldkord, Björn, et al. “Managing Multiple Mobile Resources.” <i>Theory of Computing Systems</i>, vol. 65, 2021, pp. 943–984, doi:<a href=\"https://doi.org/10.1007/s00224-020-10023-8\">10.1007/s00224-020-10023-8</a>.","bibtex":"@article{Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2021, title={Managing Multiple Mobile Resources}, volume={65}, DOI={<a href=\"https://doi.org/10.1007/s00224-020-10023-8\">10.1007/s00224-020-10023-8</a>}, journal={Theory of Computing Systems}, author={Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2021}, pages={943–984} }","apa":"Feldkord, B., Knollmann, T., Malatyali, M., &#38; Meyer auf der Heide, F. (2021). Managing Multiple Mobile Resources. <i>Theory of Computing Systems</i>, <i>65</i>, 943–984. <a href=\"https://doi.org/10.1007/s00224-020-10023-8\">https://doi.org/10.1007/s00224-020-10023-8</a>"},"intvolume":"        65","page":"943–984","year":"2021","publication_status":"published","doi":"10.1007/s00224-020-10023-8","title":"Managing Multiple Mobile Resources","author":[{"first_name":"Björn","full_name":"Feldkord, Björn","id":"22704","last_name":"Feldkord"},{"orcid":"0000-0003-2014-4696","last_name":"Knollmann","id":"39241","full_name":"Knollmann, Till","first_name":"Till"},{"first_name":"Manuel","full_name":"Malatyali, Manuel","id":"41265","last_name":"Malatyali"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm"}],"date_created":"2020-12-08T08:40:10Z","volume":65,"date_updated":"2022-01-06T06:54:31Z","status":"public","type":"journal_article","publication":"Theory of Computing Systems","language":[{"iso":"eng"}],"user_id":"15415","department":[{"_id":"63"}],"project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"_id":"20683"},{"publication_status":"published","year":"2021","page":"14:1 - 14:17","citation":{"mla":"Bienkowski, Marcin, et al. “A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location.” <i>Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS)</i>, 2021, pp. 14:1-14:17, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.14\">10.4230/LIPIcs.STACS.2021.14</a>.","bibtex":"@inproceedings{Bienkowski_Feldkord_Schmidt_2021, title={A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.14\">10.4230/LIPIcs.STACS.2021.14</a>}, booktitle={Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS)}, author={Bienkowski, Marcin and Feldkord, Björn and Schmidt, Pawel}, year={2021}, pages={14:1-14:17} }","short":"M. Bienkowski, B. Feldkord, P. Schmidt, in: Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS), 2021, pp. 14:1-14:17.","apa":"Bienkowski, M., Feldkord, B., &#38; Schmidt, P. (2021). A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location. In <i>Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS)</i> (pp. 14:1-14:17). <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.14\">https://doi.org/10.4230/LIPIcs.STACS.2021.14</a>","ama":"Bienkowski M, Feldkord B, Schmidt P. A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location. In: <i>Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS)</i>. ; 2021:14:1-14:17. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.14\">10.4230/LIPIcs.STACS.2021.14</a>","ieee":"M. Bienkowski, B. Feldkord, and P. Schmidt, “A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location,” in <i>Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS)</i>, 2021, pp. 14:1-14:17.","chicago":"Bienkowski, Marcin, Björn Feldkord, and Pawel Schmidt. “A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location.” In <i>Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS)</i>, 14:1-14:17, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.14\">https://doi.org/10.4230/LIPIcs.STACS.2021.14</a>."},"date_updated":"2022-01-06T06:54:40Z","date_created":"2020-12-21T13:46:16Z","author":[{"last_name":"Bienkowski","full_name":"Bienkowski, Marcin","first_name":"Marcin"},{"first_name":"Björn","last_name":"Feldkord","id":"22704","full_name":"Feldkord, Björn"},{"first_name":"Pawel","full_name":"Schmidt, Pawel","last_name":"Schmidt"}],"title":"A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location","doi":"10.4230/LIPIcs.STACS.2021.14","publication":"Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS)","type":"conference","status":"public","_id":"20817","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"department":[{"_id":"63"}],"user_id":"22704","language":[{"iso":"eng"}]},{"author":[{"first_name":"Jannik","last_name":"Castenow","id":"38705","full_name":"Castenow, Jannik"},{"full_name":"Feldkord, Björn","id":"22704","last_name":"Feldkord","first_name":"Björn"},{"first_name":"Till","last_name":"Knollmann","orcid":"0000-0003-2014-4696","id":"39241","full_name":"Knollmann, Till"},{"first_name":"Manuel","last_name":"Malatyali","full_name":"Malatyali, Manuel"},{"full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}],"date_updated":"2022-01-06T06:53:10Z","doi":"10.1145/3350755.3400281","publication_status":"published","publication_identifier":{"isbn":["9781450369350"]},"has_accepted_license":"1","citation":{"apa":"Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., &#38; Meyer auf der Heide, F. (2020). The Online Multi-Commodity Facility Location Problem. In <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures</i>. <a href=\"https://doi.org/10.1145/3350755.3400281\">https://doi.org/10.1145/3350755.3400281</a>","mla":"Castenow, Jannik, et al. “The Online Multi-Commodity Facility Location Problem.” <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures</i>, 2020, doi:<a href=\"https://doi.org/10.1145/3350755.3400281\">10.1145/3350755.3400281</a>.","short":"J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide, in: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020.","bibtex":"@inproceedings{Castenow_Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2020, title={The Online Multi-Commodity Facility Location Problem}, DOI={<a href=\"https://doi.org/10.1145/3350755.3400281\">10.1145/3350755.3400281</a>}, booktitle={Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures}, author={Castenow, Jannik and Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2020} }","ieee":"J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der Heide, “The Online Multi-Commodity Facility Location Problem,” in <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures</i>, 2020.","chicago":"Castenow, Jannik, Björn Feldkord, Till Knollmann, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “The Online Multi-Commodity Facility Location Problem.” In <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures</i>, 2020. <a href=\"https://doi.org/10.1145/3350755.3400281\">https://doi.org/10.1145/3350755.3400281</a>.","ama":"Castenow J, Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. The Online Multi-Commodity Facility Location Problem. In: <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures</i>. ; 2020. doi:<a href=\"https://doi.org/10.1145/3350755.3400281\">10.1145/3350755.3400281</a>"},"user_id":"39241","department":[{"_id":"63"}],"project":[{"name":"SFB 901","_id":"1"},{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"_id":"17370","file_date_updated":"2020-07-14T07:56:52Z","type":"conference","status":"public","date_created":"2020-07-14T07:53:20Z","title":"The Online Multi-Commodity Facility Location Problem","year":"2020","external_id":{"arxiv":["2005.08391"]},"language":[{"iso":"eng"}],"ddc":["000"],"keyword":["Online Multi-Commodity Facility Location","Competitive Ratio","Online Optimization","Facility Location Problem"],"publication":"Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures","file":[{"file_size":1271416,"file_name":"3350755.3400281.pdf","file_id":"17373","access_level":"closed","date_updated":"2020-07-14T07:56:52Z","date_created":"2020-07-14T07:56:52Z","creator":"tillk","success":1,"relation":"main_file","content_type":"application/pdf"}],"abstract":[{"lang":"eng","text":" We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of a finite set \\( S \\) of commodities.\r\n  Ravi and Sinha (SODA 2004) introduced the model as the \\emph{Multi-Commodity Facility Location Problem} (MFLP) and considered it an offline optimization problem.\r\n  The model itself is similar to the FLP: i.e., requests are located at points of a finite metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances.\r\n  In addition, requests and facilities are heterogeneous; they request or offer multiple commodities out of $S$.\r\n  A request has to be connected to a set of facilities jointly offering the commodities demanded by it.\r\n  In comparison to the FLP, an algorithm has to decide not only if and where to place facilities, but also which commodities to offer at each.\r\n\r\n  To the best of our knowledge we are the first to study the problem in its online variant in which requests, their positions and their commodities are not known beforehand but revealed over time.\r\n  We present results regarding the competitive ratio.\r\n  On the one hand, we show that heterogeneity influences the competitive ratio by developing a lower bound on the competitive ratio for any randomized online algorithm of \\( \\Omega (  \\sqrt{|S|} + \\frac{\\log n}{\\log \\log n}  ) \\) that already holds for simple line metrics.\r\n  Here, \\( n \\) is the number of requests.\r\n  On the other side, we establish a deterministic \\( \\mathcal{O}(\\sqrt{|S|} \\cdot \\log n) \\)-competitive algorithm and a randomized \\( \\mathcal{O}(\\sqrt{|S|} \\cdot \\frac{\\log n}{\\log \\log n} ) \\)-competitive algorithm.\r\n  Further, we show that when considering a more special class of cost functions for the construction cost of a facility, the competitive ratio decreases given by our deterministic algorithm depending on the function."}]},{"has_accepted_license":"1","citation":{"ama":"Feldkord B. <i>Mobile Resource Allocation</i>. Universität Paderborn; 2020. doi:<a href=\"https://doi.org/10.17619/UNIPB/1-869\">10.17619/UNIPB/1-869</a>","ieee":"B. Feldkord, <i>Mobile Resource Allocation</i>. Universität Paderborn, 2020.","chicago":"Feldkord, Björn. <i>Mobile Resource Allocation</i>. Universität Paderborn, 2020. <a href=\"https://doi.org/10.17619/UNIPB/1-869\">https://doi.org/10.17619/UNIPB/1-869</a>.","bibtex":"@book{Feldkord_2020, place={Universität Paderborn}, title={Mobile Resource Allocation}, DOI={<a href=\"https://doi.org/10.17619/UNIPB/1-869\">10.17619/UNIPB/1-869</a>}, author={Feldkord, Björn}, year={2020} }","mla":"Feldkord, Björn. <i>Mobile Resource Allocation</i>. 2020, doi:<a href=\"https://doi.org/10.17619/UNIPB/1-869\">10.17619/UNIPB/1-869</a>.","short":"B. Feldkord, Mobile Resource Allocation, Universität Paderborn, 2020.","apa":"Feldkord, B. (2020). <i>Mobile Resource Allocation</i>. Universität Paderborn. <a href=\"https://doi.org/10.17619/UNIPB/1-869\">https://doi.org/10.17619/UNIPB/1-869</a>"},"year":"2020","place":"Universität Paderborn","date_created":"2020-01-23T14:20:25Z","supervisor":[{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm"}],"author":[{"id":"22704","full_name":"Feldkord, Björn","last_name":"Feldkord","first_name":"Björn"}],"date_updated":"2022-01-06T06:52:31Z","doi":"10.17619/UNIPB/1-869","title":"Mobile Resource Allocation","type":"dissertation","file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_name":"DissertationFeldkord.pdf","file_id":"15634","access_level":"closed","file_size":633652,"date_created":"2020-01-24T08:19:38Z","creator":"florida","date_updated":"2020-01-24T08:19:38Z"}],"status":"public","user_id":"15415","department":[{"_id":"63"}],"project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"_id":"15631","language":[{"iso":"eng"}],"file_date_updated":"2020-01-24T08:19:38Z","ddc":["000"]},{"date_updated":"2022-01-06T06:51:20Z","publisher":"Springer","author":[{"first_name":"Björn","full_name":"Feldkord, Björn","id":"22704","last_name":"Feldkord"},{"orcid":"0000-0003-2014-4696","last_name":"Knollmann","full_name":"Knollmann, Till","id":"39241","first_name":"Till"},{"full_name":"Malatyali, Manuel","last_name":"Malatyali","first_name":"Manuel"},{"last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","first_name":"Friedhelm"}],"date_created":"2019-07-22T09:00:05Z","title":"Managing Multiple Mobile Resources","doi":"10.1007/978-3-030-39479-0_9","publication_status":"published","year":"2019","citation":{"apa":"Feldkord, B., Knollmann, T., Malatyali, M., &#38; Meyer auf der Heide, F. (2019). Managing Multiple Mobile Resources. In <i>Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA)</i> (pp. 120–137). Springer. <a href=\"https://doi.org/10.1007/978-3-030-39479-0_9\">https://doi.org/10.1007/978-3-030-39479-0_9</a>","short":"B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide, in: Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA), Springer, 2019, pp. 120–137.","mla":"Feldkord, Björn, et al. “Managing Multiple Mobile Resources.” <i>Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA)</i>, Springer, 2019, pp. 120–37, doi:<a href=\"https://doi.org/10.1007/978-3-030-39479-0_9\">10.1007/978-3-030-39479-0_9</a>.","bibtex":"@inproceedings{Feldkord_Knollmann_Malatyali_Meyer auf der Heide_2019, title={Managing Multiple Mobile Resources}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-39479-0_9\">10.1007/978-3-030-39479-0_9</a>}, booktitle={Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA)}, publisher={Springer}, author={Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2019}, pages={120–137} }","ieee":"B. Feldkord, T. Knollmann, M. Malatyali, and F. Meyer auf der Heide, “Managing Multiple Mobile Resources,” in <i>Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA)</i>, 2019, pp. 120–137.","chicago":"Feldkord, Björn, Till Knollmann, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “Managing Multiple Mobile Resources.” In <i>Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA)</i>, 120–37. Springer, 2019. <a href=\"https://doi.org/10.1007/978-3-030-39479-0_9\">https://doi.org/10.1007/978-3-030-39479-0_9</a>.","ama":"Feldkord B, Knollmann T, Malatyali M, Meyer auf der Heide F. Managing Multiple Mobile Resources. In: <i>Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA)</i>. Springer; 2019:120-137. doi:<a href=\"https://doi.org/10.1007/978-3-030-39479-0_9\">10.1007/978-3-030-39479-0_9</a>"},"page":"120 - 137","project":[{"name":"SFB 901","_id":"1"},{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"external_id":{"arxiv":["1907.09834"]},"_id":"12870","user_id":"22704","department":[{"_id":"63"}],"language":[{"iso":"eng"}],"type":"conference","publication":"Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA)","status":"public"},{"file":[{"success":1,"relation":"main_file","content_type":"application/pdf","file_size":633652,"file_id":"15632","access_level":"closed","file_name":"DissertationFeldkord.pdf","date_updated":"2020-01-24T08:12:58Z","date_created":"2020-01-24T08:12:58Z","creator":"florida"}],"publication":"ACM Transactions on Parallel Computing (TOPC)","ddc":["000"],"language":[{"iso":"eng"}],"year":"2019","issue":"3","title":"The Mobile Server Problem","date_created":"2019-10-16T07:06:22Z","status":"public","type":"journal_article","article_number":"14","file_date_updated":"2020-01-24T08:12:58Z","_id":"13873","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A1","_id":"5"}],"department":[{"_id":"63"}],"user_id":"15504","intvolume":"         6","citation":{"apa":"Feldkord, B., &#38; Meyer auf der Heide, F. (2019). The Mobile Server Problem. <i>ACM Transactions on Parallel Computing (TOPC)</i>, <i>6</i>(3). <a href=\"https://doi.org/10.1145/3364204\">https://doi.org/10.1145/3364204</a>","bibtex":"@article{Feldkord_Meyer auf der Heide_2019, title={The Mobile Server Problem}, volume={6}, DOI={<a href=\"https://doi.org/10.1145/3364204\">10.1145/3364204</a>}, number={314}, journal={ACM Transactions on Parallel Computing (TOPC)}, author={Feldkord, Björn and Meyer auf der Heide, Friedhelm}, year={2019} }","mla":"Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server Problem.” <i>ACM Transactions on Parallel Computing (TOPC)</i>, vol. 6, no. 3, 14, 2019, doi:<a href=\"https://doi.org/10.1145/3364204\">10.1145/3364204</a>.","short":"B. Feldkord, F. Meyer auf der Heide, ACM Transactions on Parallel Computing (TOPC) 6 (2019).","chicago":"Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server Problem.” <i>ACM Transactions on Parallel Computing (TOPC)</i> 6, no. 3 (2019). <a href=\"https://doi.org/10.1145/3364204\">https://doi.org/10.1145/3364204</a>.","ieee":"B. Feldkord and F. Meyer auf der Heide, “The Mobile Server Problem,” <i>ACM Transactions on Parallel Computing (TOPC)</i>, vol. 6, no. 3, 2019.","ama":"Feldkord B, Meyer auf der Heide F. The Mobile Server Problem. <i>ACM Transactions on Parallel Computing (TOPC)</i>. 2019;6(3). doi:<a href=\"https://doi.org/10.1145/3364204\">10.1145/3364204</a>"},"has_accepted_license":"1","publication_status":"published","doi":"10.1145/3364204","date_updated":"2022-01-06T06:51:46Z","volume":6,"author":[{"id":"22704","full_name":"Feldkord, Björn","last_name":"Feldkord","first_name":"Björn"},{"id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}]},{"abstract":[{"lang":"eng","text":"We study the classic bin packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio while repacking items sparingly between updates. Formally, each item i has a movement cost c_i >= 0, and we want to use alpha * OPT bins and incur a movement cost gamma * c_i, either in the worst case, or in an amortized sense, for alpha, gamma as small as possible. We call gamma the recourse of the algorithm. This is motivated by cloud storage applications, where fully-dynamic bin packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure."}],"file":[{"content_type":"application/pdf","relation":"main_file","success":1,"date_created":"2018-10-31T16:58:18Z","creator":"feldi","date_updated":"2018-10-31T16:58:18Z","file_id":"5227","access_level":"closed","file_name":"LIPIcs-ICALP-2018-51.pdf","file_size":723824}],"publication":"45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)","ddc":["000"],"language":[{"iso":"eng"}],"external_id":{"arxiv":["1711.01231"]},"year":"2018","title":"Fully-Dynamic Bin Packing with Little Repacking","publisher":"Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik","date_created":"2018-04-24T15:21:56Z","editor":[{"first_name":"Ioannis","last_name":"Chatzigiannakis","full_name":"Chatzigiannakis, Ioannis"},{"first_name":"Christos","full_name":"Kaklamanis, Christos","last_name":"Kaklamanis"},{"first_name":"Dániel","full_name":"Marx, Dániel","last_name":"Marx"},{"first_name":"Donald","full_name":"Sannella, Donald","last_name":"Sannella"}],"status":"public","type":"conference","file_date_updated":"2018-10-31T16:58:18Z","_id":"2484","project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Project Area C","_id":"4"},{"_id":"5","name":"SFB 901 - Subproject A1"},{"_id":"7","name":"SFB 901 - Subproject A3"},{"name":"SFB 901 - Subproject C4","_id":"16"}],"department":[{"_id":"541"},{"_id":"63"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","user_id":"14052","place":"Dagstuhl, Germany","intvolume":"       107","page":"51:1-51:24","citation":{"ama":"Feldkord B, Feldotto M, Gupta A, et al. Fully-Dynamic Bin Packing with Little Repacking. In: Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. <i>45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)</i>. Vol 107. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik; 2018:51:1-51:24. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2018.51\">10.4230/LIPIcs.ICALP.2018.51</a>","ieee":"B. Feldkord <i>et al.</i>, “Fully-Dynamic Bin Packing with Little Repacking,” in <i>45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)</i>, Prag, 2018, vol. 107, pp. 51:1-51:24.","chicago":"Feldkord, Björn, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit  Kumar, Sören Riechers, and David Wajc. “Fully-Dynamic Bin Packing with Little Repacking.” In <i>45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)</i>, edited by Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, 107:51:1-51:24. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2018.51\">https://doi.org/10.4230/LIPIcs.ICALP.2018.51</a>.","apa":"Feldkord, B., Feldotto, M., Gupta, A., Guruganesh, G., Kumar, A., Riechers, S., &#38; Wajc, D. (2018). Fully-Dynamic Bin Packing with Little Repacking. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, &#38; D. Sannella (Eds.), <i>45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)</i> (Vol. 107, pp. 51:1-51:24). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2018.51\">https://doi.org/10.4230/LIPIcs.ICALP.2018.51</a>","mla":"Feldkord, Björn, et al. “Fully-Dynamic Bin Packing with Little Repacking.” <i>45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)</i>, edited by Ioannis Chatzigiannakis et al., vol. 107, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, pp. 51:1-51:24, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2018.51\">10.4230/LIPIcs.ICALP.2018.51</a>.","short":"B. Feldkord, M. Feldotto, A. Gupta, G. Guruganesh, A. Kumar, S. Riechers, D. Wajc, in: I. Chatzigiannakis, C. Kaklamanis, D. Marx, D. Sannella (Eds.), 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, pp. 51:1-51:24.","bibtex":"@inproceedings{Feldkord_Feldotto_Gupta_Guruganesh_Kumar_Riechers_Wajc_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Fully-Dynamic Bin Packing with Little Repacking}, volume={107}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2018.51\">10.4230/LIPIcs.ICALP.2018.51</a>}, booktitle={45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, publisher={Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, author={Feldkord, Björn and Feldotto, Matthias and Gupta, Anupam and Guruganesh, Guru and Kumar, Amit  and Riechers, Sören and Wajc, David}, editor={Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, Dániel and Sannella, DonaldEditors}, year={2018}, pages={51:1-51:24}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }"},"has_accepted_license":"1","publication_identifier":{"isbn":["978-3-95977-076-7"],"issn":["1868-8969"]},"publication_status":"published","conference":{"start_date":"2018-07-10","name":"45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)","location":"Prag","end_date":"2018-07-13"},"doi":"10.4230/LIPIcs.ICALP.2018.51","date_updated":"2022-01-06T06:56:39Z","volume":107,"author":[{"first_name":"Björn","last_name":"Feldkord","full_name":"Feldkord, Björn","id":"22704"},{"first_name":"Matthias","full_name":"Feldotto, Matthias","id":"14052","orcid":"0000-0003-1348-6516","last_name":"Feldotto"},{"full_name":"Gupta, Anupam","last_name":"Gupta","first_name":"Anupam"},{"full_name":"Guruganesh, Guru","last_name":"Guruganesh","first_name":"Guru"},{"first_name":"Amit ","last_name":"Kumar","full_name":"Kumar, Amit "},{"first_name":"Sören","last_name":"Riechers","full_name":"Riechers, Sören"},{"first_name":"David","full_name":"Wajc, David","last_name":"Wajc"}]},{"date_created":"2018-04-25T08:49:43Z","publisher":"ACM","title":"Online Facility Location with Mobile Facilities","year":"2018","language":[{"iso":"eng"}],"ddc":["000"],"publication":"Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","file":[{"date_created":"2018-11-02T14:42:33Z","creator":"ups","date_updated":"2018-11-02T14:42:33Z","file_name":"p373-feldkord.pdf","file_id":"5280","access_level":"closed","file_size":1207546,"content_type":"application/pdf","relation":"main_file","success":1}],"author":[{"last_name":"Feldkord","id":"22704","full_name":"Feldkord, Björn","first_name":"Björn"},{"full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}],"date_updated":"2022-01-06T06:56:39Z","doi":"10.1145/3210377.3210389","conference":{"location":"Wien","name":"SPAA'18"},"publication_status":"published","has_accepted_license":"1","citation":{"ama":"Feldkord B, Meyer auf der Heide F. Online Facility Location with Mobile Facilities. In: <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. ACM; 2018:373-381. doi:<a href=\"https://doi.org/10.1145/3210377.3210389\">10.1145/3210377.3210389</a>","chicago":"Feldkord, Björn, and Friedhelm Meyer auf der Heide. “Online Facility Location with Mobile Facilities.” In <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 373–81. ACM, 2018. <a href=\"https://doi.org/10.1145/3210377.3210389\">https://doi.org/10.1145/3210377.3210389</a>.","ieee":"B. Feldkord and F. Meyer auf der Heide, “Online Facility Location with Mobile Facilities,” in <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, Wien, 2018, pp. 373–381.","apa":"Feldkord, B., &#38; Meyer auf der Heide, F. (2018). Online Facility Location with Mobile Facilities. In <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i> (pp. 373–381). Wien: ACM. <a href=\"https://doi.org/10.1145/3210377.3210389\">https://doi.org/10.1145/3210377.3210389</a>","short":"B. Feldkord, F. Meyer auf der Heide, in: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, 2018, pp. 373–381.","bibtex":"@inproceedings{Feldkord_Meyer auf der Heide_2018, title={Online Facility Location with Mobile Facilities}, DOI={<a href=\"https://doi.org/10.1145/3210377.3210389\">10.1145/3210377.3210389</a>}, booktitle={Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, publisher={ACM}, author={Feldkord, Björn and Meyer auf der Heide, Friedhelm}, year={2018}, pages={373–381} }","mla":"Feldkord, Björn, and Friedhelm Meyer auf der Heide. “Online Facility Location with Mobile Facilities.” <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, ACM, 2018, pp. 373–81, doi:<a href=\"https://doi.org/10.1145/3210377.3210389\">10.1145/3210377.3210389</a>."},"page":"373 - 381 ","user_id":"477","department":[{"_id":"63"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"_id":"2485","file_date_updated":"2018-11-02T14:42:33Z","type":"conference","status":"public"},{"publication":"Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications","type":"book_chapter","status":"public","_id":"16392","department":[{"_id":"63"}],"user_id":"15415","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["9783319125671","9783319125688"]},"publication_status":"published","year":"2018","place":"Cham","citation":{"apa":"Feldkord, B., Malatyali, M., &#38; Meyer auf der Heide, F. (2018). A Dynamic Distributed Data Structure for Top-k and k-Select Queries. In <i>Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications</i>. Cham. <a href=\"https://doi.org/10.1007/978-3-319-98355-4_18\">https://doi.org/10.1007/978-3-319-98355-4_18</a>","bibtex":"@inbook{Feldkord_Malatyali_Meyer auf der Heide_2018, place={Cham}, title={A Dynamic Distributed Data Structure for Top-k and k-Select Queries}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-98355-4_18\">10.1007/978-3-319-98355-4_18</a>}, booktitle={Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications}, author={Feldkord, Björn and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2018} }","mla":"Feldkord, Björn, et al. “A Dynamic Distributed Data Structure for Top-k and k-Select Queries.” <i>Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications</i>, 2018, doi:<a href=\"https://doi.org/10.1007/978-3-319-98355-4_18\">10.1007/978-3-319-98355-4_18</a>.","short":"B. Feldkord, M. Malatyali, F. Meyer auf der Heide, in: Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, Cham, 2018.","ama":"Feldkord B, Malatyali M, Meyer auf der Heide F. A Dynamic Distributed Data Structure for Top-k and k-Select Queries. In: <i>Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications</i>. Cham; 2018. doi:<a href=\"https://doi.org/10.1007/978-3-319-98355-4_18\">10.1007/978-3-319-98355-4_18</a>","chicago":"Feldkord, Björn, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “A Dynamic Distributed Data Structure for Top-k and k-Select Queries.” In <i>Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications</i>. Cham, 2018. <a href=\"https://doi.org/10.1007/978-3-319-98355-4_18\">https://doi.org/10.1007/978-3-319-98355-4_18</a>.","ieee":"B. Feldkord, M. Malatyali, and F. Meyer auf der Heide, “A Dynamic Distributed Data Structure for Top-k and k-Select Queries,” in <i>Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications</i>, Cham, 2018."},"date_updated":"2022-01-06T06:52:50Z","date_created":"2020-04-03T07:04:59Z","author":[{"last_name":"Feldkord","id":"22704","full_name":"Feldkord, Björn","first_name":"Björn"},{"full_name":"Malatyali, Manuel","last_name":"Malatyali","first_name":"Manuel"},{"first_name":"Friedhelm","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide"}],"title":"A Dynamic Distributed Data Structure for Top-k and k-Select Queries","doi":"10.1007/978-3-319-98355-4_18"},{"language":[{"iso":"eng"}],"file_date_updated":"2018-11-02T15:06:13Z","ddc":["000"],"department":[{"_id":"63"}],"user_id":"477","_id":"70","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"status":"public","file":[{"file_size":287315,"file_id":"5293","file_name":"PriceFluctuationInOnlineLeasin.pdf","access_level":"closed","date_updated":"2018-11-02T15:06:13Z","creator":"ups","date_created":"2018-11-02T15:06:13Z","success":1,"relation":"main_file","content_type":"application/pdf"}],"publication":"Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)","type":"conference","doi":"10.1007/978-3-319-71147-8_2","title":"Price Fluctuations in Online Leasing","author":[{"id":"22704","full_name":"Feldkord, Björn","last_name":"Feldkord","first_name":"Björn"},{"first_name":"Christine","last_name":"Markarian","full_name":"Markarian, Christine","id":"37612"},{"last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","first_name":"Friedhelm"}],"date_created":"2017-10-17T12:41:05Z","date_updated":"2022-01-06T07:03:26Z","page":"17 - 31","citation":{"ama":"Feldkord B, Markarian C, Meyer auf der Heide F. Price Fluctuations in Online Leasing. In: <i>Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>. ; 2017:17-31. doi:<a href=\"https://doi.org/10.1007/978-3-319-71147-8_2\">10.1007/978-3-319-71147-8_2</a>","chicago":"Feldkord, Björn, Christine Markarian, and Friedhelm Meyer auf der Heide. “Price Fluctuations in Online Leasing.” In <i>Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 17–31, 2017. <a href=\"https://doi.org/10.1007/978-3-319-71147-8_2\">https://doi.org/10.1007/978-3-319-71147-8_2</a>.","ieee":"B. Feldkord, C. Markarian, and F. Meyer auf der Heide, “Price Fluctuations in Online Leasing,” in <i>Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2017, pp. 17–31.","mla":"Feldkord, Björn, et al. “Price Fluctuations in Online Leasing.” <i>Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2017, pp. 17–31, doi:<a href=\"https://doi.org/10.1007/978-3-319-71147-8_2\">10.1007/978-3-319-71147-8_2</a>.","bibtex":"@inproceedings{Feldkord_Markarian_Meyer auf der Heide_2017, title={Price Fluctuations in Online Leasing}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-71147-8_2\">10.1007/978-3-319-71147-8_2</a>}, booktitle={Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}, author={Feldkord, Björn and Markarian, Christine and Meyer auf der Heide, Friedhelm}, year={2017}, pages={17–31} }","short":"B. Feldkord, C. Markarian, F. Meyer auf der Heide, in: Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2017, pp. 17–31.","apa":"Feldkord, B., Markarian, C., &#38; Meyer auf der Heide, F. (2017). Price Fluctuations in Online Leasing. In <i>Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i> (pp. 17–31). <a href=\"https://doi.org/10.1007/978-3-319-71147-8_2\">https://doi.org/10.1007/978-3-319-71147-8_2</a>"},"year":"2017","has_accepted_license":"1"},{"date_updated":"2022-01-06T07:01:56Z","author":[{"id":"22704","full_name":"Feldkord, Björn","last_name":"Feldkord","first_name":"Björn"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm"}],"date_created":"2017-10-17T12:41:02Z","title":"The Mobile Server Problem","doi":"10.1145/3087556.3087575","has_accepted_license":"1","year":"2017","page":"313-319","citation":{"ama":"Feldkord B, Meyer auf der Heide F. The Mobile Server Problem. In: <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. ; 2017:313-319. doi:<a href=\"https://doi.org/10.1145/3087556.3087575\">10.1145/3087556.3087575</a>","ieee":"B. Feldkord and F. Meyer auf der Heide, “The Mobile Server Problem,” in <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2017, pp. 313–319.","chicago":"Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server Problem.” In <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 313–19, 2017. <a href=\"https://doi.org/10.1145/3087556.3087575\">https://doi.org/10.1145/3087556.3087575</a>.","bibtex":"@inproceedings{Feldkord_Meyer auf der Heide_2017, title={The Mobile Server Problem}, DOI={<a href=\"https://doi.org/10.1145/3087556.3087575\">10.1145/3087556.3087575</a>}, booktitle={Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, author={Feldkord, Björn and Meyer auf der Heide, Friedhelm}, year={2017}, pages={313–319} }","short":"B. Feldkord, F. Meyer auf der Heide, in: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 313–319.","mla":"Feldkord, Björn, and Friedhelm Meyer auf der Heide. “The Mobile Server Problem.” <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2017, pp. 313–19, doi:<a href=\"https://doi.org/10.1145/3087556.3087575\">10.1145/3087556.3087575</a>.","apa":"Feldkord, B., &#38; Meyer auf der Heide, F. (2017). The Mobile Server Problem. In <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i> (pp. 313–319). <a href=\"https://doi.org/10.1145/3087556.3087575\">https://doi.org/10.1145/3087556.3087575</a>"},"_id":"55","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"department":[{"_id":"63"}],"user_id":"477","ddc":["000"],"file_date_updated":"2018-11-02T14:55:10Z","language":[{"iso":"eng"}],"publication":"Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","type":"conference","abstract":[{"text":"We introduce the mobile server problem, inspired by current trends to move computational tasks from cloud structures to multiple devices close to the end user. An example for this are embedded systems in autonomous cars that communicate in order to coordinate their actions. Our model is a variant of the classical Page Migration Problem. Moreformally, we consider a mobile server holding a data page.The server can move in the Euclidean space (of arbitrary dimension). In every round, requests for data items from the page pop up at arbitrary points in the space. The requests are served, each at a cost of the distance from the requesting point and the server, and the mobile server may move, at a cost D times the distance traveled for some constant D . We assume a maximum distance m the server is allowed to move per round. We show that no online algorithm can achieve a competitive ratio independent of the length of the input sequence in this setting. Hence we augment the maximum movement distance of the online algorithms to ( 1 + δ) times the maximum distance of the offline solution. We provide a deterministic algorithm which is simple to describe and works for multiple variants of our problem. The algorithm achieves almost tight competitive ratios independent of the length of the input sequence.","lang":"eng"}],"status":"public","file":[{"file_size":691691,"access_level":"closed","file_name":"p313-feldkord.pdf","file_id":"5288","date_updated":"2018-11-02T14:55:10Z","date_created":"2018-11-02T14:55:10Z","creator":"ups","success":1,"relation":"main_file","content_type":"application/pdf"}]},{"_id":"16348","user_id":"15415","department":[{"_id":"63"}],"language":[{"iso":"eng"}],"type":"conference","publication":"Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)","status":"public","publisher":"Springer","date_updated":"2022-01-06T06:52:49Z","author":[{"last_name":"Biermeier","full_name":"Biermeier, Felix","first_name":"Felix"},{"first_name":"Björn","full_name":"Feldkord, Björn","id":"22704","last_name":"Feldkord"},{"first_name":"Manuel","full_name":"Malatyali, Manuel","last_name":"Malatyali"},{"full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}],"date_created":"2020-03-30T09:25:18Z","title":"A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries","doi":"10.1007/978-3-319-89441-6_21","year":"2017","citation":{"bibtex":"@inproceedings{Biermeier_Feldkord_Malatyali_Meyer auf der Heide_2017, title={A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-89441-6_21\">10.1007/978-3-319-89441-6_21</a>}, booktitle={Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)}, publisher={Springer}, author={Biermeier, Felix and Feldkord, Björn and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2017}, pages={285–300} }","mla":"Biermeier, Felix, et al. “A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries.” <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>, Springer, 2017, pp. 285–300, doi:<a href=\"https://doi.org/10.1007/978-3-319-89441-6_21\">10.1007/978-3-319-89441-6_21</a>.","short":"F. Biermeier, B. Feldkord, M. Malatyali, F. Meyer auf der Heide, in: Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA), Springer, 2017, pp. 285–300.","apa":"Biermeier, F., Feldkord, B., Malatyali, M., &#38; Meyer auf der Heide, F. (2017). A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries. In <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i> (pp. 285–300). Springer. <a href=\"https://doi.org/10.1007/978-3-319-89441-6_21\">https://doi.org/10.1007/978-3-319-89441-6_21</a>","ama":"Biermeier F, Feldkord B, Malatyali M, Meyer auf der Heide F. A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries. In: <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>. Springer; 2017:285-300. doi:<a href=\"https://doi.org/10.1007/978-3-319-89441-6_21\">10.1007/978-3-319-89441-6_21</a>","ieee":"F. Biermeier, B. Feldkord, M. Malatyali, and F. Meyer auf der Heide, “A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries,” in <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>, 2017, pp. 285–300.","chicago":"Biermeier, Felix, Björn Feldkord, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries.” In <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>, 285–300. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-89441-6_21\">https://doi.org/10.1007/978-3-319-89441-6_21</a>."},"page":"285 - 300"},{"_id":"149","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"7","name":"SFB 901 - Subproject A3"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"63"},{"_id":"541"}],"series_title":"LNCS","user_id":"477","ddc":["040"],"file_date_updated":"2018-03-21T12:55:43Z","language":[{"iso":"eng"}],"publication":"Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)","type":"conference","abstract":[{"text":"In this paper we consider a strategic variant of the online facility location problem. Given is a graph in which each node serves two roles: it is a strategic client stating requests as well as a potential location for a facility. In each time step one client states a request which induces private costs equal to the distance to the closest facility. Before serving, the clients may collectively decide to open new facilities, sharing the corresponding price. Instead of optimizing the global costs, each client acts selfishly. The prices of new facilities vary between nodes and also change over time, but are always bounded by some fixed value α. Both the requests as well as the facility prices are given by an online sequence and are not known in advance.We characterize the optimal strategies of the clients and analyze their overall performance in comparison to a centralized offline solution. If all players optimize their own competitiveness, the global performance of the system is O(√α⋅α) times worse than the offline optimum. A restriction to a natural subclass of strategies improves this result to O(α). We also show that for fixed facility costs, we can find strategies such that this bound further improves to O(√α).","lang":"eng"}],"status":"public","file":[{"date_updated":"2018-03-21T12:55:43Z","date_created":"2018-03-21T12:55:43Z","creator":"florida","file_size":236253,"file_name":"149-chp_3A10.1007_2F978-3-319-48749-6_43.pdf","file_id":"1553","access_level":"closed","content_type":"application/pdf","success":1,"relation":"main_file"}],"date_updated":"2022-01-06T06:52:10Z","author":[{"first_name":"Maximilian","last_name":"Drees","full_name":"Drees, Maximilian"},{"first_name":"Björn","last_name":"Feldkord","full_name":"Feldkord, Björn","id":"22704"},{"last_name":"Skopalik","full_name":"Skopalik, Alexander","id":"40384","first_name":"Alexander"}],"date_created":"2017-10-17T12:41:21Z","title":"Strategic Online Facility Location","doi":"10.1007/978-3-319-48749-6_43","has_accepted_license":"1","year":"2016","page":"593--607","citation":{"mla":"Drees, Maximilian, et al. “Strategic Online Facility Location.” <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 593--607, doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">10.1007/978-3-319-48749-6_43</a>.","bibtex":"@inproceedings{Drees_Feldkord_Skopalik_2016, series={LNCS}, title={Strategic Online Facility Location}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">10.1007/978-3-319-48749-6_43</a>}, booktitle={Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}, author={Drees, Maximilian and Feldkord, Björn and Skopalik, Alexander}, year={2016}, pages={593--607}, collection={LNCS} }","short":"M. Drees, B. Feldkord, A. Skopalik, in: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 593--607.","apa":"Drees, M., Feldkord, B., &#38; Skopalik, A. (2016). Strategic Online Facility Location. In <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i> (pp. 593--607). <a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">https://doi.org/10.1007/978-3-319-48749-6_43</a>","ama":"Drees M, Feldkord B, Skopalik A. Strategic Online Facility Location. In: <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>. LNCS. ; 2016:593--607. doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">10.1007/978-3-319-48749-6_43</a>","chicago":"Drees, Maximilian, Björn Feldkord, and Alexander Skopalik. “Strategic Online Facility Location.” In <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 593--607. LNCS, 2016. <a href=\"https://doi.org/10.1007/978-3-319-48749-6_43\">https://doi.org/10.1007/978-3-319-48749-6_43</a>.","ieee":"M. Drees, B. Feldkord, and A. Skopalik, “Strategic Online Facility Location,” in <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 593--607."}},{"citation":{"ama":"Feldkord B. <i>On Variants of the Page Migration Problem</i>. Universität Paderborn; 2014.","ieee":"B. Feldkord, <i>On Variants of the Page Migration Problem</i>. Universität Paderborn, 2014.","chicago":"Feldkord, Björn. <i>On Variants of the Page Migration Problem</i>. Universität Paderborn, 2014.","bibtex":"@book{Feldkord_2014, title={On Variants of the Page Migration Problem}, publisher={Universität Paderborn}, author={Feldkord, Björn}, year={2014} }","mla":"Feldkord, Björn. <i>On Variants of the Page Migration Problem</i>. Universität Paderborn, 2014.","short":"B. Feldkord, On Variants of the Page Migration Problem, Universität Paderborn, 2014.","apa":"Feldkord, B. (2014). <i>On Variants of the Page Migration Problem</i>. Universität Paderborn."},"status":"public","year":"2014","type":"mastersthesis","title":"On Variants of the Page Migration Problem","date_created":"2017-10-17T12:42:08Z","author":[{"first_name":"Björn","last_name":"Feldkord","id":"22704","full_name":"Feldkord, Björn"}],"user_id":"477","publisher":"Universität Paderborn","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"date_updated":"2022-01-06T06:59:54Z","_id":"391"},{"author":[{"last_name":"Feldkord","full_name":"Feldkord, Björn","id":"22704","first_name":"Björn"}],"date_created":"2017-10-17T12:42:49Z","publisher":"Universität Paderborn","date_updated":"2022-01-06T07:02:49Z","title":"Lokale Swaps und überholte Informationen in Basic Network Creation Games","citation":{"ama":"Feldkord B. <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn; 2012.","ieee":"B. Feldkord, <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn, 2012.","chicago":"Feldkord, Björn. <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn, 2012.","bibtex":"@book{Feldkord_2012, title={Lokale Swaps und überholte Informationen in Basic Network Creation Games}, publisher={Universität Paderborn}, author={Feldkord, Björn}, year={2012} }","mla":"Feldkord, Björn. <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn, 2012.","short":"B. Feldkord, Lokale Swaps und überholte Informationen in Basic Network Creation Games, Universität Paderborn, 2012.","apa":"Feldkord, B. (2012). <i>Lokale Swaps und überholte Informationen in Basic Network Creation Games</i>. Universität Paderborn."},"year":"2012","user_id":"477","_id":"600","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"_id":"2","name":"SFB 901 - Project Area A"}],"language":[{"iso":"ger"}],"type":"bachelorsthesis","status":"public"}]