@article{16391, author = {{Degener, Bastian and Kempkes, Barbara and Kling, Peter and Meyer auf der Heide, Friedhelm}}, issn = {{2329-4949}}, journal = {{ACM Transactions on Parallel Computing}}, pages = {{1--18}}, title = {{{Linear and Competitive Strategies for Continuous Robot Formation Problems}}}, doi = {{10.1145/2742341}}, year = {{2015}}, } @unpublished{16397, abstract = {{In the gathering problem, n autonomous robots have to meet on a single point. We consider the gathering of a closed chain of point-shaped, anonymous robots on a grid. The robots only have local knowledge about a constant number of neighboring robots along the chain in both directions. Actions are performed in the fully synchronous time model FSYNC. Every robot has a limited memory that may contain one timestamp of the global clock, also visible to its direct neighbors. In this synchronous time model, there is no limited view gathering algorithm known to perform better than in quadratic runtime. The configurations that show the quadratic lower bound are closed chains. In this paper, we present the first sub-quadratic---in fact linear time---gathering algorithm for closed chains on a grid.}}, author = {{Abshoff, Sebastian and Andreas Cord-Landwehr, Andreas and Jung, Daniel and Meyer auf der Heide, Friedhelm}}, booktitle = {{ArXiv: 1501.04877}}, title = {{{Towards Gathering Robots with Limited View in Linear Time: The Closed Chain Case}}}, year = {{2015}}, } @misc{52655, author = {{Gausemeier, Jürgen and Grafe, M. and Meyer auf der Heide, Friedhelm}}, isbn = {{978-3-942647-61-8}}, title = {{{12. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung}}}, volume = {{ Band 342}}, year = {{2015}}, } @inproceedings{368, abstract = {{We consider the problem of scheduling a number of jobs on $m$ identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement r_j \in {0,1}. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their \emph{processing speeds}, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.In this paper, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include an efficient optimal algorithm for 2 processors. Moreover, we prove that balanced schedules yield a 2-1/m-approximation for a fixed number of processors. Such schedules are computed by our GreedyBalance algorithm, for which the bound is tight.}}, author = {{Brinkmann, Andre and Kling, Peter and Meyer auf der Heide, Friedhelm and Nagel, Lars and Riechers, Sören and Suess, Tim }}, booktitle = {{Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}}, pages = {{128--137}}, title = {{{Scheduling Shared Continuous Resources on Many-Cores}}}, doi = {{10.1145/2612669.2612698}}, year = {{2014}}, } @inproceedings{379, abstract = {{In the leasing variant of Set Cover presented by Anthony et al.[1], elements U arrive over time and must be covered by sets from a familyF of subsets of U. Each set can be leased for K different periods of time.Let |U| = n and |F| = m. Leasing a set S for a period k incurs a cost ckS and allows S to cover its elements for the next lk time steps. The objectiveis to minimize the total cost of the sets leased, such that elements arrivingat any time t are covered by sets which contain them and are leased duringtime t. Anthony et al. [1] gave an optimal O(log n)-approximation forthe problem in the offline setting, unless P = NP [22]. In this paper, wegive randomized algorithms for variants of Set Cover Leasing in the onlinesetting, including a generalization of Online Set Cover with Repetitionspresented by Alon et al. [2], where elements appear multiple times andmust be covered by a different set at each arrival. Our results improve theO(log2(mn)) competitive factor of Online Set Cover with Repetitions [2]to O(log d log(dn)) = O(logmlog(mn)), where d is the maximum numberof sets an element belongs to.}}, author = {{Abshoff, Sebastian and Markarian, Christine and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}}, pages = {{25--34}}, title = {{{Randomized Online Algorithms for Set Cover Leasing Problems}}}, doi = {{10.1007/978-3-319-12691-3_3}}, year = {{2014}}, } @inproceedings{380, abstract = {{Network creation games model the creation and usage costs of networks formed by n selfish nodes. Each node v can buy a set of edges, each for a fixed price α > 0. Its goal is to minimize its private costs, i.e., the sum (SUM-game, Fabrikant et al., PODC 2003) or maximum (MAX-game, Demaine et al., PODC 2007) of distances from v to all other nodes plus the prices of the bought edges. The above papers show the existence of Nash equilibria as well as upper and lower bounds for the prices of anarchy and stability. In several subsequent papers, these bounds were improved for a wide range of prices α. In this paper, we extend these models by incorporating quality-of-service aspects: Each edge cannot only be bought at a fixed quality (edge length one) for a fixed price α. Instead, we assume that quality levels (i.e., edge lengths) are varying in a fixed interval [βˇ,β^] , 0 series = {LNCS}}}, author = {{Cord-Landwehr, Andreas and Mäcker, Alexander and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 10th International Conference on Web and Internet Economics (WINE)}}, pages = {{423--428}}, title = {{{Quality of Service in Network Creation Games}}}, doi = {{10.1007/978-3-319-13129-0_34}}, year = {{2014}}, } @inproceedings{459, abstract = {{In this survey article, we discuss two algorithmic research areas that emerge from problems that arise when resources are offered in the cloud. The first area, online leasing, captures problems arising from the fact that resources in the cloud are not bought, but leased by cloud vendors. The second area, Distributed Storage Systems, deals with problems arising from so-called cloud federations, i.e., when several cloud providers are needed to fulfill a given task.}}, author = {{Kniesburges, Sebastian and Markarian, Christine and Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, booktitle = {{Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO)}}, pages = {{1--13}}, title = {{{Algorithmic Aspects of Resource Management in the Cloud}}}, doi = {{10.1007/978-3-319-09620-9_1}}, year = {{2014}}, } @book{16870, editor = {{Flocchini, Paola and Gao, Jie and Kranakis, Evangelos and Meyer auf der Heide, Friedhelm}}, isbn = {{9783642453458}}, issn = {{0302-9743}}, publisher = {{Springer}}, title = {{{Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013}}}, doi = {{10.1007/978-3-642-45346-5}}, volume = {{8243}}, year = {{2014}}, } @inbook{16394, author = {{Lukovszki, Tamás and Meyer auf der Heide, Friedhelm}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783319144719}}, issn = {{0302-9743}}, title = {{{Fast Collisionless Pattern Formation by Anonymous, Position-Aware Robots}}}, doi = {{10.1007/978-3-319-14472-6_17}}, year = {{2014}}, } @inbook{16395, author = {{Abshoff, Sebastian and Meyer auf der Heide, Friedhelm}}, booktitle = {{Structural Information and Communication Complexity}}, isbn = {{9783319096193}}, issn = {{0302-9743}}, title = {{{Continuous Aggregation in Dynamic Ad-Hoc Networks}}}, doi = {{10.1007/978-3-319-09620-9_16}}, year = {{2014}}, } @inproceedings{27054, author = {{Gausemeier, Jürgen and Grafe, Michael and Meyer auf der Heide, Friedhelm}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, Band 311 }}, title = {{{11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung}}}, volume = {{311}}, year = {{2013}}, } @inproceedings{17439, abstract = {{Viele virtuelle 3-D-Szenen im industriellen Bereich sind nicht gleichmäßig strukturiert, z.B. weil sie eine stark unterschiedliche Dichteverteilung der Polygone aufweisen. Für solch heterogene Daten existiert kein Algorithmus, der die Gesamtheit der Daten sowohl schnell als auch mit guter Qualität darstellen kann. Die Auswahl der richtigen Algorithmen für einzelne Szenenteile durch einen Experten ist zeitintensiv und in vielen Visualisierungssystemen nicht umzusetzen. Um dieses Problem zu lösen, setzt das hier vorgestellte Multi-Algorithmen-Rendering verschiedene Renderingalgorithmen gleichzeitig ein, um eine virtuelle 3-D-Szene darzustellen. Das Verfahren unterteilt die Szene dafür in einem Vorverarbeitungsschritt automatisch in geeignete Teilregionen und bestimmt deren Eigenschaften. Diese Daten werden zur Laufzeit dazu genutzt, um ständig für den aktuellen Standpunkt des Betrachters eine Abschätzung der Qualität und Laufzeit der zur Auswahl stehenden Renderingalgorithmen zu berechnen. Durch die Lösung eines Optimierungsproblems kann so bei vorgegebener Bildrate durch die passende Zuordnung der Algorithmen zu den Regionen die Bildqualität optimiert werden – bei automatischer Anpassung an die Leistungsfähigkeit der eingesetzten Hardware. In einer experimentellen Evaluierung vergleichen wir die Laufzeit und Bildqualität des Verfahrens mit denen verbreiteter Standardrenderingverfahren.}}, author = {{Petring, Ralf and Eikel, Benjamin and Jähn, Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm}}, booktitle = {{11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung}}, pages = {{49----60}}, title = {{{Darstellung heterogener 3-D-Szenen in Echtzeit}}}, volume = {{311}}, year = {{2013}}, } @inproceedings{17442, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung}}, pages = {{7--16}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Algorithmische Grundlagen für die Selbstorganisation von Roboterschwärmen}}}, volume = {{311}}, year = {{2013}}, } @proceedings{17443, editor = {{Gausemeier, Jürgen and Grafe, Michael and Meyer auf der Heide, Friedhelm}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung}}}, volume = {{311}}, year = {{2013}}, } @inproceedings{477, abstract = {{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.}}, author = {{Abshoff, Sebastian and Benter, Markus and Cord-Landwehr, Andreas and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}}, 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}}, pages = {{22--34}}, title = {{{Token Dissemination in Geometric Dynamic Networks}}}, doi = {{10.1007/978-3-642-45346-5_3}}, year = {{2013}}, } @inproceedings{507, abstract = {{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.}}, author = {{Abshoff, Sebastian and Benter, Markus and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS)}}, pages = {{11--22}}, title = {{{On Two-Party Communication Through Dynamic Networks}}}, doi = {{10.1007/978-3-319-03850-6_2}}, year = {{2013}}, } @unpublished{524, abstract = {{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.}}, author = {{Meyer auf der Heide, Friedhelm and Swirkot, Kamil}}, publisher = {{arXiv}}, title = {{{Hierarchies in Local Distributed Decision}}}, year = {{2013}}, } @proceedings{558, editor = {{Flocchini, Paola and Gao, Jie and Kranakis, Evangelos and Meyer auf der Heide, Friedhelm}}, location = {{Sophia Antipolis, France}}, publisher = {{Springer}}, title = {{{Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics}}}, doi = {{10.1007/978-3-642-45346-5}}, volume = {{8243}}, year = {{2013}}, } @inproceedings{563, abstract = {{Dominating set based virtual backbones are used for rou-ting in wireless ad-hoc networks. Such backbones receive and transmit messages from/to every node in the network. Existing distributed algorithms only consider undirected graphs, which model symmetric networks with uniform transmission ranges. We are particularly interested in the well-established disk graphs, which model asymmetric networks with non-uniform transmission ranges. The corresponding graph theoretic problem seeks a strongly connected dominating-absorbent set of minimum cardinality in a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent set if the subgraph induced by these nodes is strongly connected and each node in the graph is either in the set or has both an in-neighbor and an out-neighbor in it. We introduce the first distributed algorithm for this problem in disk graphs. The algorithm gives an O(k^4) -approximation ratio and has a runtime bound of O(Diam) where Diam is the diameter of the graph and k denotes the transmission ratio r_{max}/r_{min} with r_{max} and r_{min} being the maximum and minimum transmission range, respectively. Moreover, we apply our algorithm on the subgraph of disk graphs consisting of only bidirectional edges. Our algorithm gives an O(ln k) -approximation and a runtime bound of O(k^8 log^∗ n) , which, for bounded k , is an optimal approximation for the problem, following Lenzen and Wattenhofer’s Ω(log^∗ n) runtime lower bound for distributed constant approximation in disk graphs.}}, author = {{Markarian, Christine and Meyer auf der Heide, Friedhelm and Schubert, Michael}}, booktitle = {{Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)}}, pages = {{217--227}}, title = {{{A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks}}}, doi = {{10.1007/978-3-642-45346-5_16}}, year = {{2013}}, } @inproceedings{16393, abstract = {{Many 3D scenes (e.g. generated from CAD data) are composed of a multitude of objects that are nested in each other. A showroom, for instance, may contain multiple cars and every car has a gearbox with many gearwheels located inside. Because the objects occlude each other, only few are visible from outside. We present a new technique, Spherical Visibility Sampling (SVS), for real-time 3D rendering of such -- possibly highly complex -- scenes. SVS exploits the occlusion and annotates hierarchically structured objects with directional visibility information in a preprocessing step. For different directions, the directional visibility encodes which objects of a scene's region are visible from the outside of the regions' enclosing bounding sphere. Since there is no need to store a separate view space subdivision as in most techniques based on preprocessed visibility, a small memory footprint is achieved. Using the directional visibility information for an interactive walkthrough, the potentially visible objects can be retrieved very efficiently without the need for further visibility tests. Our evaluation shows that using SVS allows to preprocess complex 3D scenes fast and to visualize them in real time (e.g. a Power Plant model and five animated Boeing 777 models with billions of triangles). Because SVS does not require hardware support for occlusion culling during rendering, it is even applicable for rendering large scenes on mobile devices.}}, author = {{Eikel, Benjamin and Jähn, Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm}}, booktitle = {{Computer Graphics Forum}}, issn = {{0167-7055}}, number = {{4}}, pages = {{49--58}}, title = {{{Spherical Visibility Sampling}}}, doi = {{10.1111/cgf.12150}}, volume = {{32}}, year = {{2013}}, }