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 -