[{"date_updated":"2022-01-06T07:01:00Z","author":[{"last_name":"Benter","full_name":"Benter, Markus","first_name":"Markus"},{"first_name":"Till","id":"39241","full_name":"Knollmann, Till","last_name":"Knollmann","orcid":"0000-0003-2014-4696"},{"first_name":"Friedhelm","full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide"},{"last_name":"Setzer","id":"11108","full_name":"Setzer, Alexander","first_name":"Alexander"},{"first_name":"Jannik","last_name":"Sundermeier","id":"38705","full_name":"Sundermeier, Jannik"}],"date_created":"2018-09-11T05:26:59Z","title":"A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension","conference":{"end_date":"2018-08-21","location":"Helsinki","name":"4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)","start_date":"2018-08-20"},"doi":"10.1007/978-3-030-19759-9_4","has_accepted_license":"1","year":"2018","citation":{"chicago":"Benter, Markus, Till Knollmann, Friedhelm Meyer auf der Heide, Alexander Setzer, and Jannik Sundermeier. “A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension.” In <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, 2018. <a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">https://doi.org/10.1007/978-3-030-19759-9_4</a>.","ieee":"M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, and J. Sundermeier, “A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension,” in <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, Helsinki, 2018.","ama":"Benter M, Knollmann T, Meyer auf der Heide F, Setzer A, Sundermeier J. A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension. In: <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>. ; 2018. doi:<a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">10.1007/978-3-030-19759-9_4</a>","mla":"Benter, Markus, et al. “A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension.” <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, 2018, doi:<a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">10.1007/978-3-030-19759-9_4</a>.","bibtex":"@inproceedings{Benter_Knollmann_Meyer auf der Heide_Setzer_Sundermeier_2018, title={A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">10.1007/978-3-030-19759-9_4</a>}, booktitle={Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)}, author={Benter, Markus and Knollmann, Till and Meyer auf der Heide, Friedhelm and Setzer, Alexander and Sundermeier, Jannik}, year={2018} }","short":"M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, J. Sundermeier, in: Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD), 2018.","apa":"Benter, M., Knollmann, T., Meyer auf der Heide, F., Setzer, A., &#38; Sundermeier, J. (2018). A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension. In <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>. Helsinki. <a href=\"https://doi.org/10.1007/978-3-030-19759-9_4\">https://doi.org/10.1007/978-3-030-19759-9_4</a>"},"_id":"4375","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"department":[{"_id":"63"},{"_id":"79"}],"user_id":"14955","keyword":["Distributed Storage","Multi-Dimensional Range Queries","Peer-to-Peer","Hilbert Curve"],"ddc":["000"],"file_date_updated":"2018-11-27T10:03:33Z","language":[{"iso":"eng"}],"publication":"Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)","type":"conference","abstract":[{"text":"We present a peer-to-peer network that supports the efficient processing of orthogonal range queries $R=\\bigtimes_{i=1}^{d}[a_i,\\,b_i]$ in a $d$-dimensional point space.\\\\\r\nThe  network is the same for each dimension, namely a distance halving network like the one introduced by Naor and Wieder (ACM TALG'07).\r\nWe show how to execute such range queries using $\\mathcal{O}\\left(2^{d'}d\\,\\log m + d\\,|R|\\right)$ hops (and the same number of messages) in total. Here $[m]^d$ is the ground set, $|R|$ is the size and $d'$ the dimension of the queried range.\r\nFurthermore, if the peers form a distributed network, the query can be answered in $\\mathcal{O}\\left(d\\,\\log m + d\\,\\sum_{i=1}^{d}(b_i-a_i+1)\\right)$ communication rounds.\r\nOur algorithms are based on a mapping of the Hilbert Curve through $[m]^d$ to the peers.","lang":"eng"}],"status":"public","file":[{"file_id":"5863","access_level":"closed","file_name":"A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension.pdf","file_size":1122875,"date_created":"2018-11-27T10:03:33Z","creator":"tillk","date_updated":"2018-11-27T10:03:33Z","relation":"main_file","success":1,"content_type":"application/pdf"}]},{"publication_identifier":{"isbn":["9783319125671","9783319125688"],"issn":["0302-9743","1611-3349"]},"publication_status":"published","year":"2018","place":"Cham","citation":{"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.","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>.","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>","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."},"date_updated":"2022-01-06T06:52:50Z","date_created":"2020-04-03T07:04:59Z","author":[{"first_name":"Björn","last_name":"Feldkord","id":"22704","full_name":"Feldkord, Björn"},{"first_name":"Manuel","last_name":"Malatyali","full_name":"Malatyali, Manuel"},{"id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}],"title":"A Dynamic Distributed Data Structure for Top-k and k-Select Queries","doi":"10.1007/978-3-319-98355-4_18","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"}]},{"_id":"28231","department":[{"_id":"26"}],"user_id":"60046","series_title":"Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn","language":[{"iso":"ger"}],"type":"misc","status":"public","date_updated":"2022-01-06T06:57:53Z","publisher":"Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn","volume":369,"author":[{"first_name":"Eric","last_name":"Bodden","orcid":"0000-0003-3470-3647","id":"59256","full_name":"Bodden, Eric"},{"first_name":"Falko","orcid":"0000-0002-1989-1750","last_name":"Dressler","id":"48097","full_name":"Dressler, Falko"},{"id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide","first_name":"Friedhelm"},{"first_name":"Christoph","full_name":"Scheytt, Christoph","id":"37144","last_name":"Scheytt"},{"last_name":"Trächtler","id":"552","full_name":"Trächtler, Ansgar","first_name":"Ansgar"}],"date_created":"2021-12-02T11:53:20Z","title":"Intelligente technische Systeme","publication_identifier":{"isbn":["978-3-942647-88-5"]},"publication_status":"published","year":"2017","intvolume":"       369","citation":{"short":"E. Bodden, F. Dressler, F. Meyer auf der Heide, C. Scheytt, A. Trächtler, Intelligente technische Systeme, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","bibtex":"@book{Bodden_Dressler_Meyer auf der Heide_Scheytt_Trächtler_2017, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, title={Intelligente technische Systeme}, volume={369}, publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Bodden, Eric and Dressler, Falko and Meyer auf der Heide, Friedhelm and Scheytt, Christoph and Trächtler, Ansgar}, year={2017}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn} }","mla":"Bodden, Eric, et al. <i>Intelligente technische Systeme</i>. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","apa":"Bodden, E., Dressler, F., Meyer auf der Heide, F., Scheytt, C., &#38; Trächtler, A. (2017). <i>Intelligente technische Systeme</i> (Vol. 369). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn.","ama":"Bodden E, Dressler F, Meyer auf der Heide F, Scheytt C, Trächtler A. <i>Intelligente technische Systeme</i>. Vol 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn; 2017.","chicago":"Bodden, Eric, Falko Dressler, Friedhelm Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler. <i>Intelligente technische Systeme</i>. Vol. 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","ieee":"E. Bodden, F. Dressler, F. Meyer auf der Heide, C. Scheytt, and A. Trächtler, <i>Intelligente technische Systeme</i>, vol. 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017."}},{"user_id":"15931","series_title":"369","department":[{"_id":"58"}],"_id":"24221","language":[{"iso":"ger"}],"type":"book","status":"public","abstract":[{"text":"Das Wissenschaftsforum Intelligente Technische Systeme (WInTeSys) legt am 11. und 12. Mai 2017 in Paderborn den Schwerpunkt auf die Grundlagen und die Entwicklung intelligenter technischer Systeme im Kontext Industrie 4.0. Etwa 40 begutachtete hochkarätige Beiträge geben einen Überblick über Forschungsfelder, Technologien und Anwendungen. Die Veranstaltung bietet den Teilnehmerinnen und Teilnehmern eine ausgezeichnete Bühne für den Erfahrungsaustausch auf dem Weg in die Digitalisierung von Produkten und Produktionssystemen. »Das Besondere ist der Dialog von Hochschulforschung und industrieller Entwicklung, also das Aufeinandertreffen von »Science-Push« und »Application-Pull«. Die Beiträge spiegeln die hervorragende Vernetzung in der Region OWL und darüber hinaus wider«, sagt Veranstalter Prof. Jürgen Gausemeier (Heinz Nixdorf Institut, Universität Paderborn).","lang":"ger"}],"date_created":"2021-09-13T08:20:36Z","author":[{"last_name":"Gausemeier","full_name":"Gausemeier, Jürgen","first_name":"Jürgen"},{"id":"59256","full_name":"Bodden, Eric","last_name":"Bodden","orcid":"0000-0003-3470-3647","first_name":"Eric"},{"id":"48097","full_name":"Dressler, Falko","orcid":"0000-0002-1989-1750","last_name":"Dressler","first_name":"Falko"},{"first_name":"Roman","last_name":"Dumitrescu","full_name":"Dumitrescu, Roman","id":"16190"},{"full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide","first_name":"Friedhelm"},{"first_name":"Christoph","full_name":"Scheytt, Christoph","id":"37144","last_name":"Scheytt"},{"last_name":"Trächtler","full_name":"Trächtler, Ansgar","id":"552","first_name":"Ansgar"}],"volume":369,"date_updated":"2022-01-06T06:56:13Z","publisher":"Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn","doi":"10.17619/UNIPB/1-93","title":"Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)","related_material":{"link":[{"relation":"confirmation","url":"https://digital.ub.uni-paderborn.de/hs/content/titleinfo/2436759"}]},"publication_status":"published","publication_identifier":{"isbn":["978-3-942647-88-5"]},"citation":{"chicago":"Gausemeier, Jürgen, Eric Bodden, Falko Dressler, Roman Dumitrescu, Friedhelm Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Vol. 369. 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017. <a href=\"https://doi.org/10.17619/UNIPB/1-93\">https://doi.org/10.17619/UNIPB/1-93</a>.","ieee":"J. Gausemeier <i>et al.</i>, <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>, vol. 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","ama":"Gausemeier J, Bodden E, Dressler F, et al. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Vol 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn; 2017. doi:<a href=\"https://doi.org/10.17619/UNIPB/1-93\">10.17619/UNIPB/1-93</a>","bibtex":"@book{Gausemeier_Bodden_Dressler_Dumitrescu_Meyer auf der Heide_Scheytt_Trächtler_2017, series={369}, title={Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)}, volume={369}, DOI={<a href=\"https://doi.org/10.17619/UNIPB/1-93\">10.17619/UNIPB/1-93</a>}, publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Gausemeier, Jürgen and Bodden, Eric and Dressler, Falko and Dumitrescu, Roman and Meyer auf der Heide, Friedhelm and Scheytt, Christoph and Trächtler, Ansgar}, year={2017}, collection={369} }","short":"J. Gausemeier, E. Bodden, F. Dressler, R. Dumitrescu, F. Meyer auf der Heide, C. Scheytt, A. Trächtler, Wissenschaftsforum Intelligente Technische Systeme (WInTeSys), Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","mla":"Gausemeier, Jürgen, et al. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017, doi:<a href=\"https://doi.org/10.17619/UNIPB/1-93\">10.17619/UNIPB/1-93</a>.","apa":"Gausemeier, J., Bodden, E., Dressler, F., Dumitrescu, R., Meyer auf der Heide, F., Scheytt, C., &#38; Trächtler, A. (2017). <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i> (Vol. 369). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn. <a href=\"https://doi.org/10.17619/UNIPB/1-93\">https://doi.org/10.17619/UNIPB/1-93</a>"},"intvolume":"       369","year":"2017"},{"editor":[{"last_name":"Gausemeier","full_name":"Gausemeier, Jürgen","first_name":"Jürgen"},{"first_name":"Eric","full_name":"Bodden, Eric","id":"59256","orcid":"0000-0003-3470-3647","last_name":"Bodden"},{"first_name":"Falko","orcid":"0000-0002-1989-1750","last_name":"Dressler","full_name":"Dressler, Falko","id":"48097"},{"last_name":"Dumitrescu","id":"16190","full_name":"Dumitrescu, Roman","first_name":"Roman"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","full_name":"Meyer auf der Heide, Friedhelm","id":"15523"},{"id":"37144","full_name":"Scheytt, Christoph","last_name":"Scheytt","first_name":"Christoph"},{"full_name":"Trächtler, Ansgar","id":"552","last_name":"Trächtler","first_name":"Ansgar"}],"status":"public","type":"book_editor","language":[{"iso":"ger"}],"_id":"27415","user_id":"21240","department":[{"_id":"676"}],"year":"2017","place":"Paderborn","citation":{"bibtex":"@book{Gausemeier_Bodden_Dressler_Dumitrescu_Meyer auf der Heide_Scheytt_Trächtler_2017, place={Paderborn}, title={Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369}, volume={369}, publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts}, year={2017} }","mla":"Gausemeier, Jürgen, et al., editors. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369</i>. Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2017.","short":"J. Gausemeier, E. Bodden, F. Dressler, R. Dumitrescu, F. Meyer auf der Heide, C. Scheytt, A. Trächtler, eds., Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","apa":"Gausemeier, J., Bodden, E., Dressler, F., Dumitrescu, R., Meyer auf der Heide, F., Scheytt, C., &#38; Trächtler, A. (Eds.). (2017). <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369</i> (Vol. 369). Verlagsschriftenreihe des Heinz Nixdorf Instituts.","ieee":"J. Gausemeier <i>et al.</i>, Eds., <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369</i>, vol. 369. Paderborn: Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2017.","chicago":"Gausemeier, Jürgen, Eric Bodden, Falko Dressler, Roman Dumitrescu, Friedhelm Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler, eds. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369</i>. Vol. 369. Paderborn: Verlagsschriftenreihe des Heinz Nixdorf Instituts, 2017.","ama":"Gausemeier J, Bodden E, Dressler F, et al., eds. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369</i>. Vol 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts; 2017."},"intvolume":"       369","title":"Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369","date_updated":"2022-01-06T06:57:39Z","publisher":"Verlagsschriftenreihe des Heinz Nixdorf Instituts","date_created":"2021-11-15T08:34:31Z","volume":369},{"language":[{"iso":"eng"}],"department":[{"_id":"63"}],"user_id":"15415","_id":"17811","status":"public","abstract":[{"lang":"eng","text":"We consider a swarm of $n$ autonomous mobile robots, distributed on a\r\n2-dimensional grid. A basic task for such a swarm is the gathering process: All\r\nrobots have to gather at one (not predefined) place. A common local model for\r\nextremely simple robots is the following: The robots do not have a common\r\ncompass, only have a constant viewing radius, are autonomous and\r\nindistinguishable, can move at most a constant distance in each step, cannot\r\ncommunicate, are oblivious and do not have flags or states. The only gathering\r\nalgorithm under this robot model, with known runtime bounds, needs\r\n$\\mathcal{O}(n^2)$ rounds and works in the Euclidean plane. The underlying time\r\nmodel for the algorithm is the fully synchronous $\\mathcal{FSYNC}$ model. On\r\nthe other side, in the case of the 2-dimensional grid, the only known gathering\r\nalgorithms for the same time and a similar local model additionally require a\r\nconstant memory, states and \"flags\" to communicate these states to neighbors in\r\nviewing range. They gather in time $\\mathcal{O}(n)$.\r\n  In this paper we contribute the (to the best of our knowledge) first\r\ngathering algorithm on the grid that works under the same simple local model as\r\nthe above mentioned Euclidean plane strategy, i.e., without memory (oblivious),\r\n\"flags\" and states. We prove its correctness and an $\\mathcal{O}(n^2)$ time\r\nbound in the fully synchronous $\\mathcal{FSYNC}$ time model. This time bound\r\nmatches the time bound of the best known algorithm for the Euclidean plane\r\nmentioned above. We say gathering is done if all robots are located within a\r\n$2\\times 2$ square, because in $\\mathcal{FSYNC}$ such configurations cannot be\r\nsolved."}],"publication":"arXiv:1702.03400","type":"preprint","title":"Gathering Anonymous, Oblivious Robots on a Grid","author":[{"first_name":"Matthias","last_name":"Fischer","id":"146","full_name":"Fischer, Matthias"},{"first_name":"Daniel","last_name":"Jung","full_name":"Jung, Daniel","id":"37827"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","full_name":"Meyer auf der Heide, Friedhelm","id":"15523"}],"date_created":"2020-08-11T13:48:38Z","date_updated":"2022-01-06T06:53:20Z","citation":{"ama":"Fischer M, Jung D, Meyer auf der Heide F. Gathering Anonymous, Oblivious Robots on a Grid. <i>arXiv:170203400</i>. 2017.","chicago":"Fischer, Matthias, Daniel Jung, and Friedhelm Meyer auf der Heide. “Gathering Anonymous, Oblivious Robots on a Grid.” <i>ArXiv:1702.03400</i>, 2017.","ieee":"M. Fischer, D. Jung, and F. Meyer auf der Heide, “Gathering Anonymous, Oblivious Robots on a Grid,” <i>arXiv:1702.03400</i>. 2017.","apa":"Fischer, M., Jung, D., &#38; Meyer auf der Heide, F. (2017). Gathering Anonymous, Oblivious Robots on a Grid. <i>ArXiv:1702.03400</i>.","short":"M. Fischer, D. Jung, F. Meyer auf der Heide, ArXiv:1702.03400 (2017).","mla":"Fischer, Matthias, et al. “Gathering Anonymous, Oblivious Robots on a Grid.” <i>ArXiv:1702.03400</i>, 2017.","bibtex":"@article{Fischer_Jung_Meyer auf der Heide_2017, title={Gathering Anonymous, Oblivious Robots on a Grid}, journal={arXiv:1702.03400}, author={Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm}, year={2017} }"},"year":"2017"},{"author":[{"first_name":"Jürgen","full_name":"Gausemeier, Jürgen","last_name":"Gausemeier"},{"last_name":"Bodden","orcid":"0000-0003-3470-3647","id":"59256","full_name":"Bodden, Eric","first_name":"Eric"},{"first_name":"Falko","id":"48097","full_name":"Dressler, Falko","last_name":"Dressler","orcid":"0000-0002-1989-1750"},{"last_name":"Dumitrescu","id":"16190","full_name":"Dumitrescu, Roman","first_name":"Roman"},{"first_name":"Friedhelm","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide"},{"last_name":"Scheytt","full_name":"Scheytt, Christoph","first_name":"Christoph"},{"last_name":"Trächtler","id":"552","full_name":"Trächtler, Ansgar","first_name":"Ansgar"}],"date_created":"2021-08-09T05:50:16Z","volume":369,"date_updated":"2022-01-06T06:55:45Z","publisher":"Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn","title":"Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)","citation":{"chicago":"Gausemeier, Jürgen, Eric Bodden, Falko Dressler, Roman Dumitrescu, Friedhelm Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Vol. 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","ieee":"J. Gausemeier <i>et al.</i>, <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>, vol. 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","ama":"Gausemeier J, Bodden E, Dressler F, et al. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Vol 369. Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn; 2017.","apa":"Gausemeier, J., Bodden, E., Dressler, F., Dumitrescu, R., Meyer auf der Heide, F., Scheytt, C., &#38; Trächtler, A. (2017). <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i> (Vol. 369). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn.","mla":"Gausemeier, Jürgen, et al. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Vol. 369, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","short":"J. Gausemeier, E. Bodden, F. Dressler, R. Dumitrescu, F. Meyer auf der Heide, C. Scheytt, A. Trächtler, Wissenschaftsforum Intelligente Technische Systeme (WInTeSys), Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2017.","bibtex":"@book{Gausemeier_Bodden_Dressler_Dumitrescu_Meyer auf der Heide_Scheytt_Trächtler_2017, title={Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)}, volume={369}, publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Gausemeier, Jürgen and Bodden, Eric and Dressler, Falko and Dumitrescu, Roman and Meyer auf der Heide, Friedhelm and Scheytt, Christoph and Trächtler, Ansgar}, year={2017} }"},"intvolume":"       369","year":"2017","user_id":"24876","department":[{"_id":"153"}],"_id":"23010","language":[{"iso":"eng"}],"type":"book","status":"public"},{"intvolume":"     10787","page":"207-222","citation":{"apa":"Mäcker, A., Malatyali, M., Meyer auf der Heide, F., &#38; Riechers, S. (2017). Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times. In <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i> (Vol. 10787, pp. 207–222). Springer. <a href=\"https://doi.org/10.1007/978-3-319-89441-6\">https://doi.org/10.1007/978-3-319-89441-6</a>","bibtex":"@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2017, series={Lecture Notes in Computer Science}, title={Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times}, volume={10787}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-89441-6\">10.1007/978-3-319-89441-6</a>}, booktitle={Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)}, publisher={Springer}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2017}, pages={207–222}, collection={Lecture Notes in Computer Science} }","mla":"Mäcker, Alexander, et al. “Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times.” <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>, vol. 10787, Springer, 2017, pp. 207–22, doi:<a href=\"https://doi.org/10.1007/978-3-319-89441-6\">10.1007/978-3-319-89441-6</a>.","short":"A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA), Springer, 2017, pp. 207–222.","chicago":"Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times.” In <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>, 10787:207–22. Lecture Notes in Computer Science. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-89441-6\">https://doi.org/10.1007/978-3-319-89441-6</a>.","ieee":"A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times,” in <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>, 2017, vol. 10787, pp. 207–222.","ama":"Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times. In: <i>Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)</i>. Vol 10787. Lecture Notes in Computer Science. Springer; 2017:207-222. doi:<a href=\"https://doi.org/10.1007/978-3-319-89441-6\">10.1007/978-3-319-89441-6</a>"},"has_accepted_license":"1","doi":"10.1007/978-3-319-89441-6","volume":10787,"author":[{"first_name":"Alexander","full_name":"Mäcker, Alexander","id":"13536","last_name":"Mäcker"},{"first_name":"Manuel","full_name":"Malatyali, Manuel","last_name":"Malatyali"},{"last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","first_name":"Friedhelm"},{"first_name":"Sören","full_name":"Riechers, Sören","last_name":"Riechers"}],"date_updated":"2022-01-06T07:03:47Z","status":"public","type":"conference","file_date_updated":"2018-11-02T14:59:22Z","department":[{"_id":"63"}],"series_title":"Lecture Notes in Computer Science","user_id":"477","_id":"79","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt C4","_id":"16"},{"_id":"4","name":"SFB 901 - Project Area C"}],"year":"2017","title":"Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times","date_created":"2017-10-17T12:41:06Z","publisher":"Springer","file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_name":"Non-clairvoyantSchedulingToMin.pdf","file_id":"5289","access_level":"closed","file_size":380629,"creator":"ups","date_created":"2018-11-02T14:59:22Z","date_updated":"2018-11-02T14:59:22Z"}],"abstract":[{"lang":"eng","text":"Consider a problem in which $n$ jobs that are classified into $k$ types arrive over time at their release times and are to be scheduled on a single machine so as to minimize the maximum flow time.The machine requires a setup taking $s$ time units whenever it switches from processing jobs of one type to jobs of a different type.We consider the problem as an online problem where each job is only known to the scheduler as soon as it arrives and where the processing time of a job only becomes known upon its completion (non-clairvoyance).We are interested in the potential of simple ``greedy-like'' algorithms.We analyze a modification of the FIFO strategy and show its competitiveness to be $\\Theta(\\sqrt{n})$, which is optimal for the considered class of algorithms.For $k=2$ types it achieves a constant competitiveness.Our main insight is obtained by an analysis of the smoothed competitiveness.If processing times $p_j$ are independently perturbed to $\\hat p_j = (1+X_j)p_j$, we obtain a competitiveness of $O(\\sigma^{-2} \\log^2 n)$ when $X_j$ is drawn from a uniform or a (truncated) normal distribution with standard deviation $\\sigma$.The result proves that bad instances are fragile and ``practically'' one might expect a much better performance than given by the $\\Omega(\\sqrt{n})$-bound."}],"publication":"Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)","language":[{"iso":"eng"}],"ddc":["000"]},{"series_title":"LNCS","user_id":"477","department":[{"_id":"63"}],"project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"_id":"82","file_date_updated":"2018-11-02T15:07:35Z","language":[{"iso":"eng"}],"ddc":["000"],"type":"conference","publication":"Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)","file":[{"date_updated":"2018-11-02T15:07:35Z","creator":"ups","date_created":"2018-11-02T15:07:35Z","file_size":238276,"file_id":"5294","access_level":"closed","file_name":"Modular-WidthAnAuxiliaryParame.pdf","content_type":"application/pdf","success":1,"relation":"main_file"}],"status":"public","abstract":[{"lang":"eng","text":"Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter."}],"date_created":"2017-10-17T12:41:07Z","author":[{"first_name":"Faisal N.","full_name":"Abu-Khzam, Faisal N.","last_name":"Abu-Khzam"},{"last_name":"Li","full_name":"Li, Shouwei","first_name":"Shouwei"},{"first_name":"Christine","last_name":"Markarian","full_name":"Markarian, Christine","id":"37612"},{"id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide","first_name":"Friedhelm"},{"last_name":"Podlipyan","full_name":"Podlipyan, Pavel","first_name":"Pavel"}],"date_updated":"2022-01-06T07:03:52Z","doi":"10.1007/978-3-319-59605-1_13","title":"Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity","has_accepted_license":"1","citation":{"mla":"Abu-Khzam, Faisal N., et al. “Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity.” <i>Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)</i>, 2017, pp. 139–50, doi:<a href=\"https://doi.org/10.1007/978-3-319-59605-1_13\">10.1007/978-3-319-59605-1_13</a>.","short":"F.N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan, in: Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW), 2017, pp. 139–150.","bibtex":"@inproceedings{Abu-Khzam_Li_Markarian_Meyer auf der Heide_Podlipyan_2017, series={LNCS}, title={Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-59605-1_13\">10.1007/978-3-319-59605-1_13</a>}, booktitle={Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)}, author={Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2017}, pages={139–150}, collection={LNCS} }","apa":"Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., &#38; Podlipyan, P. (2017). Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity. In <i>Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)</i> (pp. 139–150). <a href=\"https://doi.org/10.1007/978-3-319-59605-1_13\">https://doi.org/10.1007/978-3-319-59605-1_13</a>","chicago":"Abu-Khzam, Faisal N., Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, and Pavel Podlipyan. “Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity.” In <i>Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)</i>, 139–50. LNCS, 2017. <a href=\"https://doi.org/10.1007/978-3-319-59605-1_13\">https://doi.org/10.1007/978-3-319-59605-1_13</a>.","ieee":"F. N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, and P. Podlipyan, “Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity,” in <i>Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)</i>, 2017, pp. 139–150.","ama":"Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity. In: <i>Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)</i>. LNCS. ; 2017:139-150. doi:<a href=\"https://doi.org/10.1007/978-3-319-59605-1_13\">10.1007/978-3-319-59605-1_13</a>"},"page":"139-150","year":"2017"},{"date_created":"2017-10-17T12:41:05Z","author":[{"first_name":"Björn","last_name":"Feldkord","full_name":"Feldkord, Björn","id":"22704"},{"full_name":"Markarian, Christine","id":"37612","last_name":"Markarian","first_name":"Christine"},{"first_name":"Friedhelm","full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide"}],"date_updated":"2022-01-06T07:03:26Z","doi":"10.1007/978-3-319-71147-8_2","title":"Price Fluctuations in Online Leasing","has_accepted_license":"1","citation":{"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.","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>.","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>","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.","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>.","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>"},"page":"17 - 31","year":"2017","user_id":"477","department":[{"_id":"63"}],"project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"70","file_date_updated":"2018-11-02T15:06:13Z","language":[{"iso":"eng"}],"ddc":["000"],"type":"conference","publication":"Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)","file":[{"creator":"ups","date_created":"2018-11-02T15:06:13Z","date_updated":"2018-11-02T15:06:13Z","file_name":"PriceFluctuationInOnlineLeasin.pdf","file_id":"5293","access_level":"closed","file_size":287315,"content_type":"application/pdf","relation":"main_file","success":1}],"status":"public"},{"publication":"Journal of Combinatorial Optimization","file":[{"content_type":"application/pdf","relation":"main_file","success":1,"creator":"florida","date_created":"2018-03-14T12:21:34Z","date_updated":"2018-03-14T12:21:34Z","access_level":"closed","file_id":"1210","file_name":"706-chp_3A10.1007_2F978-3-319-48749-6_42.pdf","file_size":608614}],"ddc":["040"],"language":[{"iso":"eng"}],"issue":"4","year":"2017","publisher":"Springer","date_created":"2017-11-15T10:21:34Z","title":"Cost-efficient Scheduling on Machines from the Cloud","type":"journal_article","status":"public","_id":"706","project":[{"name":"SFB 901","_id":"1"},{"_id":"16","name":"SFB 901 - Subprojekt C4"},{"name":"SFB 901 - Project Area C","_id":"4"}],"department":[{"_id":"63"}],"user_id":"15415","file_date_updated":"2018-03-14T12:21:34Z","has_accepted_license":"1","intvolume":"        36","page":"1168-1194","citation":{"ama":"Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Cost-efficient Scheduling on Machines from the Cloud. <i>Journal of Combinatorial Optimization</i>. 2017;36(4):1168-1194. doi:<a href=\"https://doi.org/10.1007/s10878-017-0198-x\">10.1007/s10878-017-0198-x</a>","chicago":"Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Cost-Efficient Scheduling on Machines from the Cloud.” <i>Journal of Combinatorial Optimization</i> 36, no. 4 (2017): 1168–94. <a href=\"https://doi.org/10.1007/s10878-017-0198-x\">https://doi.org/10.1007/s10878-017-0198-x</a>.","ieee":"A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient Scheduling on Machines from the Cloud,” <i>Journal of Combinatorial Optimization</i>, vol. 36, no. 4, pp. 1168–1194, 2017.","short":"A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, Journal of Combinatorial Optimization 36 (2017) 1168–1194.","bibtex":"@article{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2017, title={Cost-efficient Scheduling on Machines from the Cloud}, volume={36}, DOI={<a href=\"https://doi.org/10.1007/s10878-017-0198-x\">10.1007/s10878-017-0198-x</a>}, number={4}, journal={Journal of Combinatorial Optimization}, publisher={Springer}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2017}, pages={1168–1194} }","mla":"Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.” <i>Journal of Combinatorial Optimization</i>, vol. 36, no. 4, Springer, 2017, pp. 1168–94, doi:<a href=\"https://doi.org/10.1007/s10878-017-0198-x\">10.1007/s10878-017-0198-x</a>.","apa":"Mäcker, A., Malatyali, M., Meyer auf der Heide, F., &#38; Riechers, S. (2017). Cost-efficient Scheduling on Machines from the Cloud. <i>Journal of Combinatorial Optimization</i>, <i>36</i>(4), 1168–1194. <a href=\"https://doi.org/10.1007/s10878-017-0198-x\">https://doi.org/10.1007/s10878-017-0198-x</a>"},"date_updated":"2022-01-06T07:03:27Z","volume":36,"author":[{"full_name":"Mäcker, Alexander","id":"13536","last_name":"Mäcker","first_name":"Alexander"},{"full_name":"Malatyali, Manuel","last_name":"Malatyali","first_name":"Manuel"},{"first_name":"Friedhelm","full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide"},{"full_name":"Riechers, Sören","last_name":"Riechers","first_name":"Sören"}],"doi":"10.1007/s10878-017-0198-x"},{"ddc":["000"],"file_date_updated":"2018-11-02T14:55:10Z","language":[{"iso":"eng"}],"_id":"55","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"63"}],"user_id":"477","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":[{"date_updated":"2018-11-02T14:55:10Z","creator":"ups","date_created":"2018-11-02T14:55:10Z","file_size":691691,"access_level":"closed","file_name":"p313-feldkord.pdf","file_id":"5288","content_type":"application/pdf","success":1,"relation":"main_file"}],"publication":"Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","type":"conference","title":"The Mobile Server Problem","doi":"10.1145/3087556.3087575","date_updated":"2022-01-06T07:01:56Z","date_created":"2017-10-17T12:41:02Z","author":[{"last_name":"Feldkord","full_name":"Feldkord, Björn","id":"22704","first_name":"Björn"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm"}],"year":"2017","page":"313-319","citation":{"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>.","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>","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} }","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>.","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.","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>"},"has_accepted_license":"1"},{"page":"369","citation":{"bibtex":"@book{Gausemeier_Bodden_ Dressler_Dumitrescu_Meyer auf der Heide_Scheytt_Trächtler_2017, place={Paderborn}, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title={Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)}, author={Gausemeier, Jürgen and Bodden, Eric and  Dressler, Falko and Dumitrescu, Roman and Meyer auf der Heide, Friedhelm and Scheytt, Christoph and Trächtler, Ansgar}, year={2017}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}} }","short":"J. Gausemeier, E. Bodden, F.  Dressler, R. Dumitrescu, F. Meyer auf der Heide, C. Scheytt, A. Trächtler, Wissenschaftsforum Intelligente Technische Systeme (WInTeSys), Paderborn, 2017.","mla":"Gausemeier, Jürgen, et al. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. 2017.","apa":"Gausemeier, J., Bodden, E.,  Dressler, F., Dumitrescu, R., Meyer auf der Heide, F., Scheytt, C., &#38; Trächtler, A. (2017). <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Paderborn.","ama":"Gausemeier J, Bodden E,  Dressler F, et al. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Paderborn; 2017.","ieee":"J. Gausemeier <i>et al.</i>, <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Paderborn, 2017.","chicago":"Gausemeier, Jürgen, Eric Bodden, Falko  Dressler, Roman Dumitrescu, Friedhelm Meyer auf der Heide, Christoph Scheytt, and Ansgar Trächtler. <i>Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)</i>. Verlagsschriftenreihe Des Heinz Nixdorf Instituts, Paderborn}. Paderborn, 2017."},"place":"Paderborn","year":"2017","publication_status":"published","title":"Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)","author":[{"last_name":"Gausemeier","full_name":"Gausemeier, Jürgen","first_name":"Jürgen"},{"first_name":"Eric","last_name":"Bodden","full_name":"Bodden, Eric"},{"last_name":" Dressler","full_name":" Dressler, Falko","first_name":"Falko"},{"first_name":"Roman","last_name":"Dumitrescu","full_name":"Dumitrescu, Roman"},{"full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide","first_name":"Friedhelm"},{"first_name":"Christoph","last_name":"Scheytt","full_name":"Scheytt, Christoph"},{"full_name":"Trächtler, Ansgar","last_name":"Trächtler","first_name":"Ansgar"}],"date_created":"2020-04-07T06:36:06Z","date_updated":"2022-01-06T06:52:50Z","status":"public","type":"book","language":[{"iso":"eng"}],"department":[{"_id":"63"}],"user_id":"15415","series_title":"Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}","_id":"16444"},{"title":"Monitoring of Domain-Related Problems in Distributed Data Streams","doi":"10.1007/978-3-319-72050-0_13","date_updated":"2022-01-06T06:52:50Z","date_created":"2020-04-08T07:20:20Z","author":[{"first_name":"Pascal","last_name":"Bemmann","full_name":"Bemmann, Pascal"},{"first_name":"Felix","last_name":"Biermeier","full_name":"Biermeier, Felix"},{"last_name":"Bürmann","full_name":"Bürmann, Jan","first_name":"Jan"},{"first_name":"Arne","last_name":"Kemper","full_name":"Kemper, Arne"},{"first_name":"Till","orcid":"0000-0003-2014-4696","last_name":"Knollmann","id":"39241","full_name":"Knollmann, Till"},{"first_name":"Steffen","full_name":"Knorr, Steffen","last_name":"Knorr"},{"last_name":"Kothe","full_name":"Kothe, Nils","first_name":"Nils"},{"full_name":"Mäcker, Alexander","id":"13536","last_name":"Mäcker","first_name":"Alexander"},{"first_name":"Manuel","full_name":"Malatyali, Manuel","id":"41265","last_name":"Malatyali"},{"id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide","first_name":"Friedhelm"},{"first_name":"Sören","full_name":"Riechers, Sören","last_name":"Riechers"},{"first_name":"Johannes Sebastian","full_name":"Schaefer, Johannes Sebastian","id":"30291","last_name":"Schaefer"},{"first_name":"Jannik","id":"38705","full_name":"Sundermeier, Jannik","last_name":"Sundermeier"}],"place":"Cham","year":"2017","citation":{"apa":"Bemmann, P., Biermeier, F., Bürmann, J., Kemper, A., Knollmann, T., Knorr, S., Kothe, N., Mäcker, A., Malatyali, M., Meyer auf der Heide, F., Riechers, S., Schaefer, J. S., &#38; Sundermeier, J. (2017). Monitoring of Domain-Related Problems in Distributed Data Streams. In <i>Structural Information and Communication Complexity</i>. <a href=\"https://doi.org/10.1007/978-3-319-72050-0_13\">https://doi.org/10.1007/978-3-319-72050-0_13</a>","short":"P. Bemmann, F. Biermeier, J. Bürmann, A. Kemper, T. Knollmann, S. Knorr, N. Kothe, A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, J.S. Schaefer, J. Sundermeier, in: Structural Information and Communication Complexity, Cham, 2017.","bibtex":"@inbook{Bemmann_Biermeier_Bürmann_Kemper_Knollmann_Knorr_Kothe_Mäcker_Malatyali_Meyer auf der Heide_et al._2017, place={Cham}, title={Monitoring of Domain-Related Problems in Distributed Data Streams}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-72050-0_13\">10.1007/978-3-319-72050-0_13</a>}, booktitle={Structural Information and Communication Complexity}, author={Bemmann, Pascal and Biermeier, Felix and Bürmann, Jan and Kemper, Arne and Knollmann, Till and Knorr, Steffen and Kothe, Nils and Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and et al.}, year={2017} }","mla":"Bemmann, Pascal, et al. “Monitoring of Domain-Related Problems in Distributed Data Streams.” <i>Structural Information and Communication Complexity</i>, 2017, doi:<a href=\"https://doi.org/10.1007/978-3-319-72050-0_13\">10.1007/978-3-319-72050-0_13</a>.","ama":"Bemmann P, Biermeier F, Bürmann J, et al. Monitoring of Domain-Related Problems in Distributed Data Streams. In: <i>Structural Information and Communication Complexity</i>. ; 2017. doi:<a href=\"https://doi.org/10.1007/978-3-319-72050-0_13\">10.1007/978-3-319-72050-0_13</a>","chicago":"Bemmann, Pascal, Felix Biermeier, Jan Bürmann, Arne Kemper, Till Knollmann, Steffen Knorr, Nils Kothe, et al. “Monitoring of Domain-Related Problems in Distributed Data Streams.” In <i>Structural Information and Communication Complexity</i>. Cham, 2017. <a href=\"https://doi.org/10.1007/978-3-319-72050-0_13\">https://doi.org/10.1007/978-3-319-72050-0_13</a>.","ieee":"P. Bemmann <i>et al.</i>, “Monitoring of Domain-Related Problems in Distributed Data Streams,” in <i>Structural Information and Communication Complexity</i>, Cham, 2017."},"publication_status":"published","publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["9783319720494","9783319720500"]},"language":[{"iso":"eng"}],"_id":"16461","external_id":{"arxiv":["arXiv:1706.03568 "]},"user_id":"15415","department":[{"_id":"63"}],"status":"public","type":"book_chapter","publication":"Structural Information and Communication Complexity"},{"department":[{"_id":"63"}],"series_title":"Lecture Notes in Computer Science","user_id":"15415","_id":"16347","language":[{"iso":"eng"}],"publication":"Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}","type":"conference","status":"public","editor":[{"first_name":"Antonio","full_name":"Fernández Anta, Antonio","last_name":"Fernández Anta"},{"full_name":"Jurdzinski, Tomasz","last_name":"Jurdzinski","first_name":"Tomasz"},{"first_name":"Miguel A.","last_name":"Mosteiro","full_name":"Mosteiro, Miguel A."},{"full_name":"Zhang, Yanyong","last_name":"Zhang","first_name":"Yanyong"}],"volume":10718,"date_created":"2020-03-27T14:32:39Z","author":[{"first_name":"Matthias","last_name":"Fischer","full_name":"Fischer, Matthias","id":"146"},{"full_name":"Jung, Daniel","id":"37827","last_name":"Jung","first_name":"Daniel"},{"full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}],"date_updated":"2022-01-06T06:52:49Z","publisher":"Springer","doi":"10.1007/978-3-319-72751-6_13","title":"Gathering Anonymous, Oblivious Robots on a Grid","page":"168-181","intvolume":"     10718","citation":{"bibtex":"@inproceedings{Fischer_Jung_Meyer auf der Heide_2017, place={Vienna, Austria}, series={Lecture Notes in Computer Science}, title={Gathering Anonymous, Oblivious Robots on a Grid}, volume={10718}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-72751-6_13\">10.1007/978-3-319-72751-6_13</a>}, booktitle={Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}}, publisher={Springer}, author={Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm}, editor={Fernández Anta, Antonio and Jurdzinski, Tomasz and Mosteiro, Miguel A. and Zhang, YanyongEditors}, year={2017}, pages={168–181}, collection={Lecture Notes in Computer Science} }","mla":"Fischer, Matthias, et al. “Gathering Anonymous, Oblivious Robots on a Grid.” <i>Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}</i>, edited by Antonio Fernández Anta et al., vol. 10718, Springer, 2017, pp. 168–81, doi:<a href=\"https://doi.org/10.1007/978-3-319-72751-6_13\">10.1007/978-3-319-72751-6_13</a>.","short":"M. Fischer, D. Jung, F. Meyer auf der Heide, in: A. Fernández Anta, T. Jurdzinski, M.A. Mosteiro, Y. Zhang (Eds.), Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}, Springer, Vienna, Austria, 2017, pp. 168–181.","apa":"Fischer, M., Jung, D., &#38; Meyer auf der Heide, F. (2017). Gathering Anonymous, Oblivious Robots on a Grid. In A. Fernández Anta, T. Jurdzinski, M. A. Mosteiro, &#38; Y. Zhang (Eds.), <i>Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}</i> (Vol. 10718, pp. 168–181). Vienna, Austria: Springer. <a href=\"https://doi.org/10.1007/978-3-319-72751-6_13\">https://doi.org/10.1007/978-3-319-72751-6_13</a>","chicago":"Fischer, Matthias, Daniel Jung, and Friedhelm Meyer auf der Heide. “Gathering Anonymous, Oblivious Robots on a Grid.” In <i>Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}</i>, edited by Antonio Fernández Anta, Tomasz Jurdzinski, Miguel A. Mosteiro, and Yanyong Zhang, 10718:168–81. Lecture Notes in Computer Science. Vienna, Austria: Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-72751-6_13\">https://doi.org/10.1007/978-3-319-72751-6_13</a>.","ieee":"M. Fischer, D. Jung, and F. Meyer auf der Heide, “Gathering Anonymous, Oblivious Robots on a Grid,” in <i>Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}</i>, 2017, vol. 10718, pp. 168–181.","ama":"Fischer M, Jung D, Meyer auf der Heide F. Gathering Anonymous, Oblivious Robots on a Grid. In: Fernández Anta A, Jurdzinski T, Mosteiro MA, Zhang Y, eds. <i>Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}</i>. Vol 10718. Lecture Notes in Computer Science. Vienna, Austria: Springer; 2017:168-181. doi:<a href=\"https://doi.org/10.1007/978-3-319-72751-6_13\">10.1007/978-3-319-72751-6_13</a>"},"place":"Vienna, Austria","year":"2017"},{"status":"public","publication":"Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)","type":"conference","language":[{"iso":"eng"}],"_id":"16348","department":[{"_id":"63"}],"user_id":"15415","year":"2017","page":"285 - 300","citation":{"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>.","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} }","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.","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>.","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>"},"title":"A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries","doi":"10.1007/978-3-319-89441-6_21","publisher":"Springer","date_updated":"2022-01-06T06:52:49Z","date_created":"2020-03-30T09:25:18Z","author":[{"full_name":"Biermeier, Felix","last_name":"Biermeier","first_name":"Felix"},{"first_name":"Björn","last_name":"Feldkord","id":"22704","full_name":"Feldkord, Björn"},{"first_name":"Manuel","last_name":"Malatyali","full_name":"Malatyali, Manuel"},{"id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}]},{"status":"public","publication":"Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)","type":"conference","language":[{"iso":"eng"}],"department":[{"_id":"63"}],"user_id":"15415","_id":"16349","page":"182-197","citation":{"short":"P. Podlipyan, S. Li, C. Markarian, F. Meyer auf der Heide, in: Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS), 2017, pp. 182–197.","bibtex":"@inproceedings{Podlipyan_Li_Markarian_Meyer auf der Heide_2017, title={A Continuous Strategy for Collisionless Gathering}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-72751-6_14 \">10.1007/978-3-319-72751-6_14 </a>}, booktitle={Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)}, author={Podlipyan, Pavel and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm}, year={2017}, pages={182–197} }","mla":"Podlipyan, Pavel, et al. “A Continuous Strategy for Collisionless Gathering.” <i>Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)</i>, 2017, pp. 182–97, doi:<a href=\"https://doi.org/10.1007/978-3-319-72751-6_14 \">10.1007/978-3-319-72751-6_14 </a>.","apa":"Podlipyan, P., Li, S., Markarian, C., &#38; Meyer auf der Heide, F. (2017). A Continuous Strategy for Collisionless Gathering. In <i>Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)</i> (pp. 182–197). <a href=\"https://doi.org/10.1007/978-3-319-72751-6_14 \">https://doi.org/10.1007/978-3-319-72751-6_14 </a>","ama":"Podlipyan P, Li S, Markarian C, Meyer auf der Heide F. A Continuous Strategy for Collisionless Gathering. In: <i>Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)</i>. ; 2017:182-197. doi:<a href=\"https://doi.org/10.1007/978-3-319-72751-6_14 \">10.1007/978-3-319-72751-6_14 </a>","ieee":"P. Podlipyan, S. Li, C. Markarian, and F. Meyer auf der Heide, “A Continuous Strategy for Collisionless Gathering,” in <i>Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)</i>, 2017, pp. 182–197.","chicago":"Podlipyan, Pavel, Shouwei Li, Christine Markarian, and Friedhelm Meyer auf der Heide. “A Continuous Strategy for Collisionless Gathering.” In <i>Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)</i>, 182–97, 2017. <a href=\"https://doi.org/10.1007/978-3-319-72751-6_14 \">https://doi.org/10.1007/978-3-319-72751-6_14 </a>."},"year":"2017","doi":"10.1007/978-3-319-72751-6_14 ","title":"A Continuous Strategy for Collisionless Gathering","date_created":"2020-03-30T09:43:05Z","author":[{"full_name":"Podlipyan, Pavel","last_name":"Podlipyan","first_name":"Pavel"},{"last_name":"Li","full_name":"Li, Shouwei","first_name":"Shouwei"},{"first_name":"Christine","full_name":"Markarian, Christine","id":"37612","last_name":"Markarian"},{"full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}],"date_updated":"2022-01-06T06:52:49Z"},{"doi":"10.1007/978-3-319-48749-6_35","title":"On the Parameterized Parallel Complexity and the Vertex Cover Problem","author":[{"last_name":"Abu-Khzam","full_name":"Abu-Khzam, Faisal N.","first_name":"Faisal N."},{"full_name":"Li, Shouwei","last_name":"Li","first_name":"Shouwei"},{"first_name":"Christine","last_name":"Markarian","full_name":"Markarian, Christine","id":"37612"},{"id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide","first_name":"Friedhelm"},{"full_name":"Podlipyan, Pavel","last_name":"Podlipyan","first_name":"Pavel"}],"date_created":"2017-10-17T12:41:26Z","date_updated":"2022-01-06T06:53:17Z","page":"477-488","citation":{"ama":"Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. On the Parameterized Parallel Complexity and the Vertex Cover Problem. In: <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i>. LNCS. ; 2016:477-488. doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">10.1007/978-3-319-48749-6_35</a>","ieee":"F. N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, and P. Podlipyan, “On the Parameterized Parallel Complexity and the Vertex Cover Problem,” in <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 477–488.","chicago":"Abu-Khzam, Faisal N., Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, and Pavel Podlipyan. “On the Parameterized Parallel Complexity and the Vertex Cover Problem.” In <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 477–88. LNCS, 2016. <a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">https://doi.org/10.1007/978-3-319-48749-6_35</a>.","apa":"Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., &#38; Podlipyan, P. (2016). On the Parameterized Parallel Complexity and the Vertex Cover Problem. In <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i> (pp. 477–488). <a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">https://doi.org/10.1007/978-3-319-48749-6_35</a>","short":"F.N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan, in: Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 477–488.","mla":"Abu-Khzam, Faisal N., et al. “On the Parameterized Parallel Complexity and the Vertex Cover Problem.” <i>Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 477–88, doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">10.1007/978-3-319-48749-6_35</a>.","bibtex":"@inproceedings{Abu-Khzam_Li_Markarian_Meyer auf der Heide_Podlipyan_2016, series={LNCS}, title={On the Parameterized Parallel Complexity and the Vertex Cover Problem}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-48749-6_35\">10.1007/978-3-319-48749-6_35</a>}, booktitle={Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)}, author={Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2016}, pages={477–488}, collection={LNCS} }"},"year":"2016","has_accepted_license":"1","language":[{"iso":"eng"}],"file_date_updated":"2018-11-02T14:15:18Z","ddc":["000"],"department":[{"_id":"63"}],"series_title":"LNCS","user_id":"477","_id":"177","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"status":"public","file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-11-02T14:15:18Z","date_created":"2018-11-02T14:15:18Z","creator":"ups","file_size":293345,"file_name":"OnTheParameterizedParallelComp.pdf","access_level":"closed","file_id":"5266"}],"abstract":[{"text":"Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known k-vertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using O(m) instead of O(n2) parallel processors, the running time improves from 4logn+O(kk) to O(k⋅log3n), where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus.","lang":"eng"}],"publication":"Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)","type":"conference"},{"title":"Introduction to the Special Issue on SPAA 2014","doi":"10.1145/2936716","date_updated":"2022-01-06T06:53:51Z","date_created":"2017-10-17T12:41:28Z","year":"2016","citation":{"chicago":"Meyer auf der Heide, Friedhelm, ed. <i>Introduction to the Special Issue on SPAA 2014</i>. <i>Transactions on Parallel Computing (TOPC)</i>, 2016. <a href=\"https://doi.org/10.1145/2936716\">https://doi.org/10.1145/2936716</a>.","ieee":"F. Meyer auf der Heide, Ed., <i>Introduction to the Special Issue on SPAA 2014</i>, no. 1. 2016.","ama":"Meyer auf der Heide F, ed. <i>Introduction to the Special Issue on SPAA 2014</i>.; 2016. doi:<a href=\"https://doi.org/10.1145/2936716\">10.1145/2936716</a>","bibtex":"@book{Meyer auf der Heide_2016, title={Introduction to the Special Issue on SPAA 2014}, DOI={<a href=\"https://doi.org/10.1145/2936716\">10.1145/2936716</a>}, number={1}, journal={Transactions on Parallel Computing (TOPC)}, year={2016} }","mla":"Meyer auf der Heide, Friedhelm, editor. “Introduction to the Special Issue on SPAA 2014.” <i>Transactions on Parallel Computing (TOPC)</i>, no. 1, 2016, doi:<a href=\"https://doi.org/10.1145/2936716\">10.1145/2936716</a>.","short":"F. Meyer auf der Heide, ed., Introduction to the Special Issue on SPAA 2014, 2016.","apa":"Meyer auf der Heide, F. (Ed.). (2016). <i>Introduction to the Special Issue on SPAA 2014</i>. <i>Transactions on Parallel Computing (TOPC)</i>. <a href=\"https://doi.org/10.1145/2936716\">https://doi.org/10.1145/2936716</a>"},"page":"1","has_accepted_license":"1","issue":"1","ddc":["040"],"file_date_updated":"2018-03-21T12:31:42Z","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"187","user_id":"15504","department":[{"_id":"63"}],"editor":[{"first_name":"Friedhelm","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide"}],"file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-21T12:31:42Z","date_created":"2018-03-21T12:31:42Z","creator":"florida","file_size":34053,"file_id":"1531","access_level":"closed","file_name":"187-a1-heide.pdf"}],"status":"public","type":"journal_editor","publication":"Transactions on Parallel Computing (TOPC)"},{"has_accepted_license":"1","page":"578--592","citation":{"short":"A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 578--592.","bibtex":"@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2016, title={Cost-efficient Scheduling on Machines from the Cloud}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-48749-6_42\">10.1007/978-3-319-48749-6_42</a>}, booktitle={Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2016}, pages={578--592} }","mla":"Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.” <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 578--592, doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_42\">10.1007/978-3-319-48749-6_42</a>.","apa":"Mäcker, A., Malatyali, M., Meyer auf der Heide, F., &#38; Riechers, S. (2016). Cost-efficient Scheduling on Machines from the Cloud. In <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i> (pp. 578--592). <a href=\"https://doi.org/10.1007/978-3-319-48749-6_42\">https://doi.org/10.1007/978-3-319-48749-6_42</a>","ama":"Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Cost-efficient Scheduling on Machines from the Cloud. In: <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>. ; 2016:578--592. doi:<a href=\"https://doi.org/10.1007/978-3-319-48749-6_42\">10.1007/978-3-319-48749-6_42</a>","ieee":"A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient Scheduling on Machines from the Cloud,” in <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2016, pp. 578--592.","chicago":"Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Cost-Efficient Scheduling on Machines from the Cloud.” In <i>Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>, 578--592, 2016. <a href=\"https://doi.org/10.1007/978-3-319-48749-6_42\">https://doi.org/10.1007/978-3-319-48749-6_42</a>."},"year":"2016","author":[{"first_name":"Alexander","last_name":"Mäcker","full_name":"Mäcker, Alexander","id":"13536"},{"full_name":"Malatyali, Manuel","last_name":"Malatyali","first_name":"Manuel"},{"full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide","first_name":"Friedhelm"},{"first_name":"Sören","last_name":"Riechers","full_name":"Riechers, Sören"}],"date_created":"2017-10-17T12:41:32Z","date_updated":"2022-01-06T06:54:33Z","doi":"10.1007/978-3-319-48749-6_42","title":"Cost-efficient Scheduling on Machines from the Cloud","publication":"Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)","type":"conference","status":"public","file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-11-02T14:18:51Z","creator":"ups","date_created":"2018-11-02T14:18:51Z","file_size":608614,"file_name":"Cost-EfficientSchedulingOnMach.pdf","access_level":"closed","file_id":"5268"}],"abstract":[{"lang":"eng","text":"We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have machine-type dependent sizes and have individual deadlines. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. Since we observe the slack of jobs to have a fundamental influence on the competitiveness, we study the model when instances are parameterized by their (minimum) slack. An instance is called to have a slack of $\\beta$ if, for all jobs, the difference between the job's release time and the latest point in time at which it needs to be started is at least $\\beta$. While for $\\beta series = {LNCS}"}],"department":[{"_id":"63"}],"user_id":"477","_id":"207","project":[{"name":"SFB 901","_id":"1"},{"_id":"16","name":"SFB 901 - Subprojekt C4"},{"name":"SFB 901 - Project Area C","_id":"4"}],"language":[{"iso":"eng"}],"file_date_updated":"2018-11-02T14:18:51Z","ddc":["000"]}]