@inproceedings{4375, abstract = {{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.\\ The network is the same for each dimension, namely a distance halving network like the one introduced by Naor and Wieder (ACM TALG'07). We 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. Furthermore, 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. Our algorithms are based on a mapping of the Hilbert Curve through $[m]^d$ to the peers.}}, author = {{Benter, Markus and Knollmann, Till and Meyer auf der Heide, Friedhelm and Setzer, Alexander and Sundermeier, Jannik}}, booktitle = {{Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)}}, keywords = {{Distributed Storage, Multi-Dimensional Range Queries, Peer-to-Peer, Hilbert Curve}}, location = {{Helsinki}}, title = {{{A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension}}}, doi = {{10.1007/978-3-030-19759-9_4}}, year = {{2018}}, } @inbook{16392, author = {{Feldkord, Björn and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}}, booktitle = {{Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications}}, isbn = {{9783319125671}}, issn = {{0302-9743}}, title = {{{A Dynamic Distributed Data Structure for Top-k and k-Select Queries}}}, doi = {{10.1007/978-3-319-98355-4_18}}, year = {{2018}}, } @misc{28231, author = {{Bodden, Eric and Dressler, Falko and Meyer auf der Heide, Friedhelm and Scheytt, Christoph and Trächtler, Ansgar}}, isbn = {{978-3-942647-88-5}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Intelligente technische Systeme}}}, volume = {{369}}, year = {{2017}}, } @book{24221, abstract = {{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).}}, 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}}, isbn = {{978-3-942647-88-5}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)}}}, doi = {{10.17619/UNIPB/1-93}}, volume = {{369}}, year = {{2017}}, } @book{27415, editor = {{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}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts}}, title = {{{Wissenschaftsforum Intelligente Technische Systeme (WInTeSys). , Band 369}}}, volume = {{369}}, year = {{2017}}, } @unpublished{17811, abstract = {{We consider a swarm of $n$ autonomous mobile robots, distributed on a 2-dimensional grid. A basic task for such a swarm is the gathering process: All robots have to gather at one (not predefined) place. A common local model for extremely simple robots is the following: The robots do not have a common compass, only have a constant viewing radius, are autonomous and indistinguishable, can move at most a constant distance in each step, cannot communicate, are oblivious and do not have flags or states. The only gathering algorithm under this robot model, with known runtime bounds, needs $\mathcal{O}(n^2)$ rounds and works in the Euclidean plane. The underlying time model for the algorithm is the fully synchronous $\mathcal{FSYNC}$ model. On the other side, in the case of the 2-dimensional grid, the only known gathering algorithms for the same time and a similar local model additionally require a constant memory, states and "flags" to communicate these states to neighbors in viewing range. They gather in time $\mathcal{O}(n)$. In this paper we contribute the (to the best of our knowledge) first gathering algorithm on the grid that works under the same simple local model as the above mentioned Euclidean plane strategy, i.e., without memory (oblivious), "flags" and states. We prove its correctness and an $\mathcal{O}(n^2)$ time bound in the fully synchronous $\mathcal{FSYNC}$ time model. This time bound matches the time bound of the best known algorithm for the Euclidean plane mentioned above. We say gathering is done if all robots are located within a $2\times 2$ square, because in $\mathcal{FSYNC}$ such configurations cannot be solved.}}, author = {{Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm}}, booktitle = {{arXiv:1702.03400}}, title = {{{Gathering Anonymous, Oblivious Robots on a Grid}}}, year = {{2017}}, } @book{23010, 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}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)}}}, volume = {{369}}, year = {{2017}}, } @inproceedings{79, abstract = {{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.}}, author = {{Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}}, booktitle = {{Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)}}, pages = {{207--222}}, publisher = {{Springer}}, title = {{{Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times}}}, doi = {{10.1007/978-3-319-89441-6}}, volume = {{10787}}, year = {{2017}}, } @inproceedings{82, abstract = {{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.}}, author = {{Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}}, booktitle = {{Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)}}, pages = {{139--150}}, title = {{{Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity}}}, doi = {{10.1007/978-3-319-59605-1_13}}, year = {{2017}}, } @inproceedings{70, author = {{Feldkord, Björn and Markarian, Christine and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}}, pages = {{17 -- 31}}, title = {{{Price Fluctuations in Online Leasing}}}, doi = {{10.1007/978-3-319-71147-8_2}}, year = {{2017}}, } @article{706, author = {{Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}}, journal = {{Journal of Combinatorial Optimization}}, number = {{4}}, pages = {{1168--1194}}, publisher = {{Springer}}, title = {{{Cost-efficient Scheduling on Machines from the Cloud}}}, doi = {{10.1007/s10878-017-0198-x}}, volume = {{36}}, year = {{2017}}, } @inproceedings{55, abstract = {{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.}}, author = {{Feldkord, Björn and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}}, pages = {{313--319}}, title = {{{The Mobile Server Problem}}}, doi = {{10.1145/3087556.3087575}}, year = {{2017}}, } @book{16444, 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}}, pages = {{369}}, title = {{{Wissenschaftsforum Intelligente Technische Systeme (WInTeSys)}}}, year = {{2017}}, } @inbook{16461, 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 Riechers, Sören and Schaefer, Johannes Sebastian and Sundermeier, Jannik}}, booktitle = {{Structural Information and Communication Complexity}}, isbn = {{9783319720494}}, issn = {{0302-9743}}, title = {{{Monitoring of Domain-Related Problems in Distributed Data Streams}}}, doi = {{10.1007/978-3-319-72050-0_13}}, year = {{2017}}, } @inproceedings{16347, author = {{Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm}}, booktitle = {{Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, {ALGOSENSORS}}}, editor = {{Fernández Anta, Antonio and Jurdzinski, Tomasz and Mosteiro, Miguel A. and Zhang, Yanyong}}, pages = {{168--181}}, publisher = {{Springer}}, title = {{{Gathering Anonymous, Oblivious Robots on a Grid}}}, doi = {{10.1007/978-3-319-72751-6_13}}, volume = {{10718}}, year = {{2017}}, } @inproceedings{16348, author = {{Biermeier, Felix and Feldkord, Björn and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)}}, pages = {{285 -- 300}}, publisher = {{Springer}}, title = {{{A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries}}}, doi = {{10.1007/978-3-319-89441-6_21}}, year = {{2017}}, } @inproceedings{16349, author = {{Podlipyan, Pavel and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS)}}, pages = {{182--197}}, title = {{{A Continuous Strategy for Collisionless Gathering}}}, doi = {{10.1007/978-3-319-72751-6_14 }}, year = {{2017}}, } @inproceedings{177, abstract = {{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.}}, author = {{Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}}, booktitle = {{Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA)}}, pages = {{477--488}}, title = {{{On the Parameterized Parallel Complexity and the Vertex Cover Problem}}}, doi = {{10.1007/978-3-319-48749-6_35}}, year = {{2016}}, } @misc{187, booktitle = {{Transactions on Parallel Computing (TOPC)}}, editor = {{Meyer auf der Heide, Friedhelm}}, number = {{1}}, pages = {{1}}, title = {{{Introduction to the Special Issue on SPAA 2014}}}, doi = {{10.1145/2936716}}, year = {{2016}}, } @inproceedings{207, abstract = {{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}}}, author = {{Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}}, booktitle = {{Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}}, pages = {{578----592}}, title = {{{Cost-efficient Scheduling on Machines from the Cloud}}}, doi = {{10.1007/978-3-319-48749-6_42}}, year = {{2016}}, }