TY - CONF
AU - Pukrop, Simon
AU - Mäcker, Alexander
AU - Meyer auf der Heide, Friedhelm
ID - 13868
T2 - Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)
TI - Approximating Weighted Completion Time for Order Scheduling with Setup Times
ER -
TY - CONF
AU - Feldkord, Björn
AU - Knollmann, Till
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
ID - 12870
T2 - Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA) (accepted)
TI - Managing Multiple Mobile Resources
ER -
TY - JOUR
AU - Feldkord, Björn
AU - Meyer auf der Heide, Friedhelm
ID - 13873
IS - 3
JF - ACM Transactions on Parallel Computing (TOPC)
TI - The Mobile Server Problem
VL - 6
ER -
TY - JOUR
AU - Meyer auf der Heide, Friedhelm
ID - 13937
IS - 2
JF - Mathematische Semesterberichte
TI - Paul Curzon, Peter W. McOwan: Computational Thinking; Die Welt des algorithmischen Denkens – in Spielen, Zaubertricks und Rätseln
VL - 66
ER -
TY - CHAP
AU - Kling, Peter
AU - Meyer auf der Heide, Friedhelm
ID - 13939
T2 - Distributed Computing by Mobile Entities, Current Research in Moving and Computing
TI - Continuous Protocols for Swarm Robotics
VL - 11340
ER -
TY - JOUR
AU - Abu-Khzam, Faisal N.
AU - Li, Shouwei
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
ID - 13946
JF - Theoretical Computer Science
TI - Efficient parallel algorithms for parameterized problems
VL - 786
ER -
TY - JOUR
AU - Karl, Holger
AU - Kundisch, Dennis
AU - Meyer auf der Heide, Friedhelm
AU - Wehrheim, Heike
ID - 13770
JF - Business & Information Systems Engineering
TI - A Case for a New IT Ecosystem: On-The-Fly Computing
ER -
TY - CONF
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
ID - 13942
T2 - Proceedings of the 8th International Conference on Operations Research and Enterprise Systems
TI - Online Algorithms for Leasing Vertex Cover and Leasing Non-metric Facility Location
ER -
TY - CONF
AU - Meyer auf der Heide, Friedhelm
AU - Schaefer, Johannes Sebastian
ID - 7570
SN - 9781450357999
T2 - Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18
TI - Brief Announcement: Communication in Systems of Home Based Mobile Agents
ER -
TY - CONF
AU - Hamann, Heiko
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
AU - Wahby, Mostafa
ID - 2850
T2 - Ninth International Conference on Fun with Algorithms (FUN)
TI - Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets
ER -
TY - JOUR
AU - Li, Shouwei
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
ID - 2848
IS - 5
JF - Algorithmica
TI - Towards Flexible Demands in Online Leasing Problems.
VL - 80
ER -
TY - CONF
AB - 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.
AU - Benter, Markus
AU - Knollmann, Till
AU - Meyer auf der Heide, Friedhelm
AU - Setzer, Alexander
AU - Sundermeier, Jannik
ID - 4375
KW - Distributed Storage
KW - Multi-Dimensional Range Queries
KW - Peer-to-Peer
KW - Hilbert Curve
T2 - Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)
TI - A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension
ER -
TY - JOUR
AU - König, Jürgen
AU - Mäcker, Alexander
AU - Meyer auf der Heide, Friedhelm
AU - Riechers, Sören
ID - 3551
IS - 4
JF - Journal of Combinatorial Optimization
TI - Scheduling with interjob communication on parallel processors
VL - 36
ER -
TY - JOUR
AU - Abu-Khzam, Faisal N.
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
AU - Schubert, Michael
ID - 2849
JF - Theory of Computing Systems
TI - Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks
ER -
TY - CONF
AU - Feldkord, Björn
AU - Meyer auf der Heide, Friedhelm
ID - 2485
T2 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
TI - Online Facility Location with Mobile Facilities
ER -
TY - JOUR
AU - Mäcker, Alexander
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
AU - Riechers, Sören
ID - 706
IS - 4
JF - Journal of Combinatorial Optimization
TI - Cost-efficient Scheduling on Machines from the Cloud
VL - 36
ER -
TY - CONF
AB - 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.
AU - Mäcker, Alexander
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
AU - Riechers, Sören
ID - 79
T2 - Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)
TI - Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times
VL - 10787
ER -
TY - CONF
AB - 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.
AU - Feldkord, Björn
AU - Meyer auf der Heide, Friedhelm
ID - 55
T2 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
TI - The Mobile Server Problem
ER -
TY - CONF
AB - 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.
AU - Abu-Khzam, Faisal N.
AU - Li, Shouwei
AU - Markarian, Christine
AU - Meyer auf der Heide, Friedhelm
AU - Podlipyan, Pavel
ID - 82
T2 - Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)
TI - Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
ER -
TY - JOUR
AU - Althaus, Ernst
AU - Brinkmann, Andre
AU - Kling, Peter
AU - Meyer auf der Heide, Friedhelm
AU - Nagel, Lars
AU - Riechers, Sören
AU - Sgall, Jiri
AU - Suess, Tim
ID - 63
JF - Journal of Scheduling
TI - Scheduling Shared Continuous Resources on Many-Cores
ER -