@phdthesis{45580, author = {{Castenow, Jannik}}, title = {{{Local Protocols for Contracting and Expanding Robot Formation Problems}}}, doi = {{10.17619/UNIPB/1-1750}}, year = {{2023}}, } @phdthesis{45579, author = {{Knollmann, Till}}, title = {{{Online Algorithms for Allocating Heterogeneous Resources}}}, doi = {{10.17619/UNIPB/1-1751}}, year = {{2023}}, } @phdthesis{45781, author = {{Pukrop, Simon}}, title = {{{On Cloud Assisted, Restricted, and Reosurce Constrained Scheduling}}}, doi = {{10.17619/UNIPB/1-1768 }}, year = {{2023}}, } @misc{44234, author = {{Berger, Thilo Frederik}}, title = {{{Combining Mobility, Heterogeneity, and Leasing Approaches for Online Resource Allocation}}}, year = {{2021}}, } @misc{44233, author = {{Pranger, Sebastian}}, title = {{{Online k-Facility Reallocation using k-Server Algorithms}}}, year = {{2021}}, } @phdthesis{15631, author = {{Feldkord, Björn}}, title = {{{Mobile Resource Allocation}}}, doi = {{10.17619/UNIPB/1-869}}, year = {{2020}}, } @phdthesis{18975, author = {{Malatyali, Manuel}}, title = {{{Big Data: Sublinear Algorithms for Distributed Data Streams}}}, doi = {{10.17619/UNIPB/1-766}}, year = {{2019}}, } @phdthesis{14851, author = {{Mäcker, Alexander}}, title = {{{On Scheduling with Setup Times}}}, doi = {{10.17619/UNIPB/1-828}}, year = {{2019}}, } @misc{10344, author = {{Pukrop, Simon}}, publisher = {{Universität Paderborn}}, title = {{{Scheduling Algorithms for Multi-Operation Jobs with Setups on a Single Machine}}}, year = {{2019}}, } @misc{25121, abstract = {{We consider a group of $n$ autonomous mobile robots of which $m$ are stationary thus cannot move. Robots are represented by points in the Euclidean plane. They have no memory, do not communicate or share a common coordinate system and they move solely based on the positioning of other robots within their limited viewing range of 1. The goal is to gather the robots inside of the convex hull of all stationary robots. A variant of this problem, the general gathering problem, has been studied in various different time models. In this work, we consider a continuous time model, where robots continuously observe their neighbors, compute the next target of movement and move with a speed limit of 1 at any time. Regarding the robots' local strategy, we only study contracting algorithms in which every robot that is positioned on the border of the convex hull of all robots moves into this hull. We present a time bound of $\mathcal{O}(nd)$ for any general contracting algorithms in a configuration with only a single stationary robot. For configurations with more stationary robots, we prove that robots converge against the convex hull of all stationary robots and that no upper bound on the runtime exists. For the specific contracting algorithms Go-To-The-Left, Go-On-Bisector and Go-To-The-Middle, we provide linear time bounds.}}, author = {{Liedtke, David Jan}}, title = {{{Influence of Stationary Robots on Continuous Robot Formation Problems}}}, year = {{2018}}, } @misc{5403, author = {{Geromel, Marcel}}, publisher = {{Universität Paderborn}}, title = {{{Mobile Facility Leasing}}}, year = {{2018}}, } @misc{5404, author = {{Kolpaczki, Patrick Irenäus}}, publisher = {{Universität Paderborn}}, title = {{{Online Algorithmen für das k-Page Migration Problem}}}, year = {{2018}}, } @phdthesis{1209, abstract = {{My dissertation deals with the Gathering problem for swarms of n point-shaped robots on a grid, in which all robots of the swarm are supposed to gather at a previously undefined point. Special attention is paid to the strong limitation of robot capabilities. These include in particular the lack of global control, a global compass, global visibility and (global) communication skills. Furthermore, all robots are identical. The robots are given only local abilities. This includes a constant range of vision. The robots all work completely synchronously. In this work we present and analyze three different Gathering strategies in different robot models. We formally prove correctness and total running time: Chapter 4 focuses on minimizing the available robot capabilities. The underlying strategy completes the gathering in O(n^2) time. For the following Chapters 5 and 6, the aim is to optimize the total running time under using only local robot capabilities: We additionally allow a constant-sized memory and a constant number of locally visible statuses (lights, flags). For the strategies of both chapters we show an asymptotically optimal running time of O(n). Unlike in Chapters 4 and 5, we additionally restrict connectivity and vision to an initially given chain connectivity in Chapter 6, where two chain neighbors must have a distance of 1 from each other. A robot can only see and interact with a constant number of its direct chain neighbors.}}, author = {{Jung, Daniel}}, isbn = {{978-3-942647-99-1}}, publisher = {{Universität Paderborn}}, title = {{{Local Strategies for Swarm Formations on a Grid}}}, doi = {{10.17619/UNIPB/1-271}}, year = {{2018}}, } @phdthesis{19604, author = {{Li, Shouwei}}, title = {{{Parallel fixed parameter tractable problems}}}, doi = {{10.17619/UNIPB/1-252}}, year = {{2017}}, } @phdthesis{703, author = {{Podlipyan, Pavel}}, publisher = {{Universität Paderborn}}, title = {{{Local Algorithms for the Continuous Gathering Problem}}}, doi = {{10.17619/UNIPB/1-230}}, year = {{2017}}, } @phdthesis{704, author = {{Riechers, Sören}}, publisher = {{Universität Paderborn}}, title = {{{Scheduling with Scarce Resources}}}, doi = {{10.17619/UNIPB/1-231}}, year = {{2017}}, } @misc{688, author = {{Kutzias, Damian}}, publisher = {{Universität Paderborn}}, title = {{{Friendship Processes in Network Creation Games}}}, year = {{2016}}, } @misc{689, author = {{Schaefer, Johannes Sebastian}}, publisher = {{Universität Paderborn}}, title = {{{Routing Algorithms on Delayed Networks for Disaster Management Support}}}, year = {{2016}}, } @phdthesis{154, author = {{Cord-Landwehr, Andreas}}, isbn = {{978-3-942647-72-4}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Selfish Network Creation - On Variants of Network Creation Games}}}, volume = {{353}}, year = {{2016}}, } @phdthesis{267, author = {{Markarian, Christine}}, publisher = {{Universität Paderborn}}, title = {{{Online Resource Leasing}}}, year = {{2015}}, }