TY - JOUR
AU - Castenow, Jannik
AU - Harbig, Jonas
AU - Jung, Daniel
AU - Knollmann, Till
AU - Meyer auf der Heide, Friedhelm
ID - 33947
JF - Theoretical Computer Science
KW - General Computer Science
KW - Theoretical Computer Science
SN - 0304-3975
TI - Gathering a Euclidean Closed Chain of Robots in Linear Time and Improved Algorithms for Chain-Formation
VL - 939
ER -
TY - CONF
AU - Castenow, Jannik
AU - Harbig, Jonas
AU - Jung, Daniel
AU - Kling, Peter
AU - Knollmann, Till
AU - Meyer auf der Heide, Friedhelm
ED - Hillel, Eshcar
ED - Palmieri, Roberto
ED - Riviére, Etienne
ID - 34008
SN - 1868-8969
T2 - Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS)
TI - A Unifying Approach to Efficient (Near-)Gathering of Disoriented Robots with Limited Visibility
VL - 253
ER -
TY - JOUR
AU - Maack, Marten
ID - 44077
IS - 3
JF - Operations Research Letters
KW - Applied Mathematics
KW - Industrial and Manufacturing Engineering
KW - Management Science and Operations Research
KW - Software
SN - 0167-6377
TI - Online load balancing on uniform machines with limited migration
VL - 51
ER -
TY - CHAP
AU - Castenow, Jannik
AU - Harbig, Jonas
AU - Meyer auf der Heide, Friedhelm
ID - 44769
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Unifying Gathering Protocols for Swarms of Mobile Robots
ER -
TY - THES
AU - Castenow, Jannik
ID - 45580
TI - Local Protocols for Contracting and Expanding Robot Formation Problems
ER -
TY - THES
AU - Knollmann, Till
ID - 45579
TI - Online Algorithms for Allocating Heterogeneous Resources
ER -
TY - THES
AU - Pukrop, Simon
ID - 45781
TI - On Cloud Assisted, Restricted, and Reosurce Constrained Scheduling
ER -
TY - JOUR
AB - AbstractConsider a set of jobs connected to a directed acyclic task graph with a fixed source and sink. The edges of this graph model precedence constraints and the jobs have to be scheduled with respect to those. We introduce the server cloud scheduling problem, in which the jobs have to be processed either on a single local machine or on one of infinitely many cloud machines. For each job, processing times both on the server and in the cloud are given. Furthermore, for each edge in the task graph, a communication delay is included in the input and has to be taken into account if one of the two jobs is scheduled on the server and the other in the cloud. The server processes jobs sequentially, whereas the cloud can serve as many as needed in parallel, but induces costs. We consider both makespan and cost minimization. The main results are an FPTAS for the makespan objective for graphs with a constant source and sink dividing cut and strong hardness for the case with unit processing times and delays.
AU - Maack, Marten
AU - Meyer auf der Heide, Friedhelm
AU - Pukrop, Simon
ID - 50458
JF - Algorithmica
KW - Applied Mathematics
KW - Computer Science Applications
KW - General Computer Science
SN - 0178-4617
TI - Server Cloud Scheduling
ER -
TY - CONF
AU - Deppert, Max A.
AU - Jansen, Klaus
AU - Maack, Marten
AU - Pukrop, Simon
AU - Rau, Malin
ID - 50460
T2 - 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
TI - Scheduling with Many Shared Resources
ER -
TY - JOUR
AU - Castenow, Jannik
AU - Kling, Peter
AU - Knollmann, Till
AU - Meyer auf der Heide, Friedhelm
ID - 29843
JF - Information and Computation
KW - Computational Theory and Mathematics
KW - Computer Science Applications
KW - Information Systems
KW - Theoretical Computer Science
SN - 0890-5401
TI - A Discrete and Continuous Study of the Max-Chain-Formation Problem
ER -
TY - CONF
AB - The famous $k$-Server Problem covers plenty of resource allocation scenarios, and several variations have been studied extensively for decades. However, to the best of our knowledge, no research has considered the problem if the servers are not identical and requests can express which specific servers should serve them. Therefore, we present a new model generalizing the $k$-Server Problem by *preferences* of the requests and proceed to study it in a uniform metric space for deterministic online algorithms (the special case of paging).
In our model, requests can either demand to be answered by any server (*general requests*) or by a specific one (*specific requests*). If only general requests appear, the instance is one of the original $k$-Server Problem, and a lower bound for the competitive ratio of $k$ applies. If only specific requests appear, a solution with a competitive ratio of $1$ becomes trivial since there is no freedom regarding the servers' movements. Perhaps counter-intuitively, we show that if both kinds of requests appear, the lower bound raises to $2k-1$.
We study deterministic online algorithms in uniform metrics and present two algorithms. The first one has an adaptive competitive ratio dependent on the frequency of specific requests. It achieves a worst-case competitive ratio of $3k-2$ while it is optimal when only general or only specific requests appear (competitive ratio of $k$ and $1$, respectively). The second has a fixed close-to-optimal worst-case competitive ratio of $2k+14$. For the first algorithm, we show a lower bound of $3k-2$, while the second algorithm has a lower bound of $2k-1$ when only general requests appear.
The two algorithms differ in only one behavioral rule for each server that significantly influences the competitive ratio. Each server acting according to the rule allows approaching the worst-case lower bound, while it implies an increased lower bound for $k$-Server instances. In other words, there is a trade-off between performing well against instances of the $k$-Server Problem and instances containing specific requests. We also show that no deterministic online algorithm can be optimal for both kinds of instances simultaneously.
AU - Castenow, Jannik
AU - Feldkord, Björn
AU - Knollmann, Till
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
ID - 31847
KW - K-Server Problem
KW - Heterogeneity
KW - Online Caching
SN - 9781450391467
T2 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
TI - The k-Server with Preferences Problem
ER -
TY - CONF
AB - Consider the practical goal of making a desired action profile played,
when the planner can only change the payoffs, bound by
stringent constraints.
Applications include motivating people
to choose the closest school, the closest subway station, or to coordinate
on a communication protocol or an investment strategy.
Employing subsidies and tolls, we adjust the game so that choosing this predefined action profile
becomes strictly dominant.
Inspired mainly by the work of Monderer and Tennenholtz,
where the promised subsidies do not materialise in the not played
profiles, we provide a fair and individually rational game
adjustment, such that the total outside investments sum up
to zero at any profile, thereby facilitating easy and frequent
usage of our adjustment without bearing costs, even if some
players behave unexpectedly. The resultant action profile itself needs no
adjustment. Importantly, we also prove that our adjustment minimises
the general transfer among all such adjustments, counting the total subsidising and taxation.
AU - Polevoy, Gleb
AU - Dziubiński, Marcin
ED - De Raedt, Luc
ID - 34040
KW - adjustment
KW - strictly dominant
KW - fairness
KW - individually rational
KW - transfer
KW - tax
KW - subsidy
T2 - Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
TI - Fair, Individually Rational and Cheap Adjustment
ER -
TY - CONF
AU - Epstein, Leah
AU - Lassota, Alexandra
AU - Levin, Asaf
AU - Maack, Marten
AU - Rohwedder, Lars
ED - Berenbrink, Petra
ED - Monmege, Benjamin
ID - 33085
T2 - 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference)
TI - Cardinality Constrained Scheduling in Online Models
VL - 219
ER -
TY - CONF
AU - Maack, Marten
AU - Pukrop, Simon
AU - Rasmussen, Anna Rodriguez
ED - Chechik, Shiri
ED - Navarro, Gonzalo
ED - Rotenberg, Eva
ED - Herman, Grzegorz
ID - 33491
T2 - 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany
TI - (In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling
VL - 244
ER -
TY - JOUR
AU - Baswana, Surender
AU - Gupta, Shiv
AU - Knollmann, Till
ID - 31479
JF - Algorithmica
KW - Applied Mathematics
KW - Computer Science Applications
KW - General Computer Science
SN - 0178-4617
TI - Mincut Sensitivity Data Structures for the Insertion of an Edge
ER -
TY - CHAP
AU - Maack, Marten
AU - Meyer auf der Heide, Friedhelm
AU - Pukrop, Simon
ID - 29872
SN - 0302-9743
T2 - Approximation and Online Algorithms
TI - Server Cloud Scheduling
ER -
TY - JOUR
AB - While many research in distributed computing has covered solutions for self-stabilizing computing and topologies, there is far less work on self-stabilization for distributed data structures. However, when peers in peer-to-peer networks crash, a distributed data structure may not remain intact. We present a self-stabilizing protocol for a distributed data structure called the Hashed Patricia Trie (Kniesburges and Scheideler WALCOM'11) that enables efficient prefix search on a set of keys. The data structure has many applications while offering low overhead and efficient operations when embedded on top of a Distributed Hash Table. Especially, longest prefix matching for x can be done in O(log |x|) hash table read accesses. We show how to maintain the structure in a self-stabilizing way, while assuring a low overhead in a legal state and an asymptotically optimal memory demand of O(d) bits, where d is the number of bits needed for storing all keys.
AU - Knollmann, Till
AU - Scheideler, Christian
ID - 21096
JF - Information and Computation
SN - 0890-5401
TI - A self-stabilizing Hashed Patricia Trie
ER -
TY - CONF
AU - Castenow, Jannik
AU - Harbig, Jonas
AU - Jung, Daniel
AU - Knollmann, Till
AU - Meyer auf der Heide, Friedhelm
ED - Gasieniec, Leszek
ED - Klasing, Ralf
ED - Radzik, Tomasz
ID - 23730
T2 - Proceedings of the 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)
TI - Gathering a Euclidean Closed Chain of Robots in Linear Time
VL - 12961
ER -
TY - CONF
AB - Produktentstehung (PE) bezieht sich auf den Prozess der Planung und Entwicklung eines Produkts sowie der damit verbundenen Dienstleistungen von der ersten Idee bis zur Herstellung und zum Vertrieb. Während dieses Prozesses gibt es zahlreiche Aufgaben, die von menschlichem Fachwissen abhängen und typischerweise von erfahrenen Experten übernommen werden. Da sich das Feld der Künstlichen Intelligenz (KI) immer weiterentwickelt und seinen Weg in den Fertigungssektor findet, gibt es viele Möglichkeiten für eine Anwendung von KI, um bei der Lösung der oben genannten Aufgaben zu helfen. In diesem Paper geben wir einen umfassenden Überblick über den aktuellen Stand der Technik des Einsatzes von KI in der PE.
Im Detail analysieren wir 40 bestehende Surveys zu KI in der PE und 94 Case Studies, um herauszufinden, welche Bereiche der PE von der aktuellen Forschung in diesem Bereich vorrangig adressiert werden, wie ausgereift die diskutierten KI-Methoden sind und inwieweit datenzentrierte Ansätze in der aktuellen Forschung genutzt werden.
AU - Bernijazov, Ruslan
AU - Dicks, Alexander
AU - Dumitrescu, Roman
AU - Foullois, Marc
AU - Hanselle, Jonas Manuel
AU - Hüllermeier, Eyke
AU - Karakaya, Gökce
AU - Ködding, Patrick
AU - Lohweg, Volker
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
AU - Panzner, Melina
AU - Soltenborn, Christian
ID - 23779
KW - Artificial Intelligence Product Creation Literature Review
T2 - Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI-21)
TI - A Meta-Review on Artificial Intelligence in Product Creation
ER -
TY - JOUR
AU - Feldkord, Björn
AU - Knollmann, Till
AU - Malatyali, Manuel
AU - Meyer auf der Heide, Friedhelm
ID - 20683
JF - Theory of Computing Systems
TI - Managing Multiple Mobile Resources
VL - 65
ER -