[{"title":"Multilevel Network Games","date_created":"2017-10-17T12:42:09Z","year":"2014","ddc":["040"],"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We consider a multilevel network game, where nodes can improvetheir communication costs by connecting to a high-speed network.The n nodes are connected by a static network and each node can decideindividually to become a gateway to the high-speed network. The goalof a node v is to minimize its private costs, i.e., the sum (SUM-game) ormaximum (MAX-game) of communication distances from v to all othernodes plus a fixed price α > 0 if it decides to be a gateway. Between gatewaysthe communication distance is 0, and gateways also improve othernodes’ distances by behaving as shortcuts. For the SUM-game, we showthat for α ≤ n − 1, the price of anarchy is Θ (n/√α) and in this rangeequilibria always exist. In range α ∈ (n−1, n(n−1)) the price of anarchyis Θ(√α), and for α ≥ n(n − 1) it is constant. For the MAX-game, weshow that the price of anarchy is either Θ (1 + n/√α), for α ≥ 1, orelse 1. Given a graph with girth of at least 4α, equilibria always exist.Concerning the dynamics, both games are not potential games. For theSUM-game, we even show that it is not weakly acyclic."}],"file":[{"file_name":"395-WINE2014ACJS.pdf","file_id":"1382","access_level":"closed","file_size":161479,"date_created":"2018-03-20T06:59:20Z","creator":"florida","date_updated":"2018-03-20T06:59:20Z","relation":"main_file","success":1,"content_type":"application/pdf"}],"publication":"Proceedings of the 10th International Conference on Web and Internet Economics (WINE)","doi":"10.1007/978-3-319-13129-0_36","date_updated":"2022-01-06T06:59:59Z","author":[{"first_name":"Sebastian","last_name":"Abshoff","full_name":"Abshoff, Sebastian"},{"first_name":"Andreas","last_name":"Cord-Landwehr","full_name":"Cord-Landwehr, Andreas"},{"first_name":"Daniel","full_name":"Jung, Daniel","id":"37827","last_name":"Jung"},{"id":"40384","full_name":"Skopalik, Alexander","last_name":"Skopalik","first_name":"Alexander"}],"citation":{"chicago":"Abshoff, Sebastian, Andreas Cord-Landwehr, Daniel Jung, and Alexander Skopalik. “Multilevel Network Games.” In <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i>, 435–40. LNCS, 2014. <a href=\"https://doi.org/10.1007/978-3-319-13129-0_36\">https://doi.org/10.1007/978-3-319-13129-0_36</a>.","ieee":"S. Abshoff, A. Cord-Landwehr, D. Jung, and A. Skopalik, “Multilevel Network Games,” in <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i>, 2014, pp. 435–440.","ama":"Abshoff S, Cord-Landwehr A, Jung D, Skopalik A. Multilevel Network Games. In: <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i>. LNCS. ; 2014:435-440. doi:<a href=\"https://doi.org/10.1007/978-3-319-13129-0_36\">10.1007/978-3-319-13129-0_36</a>","mla":"Abshoff, Sebastian, et al. “Multilevel Network Games.” <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i>, 2014, pp. 435–40, doi:<a href=\"https://doi.org/10.1007/978-3-319-13129-0_36\">10.1007/978-3-319-13129-0_36</a>.","short":"S. Abshoff, A. Cord-Landwehr, D. Jung, A. Skopalik, in: Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 2014, pp. 435–440.","bibtex":"@inproceedings{Abshoff_Cord-Landwehr_Jung_Skopalik_2014, series={LNCS}, title={Multilevel Network Games}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-13129-0_36\">10.1007/978-3-319-13129-0_36</a>}, booktitle={Proceedings of the 10th International Conference on Web and Internet Economics (WINE)}, author={Abshoff, Sebastian and Cord-Landwehr, Andreas and Jung, Daniel and Skopalik, Alexander}, year={2014}, pages={435–440}, collection={LNCS} }","apa":"Abshoff, S., Cord-Landwehr, A., Jung, D., &#38; Skopalik, A. (2014). Multilevel Network Games. In <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i> (pp. 435–440). <a href=\"https://doi.org/10.1007/978-3-319-13129-0_36\">https://doi.org/10.1007/978-3-319-13129-0_36</a>"},"page":"435-440","has_accepted_license":"1","file_date_updated":"2018-03-20T06:59:20Z","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A3","_id":"7"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"395","user_id":"15415","series_title":"LNCS","department":[{"_id":"63"},{"_id":"541"}],"status":"public","type":"conference"},{"has_accepted_license":"1","citation":{"ieee":"C. Scheideler, M. Eikel, and A. Setzer, “Minimum Linear Arrangement of Series-Parallel Graphs,” in <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i>, 2014, pp. 168--180.","chicago":"Scheideler, Christian, Martina Eikel, and Alexander Setzer. “Minimum Linear Arrangement of Series-Parallel Graphs.” In <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i>, 168--180. LNCS, 2014.","ama":"Scheideler C, Eikel M, Setzer A. Minimum Linear Arrangement of Series-Parallel Graphs. In: <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i>. LNCS. ; 2014:168--180.","apa":"Scheideler, C., Eikel, M., &#38; Setzer, A. (2014). Minimum Linear Arrangement of Series-Parallel Graphs. In <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i> (pp. 168--180).","mla":"Scheideler, Christian, et al. “Minimum Linear Arrangement of Series-Parallel Graphs.” <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i>, 2014, pp. 168--180.","short":"C. Scheideler, M. Eikel, A. Setzer, in: Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA), 2014, pp. 168--180.","bibtex":"@inproceedings{Scheideler_Eikel_Setzer_2014, series={LNCS}, title={Minimum Linear Arrangement of Series-Parallel Graphs}, booktitle={Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)}, author={Scheideler, Christian and Eikel, Martina and Setzer, Alexander}, year={2014}, pages={168--180}, collection={LNCS} }"},"page":"168--180","year":"2014","date_created":"2017-10-17T12:42:09Z","author":[{"first_name":"Christian","last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792"},{"last_name":"Eikel","full_name":"Eikel, Martina","first_name":"Martina"},{"id":"11108","full_name":"Setzer, Alexander","last_name":"Setzer","first_name":"Alexander"}],"date_updated":"2022-01-06T07:00:02Z","title":"Minimum Linear Arrangement of Series-Parallel Graphs","type":"conference","publication":"Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)","file":[{"file_size":365818,"access_level":"closed","file_id":"1381","file_name":"397-WAOA14_01.pdf","date_updated":"2018-03-20T06:58:44Z","creator":"florida","date_created":"2018-03-20T06:58:44Z","success":1,"relation":"main_file","content_type":"application/pdf"}],"status":"public","abstract":[{"text":"We present a factor $14D^2$ approximation algorithm for the minimum linear arrangement problem on series-parallel graphs, where $D$ is the maximum degree in the graph. Given a suitable decomposition of the graph, our algorithm runs in time $O(|E|)$ and is very easy to implement. Its divide-and-conquer approach allows for an effective parallelization. Note that a suitable decomposition can also be computed in time $O(|E|\\log{|E|})$ (or even $O(\\log{|E|}\\log^*{|E|})$ on an EREW PRAM using $O(|E|)$ processors). For the proof of the approximation ratio, we use a sophisticated charging method that uses techniques similar to amortized analysis in advanced data structures. On general graphs, the minimum linear arrangement problem is known to be NP-hard. To the best of our knowledge, the minimum linear arrangement problem on series-parallel graphs has not been studied before.","lang":"eng"}],"series_title":"LNCS","user_id":"15504","department":[{"_id":"79"}],"project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"397","file_date_updated":"2018-03-20T06:58:44Z","ddc":["040"]},{"year":"2014","date_created":"2017-10-17T12:42:12Z","title":"HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths","publication":"Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing (P2P)","abstract":[{"text":"In this paper we present and analyze HSkip+, a self-stabilizing overlay network for nodes with arbitrary heterogeneous bandwidths. HSkip+ has the same topology as the Skip+ graph proposed by Jacob et al. [PODC 2009] but its self-stabilization mechanism significantly outperforms the self-stabilization mechanism proposed for Skip+. Also, the nodes are now ordered according to their bandwidths and not according to their identifiers. Various other solutions have already been proposed for overlay networks with heterogeneous bandwidths, but they are not self-stabilizing. In addition to HSkip+ being self-stabilizing, its performance is on par with the best previous bounds on the time and work for joining or leaving a network of peers of logarithmic diameter and degree and arbitrary bandwidths. Also, the dilation and congestion for routing messages is on par with the best previous bounds for such networks, so that HSkip+ combines the advantages of both worlds. Our theoretical investigations are backed by simulations demonstrating that HSkip+ is indeed performing much better than Skip+ and working correctly under high churn rates.","lang":"eng"}],"file":[{"creator":"florida","date_created":"2018-03-16T11:34:00Z","date_updated":"2018-03-16T11:34:00Z","file_id":"1361","file_name":"412-FSG2014P2P.pdf","access_level":"closed","file_size":472321,"content_type":"application/pdf","relation":"main_file","success":1}],"external_id":{"arxiv":["1408.0395"]},"ddc":["040"],"has_accepted_license":"1","citation":{"chicago":"Feldotto, Matthias, Christian Scheideler, and Kalman Graffi. “HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths.” In <i>Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing (P2P)</i>, 1–10, 2014. <a href=\"https://doi.org/10.1109/P2P.2014.6934300\">https://doi.org/10.1109/P2P.2014.6934300</a>.","ieee":"M. Feldotto, C. Scheideler, and K. Graffi, “HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths,” in <i>Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing (P2P)</i>, 2014, pp. 1–10.","ama":"Feldotto M, Scheideler C, Graffi K. HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths. In: <i>Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing (P2P)</i>. ; 2014:1-10. doi:<a href=\"https://doi.org/10.1109/P2P.2014.6934300\">10.1109/P2P.2014.6934300</a>","apa":"Feldotto, M., Scheideler, C., &#38; Graffi, K. (2014). HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths. In <i>Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing (P2P)</i> (pp. 1–10). <a href=\"https://doi.org/10.1109/P2P.2014.6934300\">https://doi.org/10.1109/P2P.2014.6934300</a>","short":"M. Feldotto, C. Scheideler, K. Graffi, in: Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing (P2P), 2014, pp. 1–10.","bibtex":"@inproceedings{Feldotto_Scheideler_Graffi_2014, title={HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths}, DOI={<a href=\"https://doi.org/10.1109/P2P.2014.6934300\">10.1109/P2P.2014.6934300</a>}, booktitle={Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing (P2P)}, author={Feldotto, Matthias and Scheideler, Christian and Graffi, Kalman}, year={2014}, pages={1–10} }","mla":"Feldotto, Matthias, et al. “HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths.” <i>Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing (P2P)</i>, 2014, pp. 1–10, doi:<a href=\"https://doi.org/10.1109/P2P.2014.6934300\">10.1109/P2P.2014.6934300</a>."},"page":"1-10","date_updated":"2022-01-06T07:00:20Z","author":[{"full_name":"Feldotto, Matthias","id":"14052","last_name":"Feldotto","orcid":"0000-0003-1348-6516","first_name":"Matthias"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"},{"first_name":"Kalman","last_name":"Graffi","full_name":"Graffi, Kalman"}],"doi":"10.1109/P2P.2014.6934300","type":"conference","status":"public","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"_id":"412","user_id":"14052","department":[{"_id":"79"},{"_id":"63"},{"_id":"541"}],"file_date_updated":"2018-03-16T11:34:00Z"},{"language":[{"iso":"ger"}],"user_id":"477","_id":"434","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"status":"public","type":"bachelorsthesis","title":"Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem in Skip+ Graphen","author":[{"first_name":"Linghui","last_name":"Luo","full_name":"Luo, Linghui"}],"date_created":"2017-10-17T12:42:16Z","publisher":"Universität Paderborn","date_updated":"2022-01-06T07:00:57Z","citation":{"bibtex":"@book{Luo_2014, title={Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem in Skip+ Graphen}, publisher={Universität Paderborn}, author={Luo, Linghui}, year={2014} }","mla":"Luo, Linghui. <i>Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem in Skip+ Graphen</i>. Universität Paderborn, 2014.","short":"L. Luo, Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem in Skip+ Graphen, Universität Paderborn, 2014.","apa":"Luo, L. (2014). <i>Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem in Skip+ Graphen</i>. Universität Paderborn.","ieee":"L. Luo, <i>Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem in Skip+ Graphen</i>. Universität Paderborn, 2014.","chicago":"Luo, Linghui. <i>Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem in Skip+ Graphen</i>. Universität Paderborn, 2014.","ama":"Luo L. <i>Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem in Skip+ Graphen</i>. Universität Paderborn; 2014."},"year":"2014"},{"title":"Cliquenbildung in verteilten Systemen","supervisor":[{"last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian","first_name":"Christian"}],"author":[{"last_name":"Blumentritt","full_name":"Blumentritt, Fritz","first_name":"Fritz"}],"date_created":"2020-08-17T08:14:17Z","publisher":"Universität Paderborn","date_updated":"2022-01-06T06:53:25Z","citation":{"bibtex":"@book{Blumentritt_2013, title={Cliquenbildung in verteilten Systemen}, publisher={Universität Paderborn}, author={Blumentritt, Fritz}, year={2013} }","short":"F. Blumentritt, Cliquenbildung in Verteilten Systemen, Universität Paderborn, 2013.","mla":"Blumentritt, Fritz. <i>Cliquenbildung in Verteilten Systemen</i>. Universität Paderborn, 2013.","apa":"Blumentritt, F. (2013). <i>Cliquenbildung in verteilten Systemen</i>. Universität Paderborn.","ama":"Blumentritt F. <i>Cliquenbildung in Verteilten Systemen</i>. Universität Paderborn; 2013.","ieee":"F. Blumentritt, <i>Cliquenbildung in verteilten Systemen</i>. Universität Paderborn, 2013.","chicago":"Blumentritt, Fritz. <i>Cliquenbildung in Verteilten Systemen</i>. Universität Paderborn, 2013."},"year":"2013","language":[{"iso":"eng"}],"department":[{"_id":"79"}],"user_id":"477","_id":"18000","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"status":"public","type":"bachelorsthesis"},{"page":"341-363","citation":{"ieee":"P. Kolman and C. Scheideler, “Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing,” <i>Theory of Computing Systems</i>, no. 2, pp. 341–363, 2013.","chicago":"Kolman, Petr, and Christian Scheideler. “Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing.” <i>Theory of Computing Systems</i>, no. 2 (2013): 341–63. <a href=\"https://doi.org/10.1007/s00224-013-9454-3\">https://doi.org/10.1007/s00224-013-9454-3</a>.","ama":"Kolman P, Scheideler C. Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing. <i>Theory of Computing Systems</i>. 2013;(2):341-363. doi:<a href=\"https://doi.org/10.1007/s00224-013-9454-3\">10.1007/s00224-013-9454-3</a>","mla":"Kolman, Petr, and Christian Scheideler. “Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing.” <i>Theory of Computing Systems</i>, no. 2, Springer, 2013, pp. 341–63, doi:<a href=\"https://doi.org/10.1007/s00224-013-9454-3\">10.1007/s00224-013-9454-3</a>.","short":"P. Kolman, C. Scheideler, Theory of Computing Systems (2013) 341–363.","bibtex":"@article{Kolman_Scheideler_2013, title={Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing}, DOI={<a href=\"https://doi.org/10.1007/s00224-013-9454-3\">10.1007/s00224-013-9454-3</a>}, number={2}, journal={Theory of Computing Systems}, publisher={Springer}, author={Kolman, Petr and Scheideler, Christian}, year={2013}, pages={341–363} }","apa":"Kolman, P., &#38; Scheideler, C. (2013). Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing. <i>Theory of Computing Systems</i>, (2), 341–363. <a href=\"https://doi.org/10.1007/s00224-013-9454-3\">https://doi.org/10.1007/s00224-013-9454-3</a>"},"year":"2013","issue":"2","has_accepted_license":"1","doi":"10.1007/s00224-013-9454-3","title":"Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing","date_created":"2017-10-17T12:42:24Z","author":[{"last_name":"Kolman","full_name":"Kolman, Petr","first_name":"Petr"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"}],"publisher":"Springer","date_updated":"2022-01-06T07:01:21Z","status":"public","file":[{"relation":"main_file","success":1,"content_type":"application/pdf","file_id":"1326","access_level":"closed","file_name":"476-tocsrevised3b.pdf","file_size":264308,"date_created":"2018-03-15T14:07:18Z","creator":"florida","date_updated":"2018-03-15T14:07:18Z"}],"abstract":[{"text":"An elementary h-route ow, for an integer h 1, is a set of h edge- disjoint paths between a source and a sink, each path carrying a unit of ow, and an h-route ow is a non-negative linear combination of elementary h-routeows. An h-route cut is a set of edges whose removal decreases the maximum h-route ow between a given source-sink pair (or between every source-sink pair in the multicommodity setting) to zero. The main result of this paper is an approximate duality theorem for multicommodity h-route cuts and ows, for h 3: The size of a minimum h-route cut is at least f=h and at most O(log4 k f) where f is the size of the maximum h-routeow and k is the number of commodities. The main step towards the proof of this duality is the design and analysis of a polynomial-time approximation algorithm for the minimum h-route cut problem for h = 3 that has an approximation ratio of O(log4 k). Previously, polylogarithmic approximation was known only for h-route cuts for h 2. A key ingredient of our algorithm is a novel rounding technique that we call multilevel ball-growing. Though the proof of the duality relies on this algorithm, it is not a straightforward corollary of it as in the case of classical multicommodity ows and cuts. Similar results are shown also for the sparsest multiroute cut problem.","lang":"eng"}],"publication":"Theory of Computing Systems","type":"journal_article","file_date_updated":"2018-03-15T14:07:18Z","ddc":["040"],"department":[{"_id":"79"}],"user_id":"477","_id":"476","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}]},{"_id":"477","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"63"}],"series_title":"Lecture Notes in Computer Science","user_id":"15504","ddc":["040"],"file_date_updated":"2018-03-15T14:06:38Z","publication":"Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers","type":"conference","abstract":[{"text":"We consider the k-token dissemination problem, where k initially arbitrarily distributed tokens have to be disseminated to all nodes in a dynamic network (as introduced by Kuhn et al., STOC 2010). In contrast to general dynamic networks, our dynamic networks are unit disk graphs, i.e., nodes are embedded into the Euclidean plane and two nodes are connected if and only if their distance is at most R. Our worst-case adversary is allowed to move the nodes on the plane, but the maximum velocity v_max of each node is limited and the graph must be connected in each round. For this model, we provide almost tight lower and upper bounds for k-token dissemination if nodes are restricted to send only one token per round. It turns out that the maximum velocity v_max is a meaningful parameter to characterize dynamics in our model.","lang":"eng"}],"status":"public","file":[{"date_updated":"2018-03-15T14:06:38Z","creator":"florida","date_created":"2018-03-15T14:06:38Z","file_size":193169,"file_name":"477-geometric-dynamic-networks_01.pdf","file_id":"1325","access_level":"closed","content_type":"application/pdf","success":1,"relation":"main_file"}],"date_updated":"2022-01-06T07:01:21Z","date_created":"2017-10-17T12:42:25Z","author":[{"first_name":"Sebastian","full_name":"Abshoff, Sebastian","last_name":"Abshoff"},{"first_name":"Markus","full_name":"Benter, Markus","last_name":"Benter"},{"first_name":"Andreas","full_name":"Cord-Landwehr, Andreas","last_name":"Cord-Landwehr"},{"first_name":"Manuel","full_name":"Malatyali, Manuel","last_name":"Malatyali"},{"first_name":"Friedhelm","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide"}],"title":"Token Dissemination in Geometric Dynamic Networks","doi":"10.1007/978-3-642-45346-5_3","has_accepted_license":"1","year":"2013","page":"22-34","citation":{"chicago":"Abshoff, Sebastian, Markus Benter, Andreas Cord-Landwehr, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “Token Dissemination in Geometric Dynamic Networks.” In <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers</i>, 22–34. Lecture Notes in Computer Science, 2013. <a href=\"https://doi.org/10.1007/978-3-642-45346-5_3\">https://doi.org/10.1007/978-3-642-45346-5_3</a>.","ieee":"S. Abshoff, M. Benter, A. Cord-Landwehr, M. Malatyali, and F. Meyer auf der Heide, “Token Dissemination in Geometric Dynamic Networks,” in <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers</i>, 2013, pp. 22–34.","ama":"Abshoff S, Benter M, Cord-Landwehr A, Malatyali M, Meyer auf der Heide F. Token Dissemination in Geometric Dynamic Networks. In: <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers</i>. Lecture Notes in Computer Science. ; 2013:22-34. doi:<a href=\"https://doi.org/10.1007/978-3-642-45346-5_3\">10.1007/978-3-642-45346-5_3</a>","bibtex":"@inproceedings{Abshoff_Benter_Cord-Landwehr_Malatyali_Meyer auf der Heide_2013, series={Lecture Notes in Computer Science}, title={Token Dissemination in Geometric Dynamic Networks}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-45346-5_3\">10.1007/978-3-642-45346-5_3</a>}, booktitle={Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers}, author={Abshoff, Sebastian and Benter, Markus and Cord-Landwehr, Andreas and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2013}, pages={22–34}, collection={Lecture Notes in Computer Science} }","short":"S. Abshoff, M. Benter, A. Cord-Landwehr, M. Malatyali, F. Meyer auf der Heide, in: Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers, 2013, pp. 22–34.","mla":"Abshoff, Sebastian, et al. “Token Dissemination in Geometric Dynamic Networks.” <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers</i>, 2013, pp. 22–34, doi:<a href=\"https://doi.org/10.1007/978-3-642-45346-5_3\">10.1007/978-3-642-45346-5_3</a>.","apa":"Abshoff, S., Benter, M., Cord-Landwehr, A., Malatyali, M., &#38; Meyer auf der Heide, F. (2013). Token Dissemination in Geometric Dynamic Networks. In <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers</i> (pp. 22–34). <a href=\"https://doi.org/10.1007/978-3-642-45346-5_3\">https://doi.org/10.1007/978-3-642-45346-5_3</a>"}},{"type":"conference","publication":"Proceedings of the International Conference on Communications (ICC'13)","abstract":[{"lang":"eng","text":"Cloud computing offers high availability, dynamic scalability, and elasticity requiring only very little administration. However, this service comes with financial costs. Peer-to-peer systems, in contrast, operate at very low costs but cannot match the quality of service of the cloud. This paper focuses on the case study of Wikipedia and presents an approach to reduce the operational costs of hosting similar websites in the cloud by using a practical peer-to-peer approach. The visitors of the site are joining a Chord overlay, which acts as first cache for article lookups. Simulation results show, that up to 72% of the article lookups in Wikipedia could be answered by other visitors instead of using the cloud."}],"file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-15T14:02:01Z","date_created":"2018-03-15T14:02:01Z","creator":"florida","file_size":1405789,"file_name":"481-Symbiotic.Coupling.of.P2P.and.Cloud.Systems.The.Wikipedia.Case2.pdf","access_level":"closed","file_id":"1321"}],"status":"public","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"481","user_id":"477","department":[{"_id":"79"}],"ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-15T14:02:01Z","has_accepted_license":"1","year":"2013","citation":{"chicago":"Graffi, Kalman, and Lars Bremer. “Symbiotic Coupling of P2P and Cloud Systems: The Wikipedia Case.” In <i>Proceedings of the International Conference on Communications (ICC’13)</i>, 3444–49, 2013. <a href=\"https://doi.org/10.1109/ICC.2013.6655082\">https://doi.org/10.1109/ICC.2013.6655082</a>.","ieee":"K. Graffi and L. Bremer, “Symbiotic Coupling of P2P and Cloud Systems: The Wikipedia Case,” in <i>Proceedings of the International Conference on Communications (ICC’13)</i>, 2013, pp. 3444–3449.","ama":"Graffi K, Bremer L. Symbiotic Coupling of P2P and Cloud Systems: The Wikipedia Case. In: <i>Proceedings of the International Conference on Communications (ICC’13)</i>. ; 2013:3444-3449. doi:<a href=\"https://doi.org/10.1109/ICC.2013.6655082\">10.1109/ICC.2013.6655082</a>","mla":"Graffi, Kalman, and Lars Bremer. “Symbiotic Coupling of P2P and Cloud Systems: The Wikipedia Case.” <i>Proceedings of the International Conference on Communications (ICC’13)</i>, 2013, pp. 3444–49, doi:<a href=\"https://doi.org/10.1109/ICC.2013.6655082\">10.1109/ICC.2013.6655082</a>.","bibtex":"@inproceedings{Graffi_Bremer_2013, title={Symbiotic Coupling of P2P and Cloud Systems: The Wikipedia Case}, DOI={<a href=\"https://doi.org/10.1109/ICC.2013.6655082\">10.1109/ICC.2013.6655082</a>}, booktitle={Proceedings of the International Conference on Communications (ICC’13)}, author={Graffi, Kalman and Bremer, Lars}, year={2013}, pages={3444–3449} }","short":"K. Graffi, L. Bremer, in: Proceedings of the International Conference on Communications (ICC’13), 2013, pp. 3444–3449.","apa":"Graffi, K., &#38; Bremer, L. (2013). Symbiotic Coupling of P2P and Cloud Systems: The Wikipedia Case. In <i>Proceedings of the International Conference on Communications (ICC’13)</i> (pp. 3444–3449). <a href=\"https://doi.org/10.1109/ICC.2013.6655082\">https://doi.org/10.1109/ICC.2013.6655082</a>"},"page":"3444 - 3449 ","date_updated":"2022-01-06T07:01:25Z","date_created":"2017-10-17T12:42:26Z","author":[{"last_name":"Graffi","full_name":"Graffi, Kalman","first_name":"Kalman"},{"first_name":"Lars","last_name":"Bremer","full_name":"Bremer, Lars"}],"title":"Symbiotic Coupling of P2P and Cloud Systems: The Wikipedia Case","doi":"10.1109/ICC.2013.6655082"},{"citation":{"ama":"Blix A. <i>Optimale und adaptive binäre Bäume in Netzwerken</i>. Universität Paderborn; 2013.","chicago":"Blix, Andreas. <i>Optimale und adaptive binäre Bäume in Netzwerken</i>. Universität Paderborn, 2013.","ieee":"A. Blix, <i>Optimale und adaptive binäre Bäume in Netzwerken</i>. Universität Paderborn, 2013.","apa":"Blix, A. (2013). <i>Optimale und adaptive binäre Bäume in Netzwerken</i>. Universität Paderborn.","bibtex":"@book{Blix_2013, title={Optimale und adaptive binäre Bäume in Netzwerken}, publisher={Universität Paderborn}, author={Blix, Andreas}, year={2013} }","short":"A. Blix, Optimale und adaptive binäre Bäume in Netzwerken, Universität Paderborn, 2013.","mla":"Blix, Andreas. <i>Optimale und adaptive binäre Bäume in Netzwerken</i>. Universität Paderborn, 2013."},"year":"2013","title":"Optimale und adaptive binäre Bäume in Netzwerken","date_created":"2017-10-17T12:42:30Z","author":[{"first_name":"Andreas","full_name":"Blix, Andreas","last_name":"Blix"}],"publisher":"Universität Paderborn","date_updated":"2022-01-06T07:01:35Z","status":"public","type":"bachelorsthesis","language":[{"iso":"ger"}],"user_id":"477","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"503"},{"_id":"507","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"department":[{"_id":"63"}],"series_title":"LNCS","user_id":"15504","ddc":["040"],"file_date_updated":"2018-03-15T10:47:31Z","publication":"Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)","type":"conference","abstract":[{"text":"We study two-party communication in the context of directed dynamic networks that are controlled by an adaptive adversary. This adversary is able to change all edges as long as the networks stay strongly-connected in each round. In this work, we establish a relation between counting the total number of nodes in the network and the problem of exchanging tokens between two communication partners which communicate through a dynamic network. We show that the communication problem for a constant fraction of n tokens in a dynamic network with n nodes is at most as hard as counting the number of nodes in a dynamic network with at most 4n+3 nodes. For the proof, we construct a family of directed dynamic networks and apply a lower bound from two-party communication complexity.","lang":"eng"}],"status":"public","file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-15T10:47:31Z","date_created":"2018-03-15T10:47:31Z","creator":"florida","file_size":181398,"access_level":"closed","file_name":"507-on-two-party-communication-through-dynamic-networks_01.pdf","file_id":"1305"}],"date_updated":"2022-01-06T07:01:36Z","author":[{"full_name":"Abshoff, Sebastian","last_name":"Abshoff","first_name":"Sebastian"},{"first_name":"Markus","full_name":"Benter, Markus","last_name":"Benter"},{"first_name":"Manuel","last_name":"Malatyali","full_name":"Malatyali, Manuel"},{"first_name":"Friedhelm","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide"}],"date_created":"2017-10-17T12:42:31Z","title":"On Two-Party Communication Through Dynamic Networks","doi":"10.1007/978-3-319-03850-6_2","has_accepted_license":"1","year":"2013","page":"11-22","citation":{"chicago":"Abshoff, Sebastian, Markus Benter, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “On Two-Party Communication Through Dynamic Networks.” In <i>Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)</i>, 11–22. LNCS, 2013. <a href=\"https://doi.org/10.1007/978-3-319-03850-6_2\">https://doi.org/10.1007/978-3-319-03850-6_2</a>.","ieee":"S. Abshoff, M. Benter, M. Malatyali, and F. Meyer auf der Heide, “On Two-Party Communication Through Dynamic Networks,” in <i>Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)</i>, 2013, pp. 11–22.","ama":"Abshoff S, Benter M, Malatyali M, Meyer auf der Heide F. On Two-Party Communication Through Dynamic Networks. In: <i>Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)</i>. LNCS. ; 2013:11-22. doi:<a href=\"https://doi.org/10.1007/978-3-319-03850-6_2\">10.1007/978-3-319-03850-6_2</a>","apa":"Abshoff, S., Benter, M., Malatyali, M., &#38; Meyer auf der Heide, F. (2013). On Two-Party Communication Through Dynamic Networks. In <i>Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)</i> (pp. 11–22). <a href=\"https://doi.org/10.1007/978-3-319-03850-6_2\">https://doi.org/10.1007/978-3-319-03850-6_2</a>","bibtex":"@inproceedings{Abshoff_Benter_Malatyali_Meyer auf der Heide_2013, series={LNCS}, title={On Two-Party Communication Through Dynamic Networks}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-03850-6_2\">10.1007/978-3-319-03850-6_2</a>}, booktitle={Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)}, author={Abshoff, Sebastian and Benter, Markus and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2013}, pages={11–22}, collection={LNCS} }","short":"S. Abshoff, M. Benter, M. Malatyali, F. Meyer auf der Heide, in: Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS), 2013, pp. 11–22.","mla":"Abshoff, Sebastian, et al. “On Two-Party Communication Through Dynamic Networks.” <i>Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)</i>, 2013, pp. 11–22, doi:<a href=\"https://doi.org/10.1007/978-3-319-03850-6_2\">10.1007/978-3-319-03850-6_2</a>."}},{"_id":"510","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"user_id":"15504","type":"mastersthesis","status":"public","date_updated":"2022-01-06T07:01:37Z","publisher":"Universität Paderborn","author":[{"first_name":"Chintan","full_name":"Jayesh Parekh, Chintan","last_name":"Jayesh Parekh"}],"date_created":"2017-10-17T12:42:31Z","title":"Meta-data based Search in Structured Peer-to-Peer Networks","year":"2013","citation":{"mla":"Jayesh Parekh, Chintan. <i>Meta-Data Based Search in Structured Peer-to-Peer Networks</i>. Universität Paderborn, 2013.","bibtex":"@book{Jayesh Parekh_2013, title={Meta-data based Search in Structured Peer-to-Peer Networks}, publisher={Universität Paderborn}, author={Jayesh Parekh, Chintan}, year={2013} }","short":"C. Jayesh Parekh, Meta-Data Based Search in Structured Peer-to-Peer Networks, Universität Paderborn, 2013.","apa":"Jayesh Parekh, C. (2013). <i>Meta-data based Search in Structured Peer-to-Peer Networks</i>. Universität Paderborn.","chicago":"Jayesh Parekh, Chintan. <i>Meta-Data Based Search in Structured Peer-to-Peer Networks</i>. Universität Paderborn, 2013.","ieee":"C. Jayesh Parekh, <i>Meta-data based Search in Structured Peer-to-Peer Networks</i>. Universität Paderborn, 2013.","ama":"Jayesh Parekh C. <i>Meta-Data Based Search in Structured Peer-to-Peer Networks</i>. Universität Paderborn; 2013."}},{"file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-15T10:45:15Z","creator":"florida","date_created":"2018-03-15T10:45:15Z","file_size":518804,"file_name":"513-ipdps13_01.pdf","access_level":"closed","file_id":"1303"}],"status":"public","abstract":[{"lang":"eng","text":"This paper initiates the study of self-adjusting networks (or distributed data structures) whose topologies dynamically adapt to a communication pattern $\\sigma$. We present a fully decentralized self-adjusting solution called SplayNet. A SplayNet is a distributed generalization of the classic splay tree concept. It ensures short paths (which can be found using local-greedy routing) between communication partners while minimizing topological rearrangements. We derive an upper bound for the amortized communication cost of a SplayNet based on empirical entropies of $\\sigma$, and show that SplayNets have several interesting convergence properties. For instance, SplayNets features a provable online optimality under special requests scenarios. We also investigate the optimal static network and prove different lower bounds for the average communication cost based on graph cuts and on the empirical entropy of the communication pattern $\\sigma$. From these lower bounds it follows, e.g., that SplayNets are optimal in scenarios where the requests follow a product distribution as well. Finally, this paper shows that in contrast to the Minimum Linear Arrangement problem which is generally NP-hard, the optimal static tree network can be computed in polynomial time for any guest graph, despite the exponentially large graph family. We complement our formal analysis with a small simulation study on a Facebook graph."}],"type":"conference","publication":"Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)","file_date_updated":"2018-03-15T10:45:15Z","ddc":["040"],"user_id":"15504","department":[{"_id":"79"}],"project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"513","citation":{"chicago":"Avin, Chen, Bernhard Häupler, Zvi Lotker, Christian Scheideler, and Stefan Schmid. “Locally Self-Adjusting Tree Networks.” In <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>, 395–406, 2013. <a href=\"https://doi.org/10.1109/IPDPS.2013.40\">https://doi.org/10.1109/IPDPS.2013.40</a>.","ieee":"C. Avin, B. Häupler, Z. Lotker, C. Scheideler, and S. Schmid, “Locally Self-Adjusting Tree Networks,” in <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>, 2013, pp. 395–406.","ama":"Avin C, Häupler B, Lotker Z, Scheideler C, Schmid S. Locally Self-Adjusting Tree Networks. In: <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>. ; 2013:395-406. doi:<a href=\"https://doi.org/10.1109/IPDPS.2013.40\">10.1109/IPDPS.2013.40</a>","short":"C. Avin, B. Häupler, Z. Lotker, C. Scheideler, S. Schmid, in: Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2013, pp. 395–406.","bibtex":"@inproceedings{Avin_Häupler_Lotker_Scheideler_Schmid_2013, title={Locally Self-Adjusting Tree Networks}, DOI={<a href=\"https://doi.org/10.1109/IPDPS.2013.40\">10.1109/IPDPS.2013.40</a>}, booktitle={Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)}, author={Avin, Chen and Häupler, Bernhard and Lotker, Zvi and Scheideler, Christian and Schmid, Stefan}, year={2013}, pages={395–406} }","mla":"Avin, Chen, et al. “Locally Self-Adjusting Tree Networks.” <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>, 2013, pp. 395–406, doi:<a href=\"https://doi.org/10.1109/IPDPS.2013.40\">10.1109/IPDPS.2013.40</a>.","apa":"Avin, C., Häupler, B., Lotker, Z., Scheideler, C., &#38; Schmid, S. (2013). Locally Self-Adjusting Tree Networks. In <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i> (pp. 395–406). <a href=\"https://doi.org/10.1109/IPDPS.2013.40\">https://doi.org/10.1109/IPDPS.2013.40</a>"},"page":"395-406","year":"2013","has_accepted_license":"1","doi":"10.1109/IPDPS.2013.40","title":"Locally Self-Adjusting Tree Networks","author":[{"last_name":"Avin","full_name":"Avin, Chen","first_name":"Chen"},{"first_name":"Bernhard","full_name":"Häupler, Bernhard","last_name":"Häupler"},{"last_name":"Lotker","full_name":"Lotker, Zvi","first_name":"Zvi"},{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"date_created":"2017-10-17T12:42:32Z","date_updated":"2022-01-06T07:01:38Z"},{"abstract":[{"text":"Diese Arbeit besch{\\\"a}ftigt sich mit dem Facility Location Problem. Dies ist ein Optimierungsproblem, bei dem festgelegt werden muss an welchen Positionen Ressourcen zur Verf{\\\"u}gung gestellt werden, so dass diese von Nutzern gut erreicht werden k{\\\"o}nnen. Es sollen dabei Kosten minimiert werden, die zum einen durch Bereitstellung von Ressourcen und zum anderen durch Verbindungskosten zwischen Nutzern und Ressourcen entstehen. Die Schwierigkeit des Problems liegt darin, dass man einerseits m{\\\"o}glichst wenige Ressourcen zur Verf{\\\"u}gung stellen m{\\\"o}chte, andererseits daf{\\\"u}r sorgen muss, dass sich Nutzer nicht all zu weit weg von Ressourcen befinden. Dies w{\\\"u}rde n{\\\"a}mlich hohe Verbindungskosten nach sich ziehen. Das Facility Location Problem wurde bereits sehr intensiv in vielen unterschiedlichen Varianten untersucht. In dieser Arbeit werden drei Varianten des Problems modelliert und neue Algorithmen f{\\\"u}r sie entwickelt und bez{\\\"u}glich ihres Approximationsfaktors und ihrer Laufzeit analysiert. Jede dieser drei untersuchten Varianten hat einen besonderen Schwerpunkt. Bei der ersten Varianten handelt es sich um ein Online Problem, da hier die Eingabe nicht von Anfang an bekannt ist, sondern Schritt f{\\\"u}r Schritt enth{\\\"u}llt wird. Die Schwierigkeit hierbei besteht darin unwiderrufliche Entscheidungen treffen zu m{\\\"u}ssen ohne dabei die Zukunft zu kennen und trotzdem eine zu jeder Zeit gute L{\\\"o}sung angeben zu k{\\\"o}nnen. Der Schwerpunkt der zweiten Variante liegt auf Lokalit{\\\"a}t, die z.B. in Sensornetzwerken von großer Bedeutung ist. Hier soll eine L{\\\"o}sung verteilt und nur mit Hilfe von lokalen Information berechnet werden. Schließlich besch{\\\"a}ftigt sich die dritte Variante mit einer verteilten Berechnung, bei welcher nur eine stark beschr{\\\"a}nkte Datenmenge verschickt werden darf und dabei trotzdem ein sehr guter Approximationsfaktor erreicht werden muss. Die bei der Analyse der Approximationsfaktoren bzw. der Kompetitivit{\\\"a}t verwendeten Techniken basieren zum großen Teil auf Absch{\\\"a}tzung der primalen L{\\\"o}sung mit Hilfe einer L{\\\"o}sung des zugeh{\\\"o}rigen dualen Problems. F{\\\"u}r die Modellierung von Lokalit{\\\"a}t wird das weitverbreitete LOCAL Modell verwendet. In diesem Modell werden f{\\\"u}r die Algorithmen subpolynomielle obere Laufzeitschranken gezeigt.","lang":"eng"}],"status":"public","file":[{"date_updated":"2018-03-15T10:44:13Z","creator":"florida","date_created":"2018-03-15T10:44:13Z","file_size":790821,"file_id":"1302","file_name":"514-DissertationPietrzyk.pdf","access_level":"closed","content_type":"application/pdf","success":1,"relation":"main_file"}],"type":"dissertation","ddc":["040"],"file_date_updated":"2018-03-15T10:44:13Z","_id":"514","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"department":[{"_id":"63"}],"user_id":"477","year":"2013","citation":{"apa":"Pietrzyk, P. (2013). <i>Local and Online Algorithms for Facility Location</i>. Universität Paderborn.","short":"P. Pietrzyk, Local and Online Algorithms for Facility Location, Universität Paderborn, 2013.","mla":"Pietrzyk, Peter. <i>Local and Online Algorithms for Facility Location</i>. Universität Paderborn, 2013.","bibtex":"@book{Pietrzyk_2013, title={Local and Online Algorithms for Facility Location}, publisher={Universität Paderborn}, author={Pietrzyk, Peter}, year={2013} }","ama":"Pietrzyk P. <i>Local and Online Algorithms for Facility Location</i>. Universität Paderborn; 2013.","ieee":"P. Pietrzyk, <i>Local and Online Algorithms for Facility Location</i>. Universität Paderborn, 2013.","chicago":"Pietrzyk, Peter. <i>Local and Online Algorithms for Facility Location</i>. Universität Paderborn, 2013."},"has_accepted_license":"1","title":"Local and Online Algorithms for Facility Location","date_updated":"2022-01-06T07:01:38Z","publisher":"Universität Paderborn","supervisor":[{"id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide","first_name":"Friedhelm"}],"author":[{"first_name":"Peter","last_name":"Pietrzyk","full_name":"Pietrzyk, Peter"}],"date_created":"2017-10-17T12:42:32Z"},{"type":"mastersthesis","status":"public","department":[{"_id":"79"}],"user_id":"14052","_id":"522","project":[{"name":"SFB 901","_id":"1"},{"_id":"2","name":"SFB 901 - Teilprojekt A"},{"_id":"5","name":"SFB 901 - Subprojekt A1"}],"citation":{"ieee":"M. Feldotto, <i>HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths</i>. Universität Paderborn, 2013.","chicago":"Feldotto, Matthias. <i>HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths</i>. Universität Paderborn, 2013.","ama":"Feldotto M. <i>HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths</i>. Universität Paderborn; 2013.","apa":"Feldotto, M. (2013). <i>HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths</i>. Universität Paderborn.","mla":"Feldotto, Matthias. <i>HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths</i>. Universität Paderborn, 2013.","bibtex":"@book{Feldotto_2013, title={HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths}, publisher={Universität Paderborn}, author={Feldotto, Matthias}, year={2013} }","short":"M. Feldotto, HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths, Universität Paderborn, 2013."},"year":"2013","author":[{"orcid":"0000-0003-1348-6516","last_name":"Feldotto","full_name":"Feldotto, Matthias","id":"14052","first_name":"Matthias"}],"date_created":"2017-10-17T12:42:34Z","supervisor":[{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"}],"date_updated":"2022-01-06T07:01:47Z","publisher":"Universität Paderborn","title":"HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths"},{"has_accepted_license":"1","citation":{"ieee":"F. Meyer auf der Heide and K. Swirkot, “Hierarchies in Local Distributed Decision.” arXiv, 2013.","chicago":"Meyer auf der Heide, Friedhelm, and Kamil Swirkot. “Hierarchies in Local Distributed Decision.” arXiv, 2013.","ama":"Meyer auf der Heide F, Swirkot K. Hierarchies in Local Distributed Decision. 2013.","apa":"Meyer auf der Heide, F., &#38; Swirkot, K. (2013). Hierarchies in Local Distributed Decision. arXiv.","bibtex":"@article{Meyer auf der Heide_Swirkot_2013, title={Hierarchies in Local Distributed Decision}, publisher={arXiv}, author={Meyer auf der Heide, Friedhelm and Swirkot, Kamil}, year={2013} }","mla":"Meyer auf der Heide, Friedhelm, and Kamil Swirkot. <i>Hierarchies in Local Distributed Decision</i>. arXiv, 2013.","short":"F. Meyer auf der Heide, K. Swirkot, (2013)."},"date_updated":"2022-01-06T07:01:48Z","author":[{"id":"15523","full_name":"Meyer auf der Heide, Friedhelm","last_name":"Meyer auf der Heide","first_name":"Friedhelm"},{"last_name":"Swirkot","full_name":"Swirkot, Kamil","first_name":"Kamil"}],"type":"preprint","status":"public","_id":"524","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":"15415","file_date_updated":"2018-03-15T10:37:07Z","year":"2013","publisher":"arXiv","date_created":"2017-10-17T12:42:34Z","title":"Hierarchies in Local Distributed Decision","abstract":[{"text":"We study the complexity theory for the local distributed setting introduced by Korman, Peleg and Fraigniaud. They have defined three complexity classes LD (Local Decision), NLD (Nondeterministic Local Decision) and NLD^#n. The class LD consists of all languages which can be decided with a constant number of communication rounds. The class NLD consists of all languages which can be verified by a nondeterministic algorithm with a constant number of communication rounds. In order to define the nondeterministic classes, they have transferred the notation of nondeterminism into the distributed setting by the use of certificates and verifiers. The class NLD^#n consists of all languages which can be verified by a nondeterministic algorithm where each node has access to an oracle for the number of nodes. They have shown the hierarchy LD subset NLD subset NLD^#n. Our main contributions are strict hierarchies within the classes defined by Korman, Peleg and Fraigniaud. We define additional complexity classes: the class LD(t) consists of all languages which can be decided with at most t communication rounds. The class NLD-O(f) consists of all languages which can be verified by a local verifier such that the size of the certificates that are needed to verify the language are bounded by a function from O(f). Our main results are refined strict hierarchies within these nondeterministic classes.","lang":"eng"}],"file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-15T10:37:07Z","creator":"florida","date_created":"2018-03-15T10:37:07Z","file_size":534906,"file_name":"524-paper_01.pdf","file_id":"1296","access_level":"closed"}],"external_id":{"arxiv":["1311.7229"]},"ddc":["040"],"language":[{"iso":"eng"}]},{"user_id":"15504","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"526","type":"mastersthesis","status":"public","author":[{"first_name":"Alexander","last_name":"Mäcker","id":"13536","full_name":"Mäcker, Alexander"}],"date_created":"2017-10-17T12:42:35Z","publisher":"Universität Paderborn","date_updated":"2022-01-06T07:01:48Z","title":"Greedy Network Creation With Heavy And Light Edges","citation":{"bibtex":"@book{Mäcker_2013, title={Greedy Network Creation With Heavy And Light Edges}, publisher={Universität Paderborn}, author={Mäcker, Alexander}, year={2013} }","mla":"Mäcker, Alexander. <i>Greedy Network Creation With Heavy And Light Edges</i>. Universität Paderborn, 2013.","short":"A. Mäcker, Greedy Network Creation With Heavy And Light Edges, Universität Paderborn, 2013.","apa":"Mäcker, A. (2013). <i>Greedy Network Creation With Heavy And Light Edges</i>. Universität Paderborn.","chicago":"Mäcker, Alexander. <i>Greedy Network Creation With Heavy And Light Edges</i>. Universität Paderborn, 2013.","ieee":"A. Mäcker, <i>Greedy Network Creation With Heavy And Light Edges</i>. Universität Paderborn, 2013.","ama":"Mäcker A. <i>Greedy Network Creation With Heavy And Light Edges</i>. Universität Paderborn; 2013."},"year":"2013"},{"status":"public","type":"mastersthesis","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"_id":"537","user_id":"15504","year":"2013","citation":{"ieee":"S. Heindorf, <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn, 2013.","chicago":"Heindorf, Stefan. <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn, 2013.","ama":"Heindorf S. <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn; 2013.","apa":"Heindorf, S. (2013). <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn.","bibtex":"@book{Heindorf_2013, title={Dispersion of Multi-Robot Teams}, publisher={Universität Paderborn}, author={Heindorf, Stefan}, year={2013} }","short":"S. Heindorf, Dispersion of Multi-Robot Teams, Universität Paderborn, 2013.","mla":"Heindorf, Stefan. <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn, 2013."},"title":"Dispersion of Multi-Robot Teams","date_updated":"2022-01-06T07:01:50Z","publisher":"Universität Paderborn","date_created":"2017-10-17T12:42:37Z","author":[{"first_name":"Stefan","full_name":"Heindorf, Stefan","last_name":"Heindorf"}]},{"author":[{"full_name":"Graffi, Kalman","last_name":"Graffi","first_name":"Kalman"},{"first_name":"Vitaly","last_name":"Rapp","full_name":"Rapp, Vitaly"}],"date_created":"2017-10-17T12:42:37Z","date_updated":"2022-01-06T07:01:52Z","doi":"10.1109/ICCCN.2013.6614118","title":"Continuous Gossip-based Aggregation through Dynamic Information Aging","has_accepted_license":"1","page":"1-7","citation":{"short":"K. Graffi, V. Rapp, in: Proceedings of the International Conference on Computer Communications and Networks (ICCCN’13), 2013, pp. 1–7.","bibtex":"@inproceedings{Graffi_Rapp_2013, title={Continuous Gossip-based Aggregation through Dynamic Information Aging}, DOI={<a href=\"https://doi.org/10.1109/ICCCN.2013.6614118\">10.1109/ICCCN.2013.6614118</a>}, booktitle={Proceedings of the International Conference on Computer Communications and Networks (ICCCN’13)}, author={Graffi, Kalman and Rapp, Vitaly}, year={2013}, pages={1–7} }","mla":"Graffi, Kalman, and Vitaly Rapp. “Continuous Gossip-Based Aggregation through Dynamic Information Aging.” <i>Proceedings of the International Conference on Computer Communications and Networks (ICCCN’13)</i>, 2013, pp. 1–7, doi:<a href=\"https://doi.org/10.1109/ICCCN.2013.6614118\">10.1109/ICCCN.2013.6614118</a>.","apa":"Graffi, K., &#38; Rapp, V. (2013). Continuous Gossip-based Aggregation through Dynamic Information Aging. In <i>Proceedings of the International Conference on Computer Communications and Networks (ICCCN’13)</i> (pp. 1–7). <a href=\"https://doi.org/10.1109/ICCCN.2013.6614118\">https://doi.org/10.1109/ICCCN.2013.6614118</a>","ieee":"K. Graffi and V. Rapp, “Continuous Gossip-based Aggregation through Dynamic Information Aging,” in <i>Proceedings of the International Conference on Computer Communications and Networks (ICCCN’13)</i>, 2013, pp. 1–7.","chicago":"Graffi, Kalman, and Vitaly Rapp. “Continuous Gossip-Based Aggregation through Dynamic Information Aging.” In <i>Proceedings of the International Conference on Computer Communications and Networks (ICCCN’13)</i>, 1–7, 2013. <a href=\"https://doi.org/10.1109/ICCCN.2013.6614118\">https://doi.org/10.1109/ICCCN.2013.6614118</a>.","ama":"Graffi K, Rapp V. Continuous Gossip-based Aggregation through Dynamic Information Aging. In: <i>Proceedings of the International Conference on Computer Communications and Networks (ICCCN’13)</i>. ; 2013:1-7. doi:<a href=\"https://doi.org/10.1109/ICCCN.2013.6614118\">10.1109/ICCCN.2013.6614118</a>"},"year":"2013","department":[{"_id":"79"}],"user_id":"477","_id":"541","project":[{"name":"SFB 901","_id":"1"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"name":"SFB 901 - Project Area A","_id":"2"}],"file_date_updated":"2018-03-15T10:33:20Z","language":[{"iso":"eng"}],"ddc":["040"],"publication":"Proceedings of the International Conference on Computer Communications and Networks (ICCCN'13)","type":"conference","status":"public","file":[{"file_size":272960,"access_level":"closed","file_id":"1290","file_name":"541-Continuous.Gossip.based.Aggregation.Through.Dynamic.Information.Aging.pdf","date_updated":"2018-03-15T10:33:20Z","creator":"florida","date_created":"2018-03-15T10:33:20Z","success":1,"relation":"main_file","content_type":"application/pdf"}],"abstract":[{"lang":"eng","text":"Existing solutions for gossip-based aggregation in peer-to-peer networks use epochs to calculate a global estimation from an initial static set of local values. Once the estimation converges system-wide, a new epoch is started with fresh initial values. Long epochs result in precise estimations based on old measurements and short epochs result in imprecise aggregated estimations. In contrast to this approach, we present in this paper a continuous, epoch-less approach which considers fresh local values in every round of the gossip-based aggregation. By using an approach for dynamic information aging, inaccurate values and values from left peers fade from the aggregation memory. Evaluation shows that the presented approach for continuous information aggregation in peer-to-peer systems monitors the system performance precisely, adapts to changes and is lightweight to operate."}]},{"has_accepted_license":"1","page":"99-106","citation":{"ama":"Feldotto M, Graffi K. Comparative Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM. In: <i>Proceedings of the International Conference on High Performance Computing and Simulation (HPCS’13)</i>. ; 2013:99-106. doi:<a href=\"https://doi.org/10.1109/HPCSim.2013.6641399\">10.1109/HPCSim.2013.6641399</a>","chicago":"Feldotto, Matthias, and Kalman Graffi. “Comparative Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM.” In <i>Proceedings of the International Conference on High Performance Computing and Simulation (HPCS’13)</i>, 99–106, 2013. <a href=\"https://doi.org/10.1109/HPCSim.2013.6641399\">https://doi.org/10.1109/HPCSim.2013.6641399</a>.","ieee":"M. Feldotto and K. Graffi, “Comparative Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM,” in <i>Proceedings of the International Conference on High Performance Computing and Simulation (HPCS’13)</i>, 2013, pp. 99–106.","short":"M. Feldotto, K. Graffi, in: Proceedings of the International Conference on High Performance Computing and Simulation (HPCS’13), 2013, pp. 99–106.","bibtex":"@inproceedings{Feldotto_Graffi_2013, title={Comparative Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM}, DOI={<a href=\"https://doi.org/10.1109/HPCSim.2013.6641399\">10.1109/HPCSim.2013.6641399</a>}, booktitle={Proceedings of the International Conference on High Performance Computing and Simulation (HPCS’13)}, author={Feldotto, Matthias and Graffi, Kalman}, year={2013}, pages={99–106} }","mla":"Feldotto, Matthias, and Kalman Graffi. “Comparative Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM.” <i>Proceedings of the International Conference on High Performance Computing and Simulation (HPCS’13)</i>, 2013, pp. 99–106, doi:<a href=\"https://doi.org/10.1109/HPCSim.2013.6641399\">10.1109/HPCSim.2013.6641399</a>.","apa":"Feldotto, M., &#38; Graffi, K. (2013). Comparative Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM. In <i>Proceedings of the International Conference on High Performance Computing and Simulation (HPCS’13)</i> (pp. 99–106). <a href=\"https://doi.org/10.1109/HPCSim.2013.6641399\">https://doi.org/10.1109/HPCSim.2013.6641399</a>"},"year":"2013","date_created":"2017-10-17T12:42:38Z","author":[{"first_name":"Matthias","last_name":"Feldotto","orcid":"0000-0003-1348-6516","id":"14052","full_name":"Feldotto, Matthias"},{"first_name":"Kalman","full_name":"Graffi, Kalman","last_name":"Graffi"}],"date_updated":"2022-01-06T07:01:53Z","doi":"10.1109/HPCSim.2013.6641399","title":"Comparative Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM","publication":"Proceedings of the International Conference on High Performance Computing and Simulation (HPCS'13)","type":"conference","status":"public","file":[{"content_type":"application/pdf","relation":"main_file","success":1,"creator":"florida","date_created":"2018-03-15T10:32:17Z","date_updated":"2018-03-15T10:32:17Z","file_name":"544-FeldGraffi13.pdf","access_level":"closed","file_id":"1288","file_size":899441}],"abstract":[{"text":"Comparative evaluations of peer-to-peer protocols through simulations are a viable approach to judge the performance and costs of the individual protocols in large-scale networks. In order to support this work, we enhanced the peer-to-peer systems simulator PeerfactSim.KOM with a fine-grained analyzer concept, with exhaustive automated measurements and gnuplot generators as well as a coordination control to evaluate a set of experiment setups in parallel. Thus, by configuring all experiments and protocols only once and starting the simulator, all desired measurements are performed, analyzed, evaluated and combined, resulting in a holistic environment for the comparative evaluation of peer-to-peer systems.","lang":"eng"}],"department":[{"_id":"79"}],"user_id":"14052","_id":"544","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"file_date_updated":"2018-03-15T10:32:17Z","language":[{"iso":"eng"}],"ddc":["040"]},{"type":"bachelorsthesis","status":"public","user_id":"477","_id":"545","project":[{"_id":"1","name":"SFB 901"},{"_id":"5","name":"SFB 901 - Subprojekt A1"},{"_id":"2","name":"SFB 901 - Project Area A"}],"language":[{"iso":"ger"}],"citation":{"ama":"Blumentritt F. <i>Cliquenbildung in verteilten Systemen</i>. Universität Paderborn; 2013.","ieee":"F. Blumentritt, <i>Cliquenbildung in verteilten Systemen</i>. Universität Paderborn, 2013.","chicago":"Blumentritt, Fritz. <i>Cliquenbildung in verteilten Systemen</i>. Universität Paderborn, 2013.","bibtex":"@book{Blumentritt_2013, title={Cliquenbildung in verteilten Systemen}, publisher={Universität Paderborn}, author={Blumentritt, Fritz}, year={2013} }","mla":"Blumentritt, Fritz. <i>Cliquenbildung in verteilten Systemen</i>. Universität Paderborn, 2013.","short":"F. Blumentritt, Cliquenbildung in verteilten Systemen, Universität Paderborn, 2013.","apa":"Blumentritt, F. (2013). <i>Cliquenbildung in verteilten Systemen</i>. Universität Paderborn."},"year":"2013","date_created":"2017-10-17T12:42:38Z","author":[{"full_name":"Blumentritt, Fritz","last_name":"Blumentritt","first_name":"Fritz"}],"publisher":"Universität Paderborn","date_updated":"2022-01-06T07:01:54Z","title":"Cliquenbildung in verteilten Systemen"}]