@inproceedings{13868,
author = {Pukrop, Simon and Mäcker, Alexander and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)},
title = {{Approximating Weighted Completion Time for Order Scheduling with Setup Times}},
year = {2020},
}
@article{13873,
author = {Feldkord, Björn and Meyer auf der Heide, Friedhelm},
journal = {ACM Transactions on Parallel Computing (TOPC)},
number = {3},
title = {{The Mobile Server Problem}},
doi = {10.1145/3364204},
volume = {6},
year = {2019},
}
@inproceedings{12870,
author = {Feldkord, Björn and Knollmann, Till and Malatyali, Manuel and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA) (accepted)},
publisher = {Springer},
title = {{Managing Multiple Mobile Resources}},
year = {2019},
}
@article{13937,
author = {Meyer auf der Heide, Friedhelm},
journal = {Mathematische Semesterberichte},
number = {2},
pages = {259--260},
title = {{Paul Curzon, Peter W. McOwan: Computational Thinking; Die Welt des algorithmischen Denkens – in Spielen, Zaubertricks und Rätseln}},
doi = {10.1007/s00591-019-00249-0},
volume = {66},
year = {2019},
}
@inbook{13939,
author = {Kling, Peter and Meyer auf der Heide, Friedhelm},
booktitle = {Distributed Computing by Mobile Entities, Current Research in Moving and Computing},
pages = {317--334},
publisher = {Springer},
title = {{Continuous Protocols for Swarm Robotics}},
doi = {10.1007/978-3-030-11072-7\_13},
volume = {11340},
year = {2019},
}
@article{13946,
author = {Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm},
journal = {Theoretical Computer Science},
pages = {2--12},
title = {{Efficient parallel algorithms for parameterized problems}},
doi = {10.1016/j.tcs.2018.11.006},
volume = {786},
year = {2019},
}
@article{13770,
author = {Karl, Holger and Kundisch, Dennis and Meyer auf der Heide, Friedhelm and Wehrheim, Heike},
journal = {Business & Information Systems Engineering},
publisher = {Springer},
title = {{A Case for a New IT Ecosystem: On-The-Fly Computing}},
doi = {10.1007/s12599-019-00627-x},
year = {2019},
}
@inproceedings{13942,
author = {Markarian, Christine and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 8th International Conference on Operations Research and Enterprise Systems},
pages = {315--321},
publisher = {SciTePress},
title = {{Online Algorithms for Leasing Vertex Cover and Leasing Non-metric Facility Location}},
doi = {10.5220/0007369503150321},
year = {2019},
}
@inproceedings{7570,
author = {Meyer auf der Heide, Friedhelm and Schaefer, Johannes Sebastian},
booktitle = {Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18},
isbn = {9781450357999},
location = {Vienna},
publisher = {ACM Press},
title = {{Brief Announcement: Communication in Systems of Home Based Mobile Agents}},
doi = {10.1145/3210377.3210662},
year = {2018},
}
@inproceedings{2850,
author = {Hamann, Heiko and Markarian, Christine and Meyer auf der Heide, Friedhelm and Wahby, Mostafa},
booktitle = {Ninth International Conference on Fun with Algorithms (FUN)},
title = {{Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets}},
doi = {10.4230/LIPIcs.FUN.2018.22},
year = {2018},
}
@article{2848,
author = {Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm},
journal = {Algorithmica},
number = {5},
pages = {1556–1574},
publisher = {Springer},
title = {{Towards Flexible Demands in Online Leasing Problems. }},
doi = {10.1007/s00453-018-0420-y},
volume = {80},
year = {2018},
}
@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)},
keyword = {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},
}
@article{3551,
author = {König, Jürgen and Mäcker, Alexander and Meyer auf der Heide, Friedhelm and Riechers, Sören},
journal = {Journal of Combinatorial Optimization},
number = {4},
pages = {1356--1379},
title = {{Scheduling with interjob communication on parallel processors}},
doi = {10.1007/s10878-018-0325-3},
volume = {36},
year = {2018},
}
@article{2849,
author = {Abu-Khzam, Faisal N. and Markarian, Christine and Meyer auf der Heide, Friedhelm and Schubert, Michael},
journal = {Theory of Computing Systems},
publisher = {Springer},
title = {{Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks}},
doi = {10.1007/s00224-017-9836-z},
year = {2018},
}
@inproceedings{2485,
author = {Feldkord, Björn and Meyer auf der Heide, Friedhelm},
booktitle = {Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
location = {Wien},
pages = {373 -- 381 },
publisher = {ACM},
title = {{Online Facility Location with Mobile Facilities}},
doi = {10.1145/3210377.3210389},
year = {2018},
}
@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{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{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},
}
@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},
}
@article{63,
author = {Althaus, Ernst and Brinkmann, Andre and Kling, Peter and Meyer auf der Heide, Friedhelm and Nagel, Lars and Riechers, Sören and Sgall, Jiri and Suess, Tim},
journal = {Journal of Scheduling},
publisher = {Springer},
title = {{Scheduling Shared Continuous Resources on Many-Cores}},
doi = {10.1007/s10951-017-0518-0},
year = {2017},
}