TY - CONF AB - We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of a finite set \( S \) of commodities. Ravi and Sinha (SODA 2004) introduced the model as the \emph{Multi-Commodity Facility Location Problem} (MFLP) and considered it an offline optimization problem. The model itself is similar to the FLP: i.e., requests are located at points of a finite metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances. In addition, requests and facilities are heterogeneous; they request or offer multiple commodities out of $S$. A request has to be connected to a set of facilities jointly offering the commodities demanded by it. In comparison to the FLP, an algorithm has to decide not only if and where to place facilities, but also which commodities to offer at each. To the best of our knowledge we are the first to study the problem in its online variant in which requests, their positions and their commodities are not known beforehand but revealed over time. We present results regarding the competitive ratio. On the one hand, we show that heterogeneity influences the competitive ratio by developing a lower bound on the competitive ratio for any randomized online algorithm of \( \Omega ( \sqrt{|S|} + \frac{\log n}{\log \log n} ) \) that already holds for simple line metrics. Here, \( n \) is the number of requests. On the other side, we establish a deterministic \( \mathcal{O}(\sqrt{|S|} \cdot \log n) \)-competitive algorithm and a randomized \( \mathcal{O}(\sqrt{|S|} \cdot \frac{\log n}{\log \log n} ) \)-competitive algorithm. Further, we show that when considering a more special class of cost functions for the construction cost of a facility, the competitive ratio decreases given by our deterministic algorithm depending on the function. AU - Castenow, Jannik AU - Feldkord, Björn AU - Knollmann, Till AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm ID - 17370 KW - Online Multi-Commodity Facility Location KW - Competitive Ratio KW - Online Optimization KW - Facility Location Problem SN - 9781450369350 T2 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures TI - The Online Multi-Commodity Facility Location Problem ER - TY - CONF AU - Castenow, Jannik AU - Kling, Peter AU - Knollmann, Till AU - Meyer auf der Heide, Friedhelm ID - 17371 SN - 9781450369350 T2 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures TI - Brief Announcement: A Discrete and Continuous Study of the Max-Chain-Formation Problem: Slow Down to Speed up ER - TY - CONF AB - In this work, we initiate the research about the Gathering problem for robots with limited viewing range in the three-dimensional Euclidean space. In the Gathering problem, a set of initially scattered robots is required to gather at the same position. The robots' capabilities are very restricted -- they do not agree on any coordinate system or compass, have a limited viewing range, have no memory of the past and cannot communicate. We study the problem in two different time models, in FSYNC (fully synchronized discrete rounds) and the continuous time model. For FSYNC, we introduce the 3D-Go-To-The-Center-strategy and prove a runtime of $\Theta(n^2)$ that matches the currently best runtime bound for the same model in the Euclidean plane [SPAA'11]. Our main result is the generalization of contracting strategies (continuous time) from [Algosensors'17] to three dimensions. In contracting strategies, every robot that is located on the global convex hull of all robots' positions moves with full speed towards the inside of the convex hull. We prove a runtime bound of $O(\Delta \cdot n^{3/2})$ for any three-dimensional contracting strategy, where $\Delta$ denotes the diameter of the initial configuration. This comes up to a factor of $\sqrt{n}$ close to the lower bound of $\Omega (\Delta \cdot n)$ which is already true in two dimensions. In general, it might be hard for robots with limited viewing range to decide whether they are located on the global convex hull and which movement maintains the connectivity of the swarm, rendering the design of concrete contracting strategies a challenging task. We prove that the continuous variant of 3D-Go-To-The-Center is contracting and keeps the swarm connected. Moreover, we give a simple design criterion for three-dimensional contracting strategies that maintains the connectivity of the swarm and introduce an exemplary strategy based on this criterion. AU - Braun, Michael AU - Castenow, Jannik AU - Meyer auf der Heide, Friedhelm ID - 16968 T2 - Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO) TI - Local Gathering of Mobile Robots in Three Dimensions ER - TY - THES AU - Feldkord, Björn ID - 15631 TI - Mobile Resource Allocation ER - TY - JOUR AB - In software engineering, the imprecise requirements of a user are transformed to a formal requirements specification during the requirements elicitation process. This process is usually guided by requirements engineers interviewing the user. We want to partially automate this first step of the software engineering process in order to enable users to specify a desired software system on their own. With our approach, users are only asked to provide exemplary behavioral descriptions. The problem of synthesizing a requirements specification from examples can partially be reduced to the problem of grammatical inference, to which we apply an active coevolutionary learning approach. However, this approach would usually require many feedback queries to be sent to the user. In this work, we extend and generalize our active learning approach to receive knowledge from multiple oracles, also known as proactive learning. The ‘user oracle’ represents input received from the user and the ‘knowledge oracle’ represents available, formalized domain knowledge. We call our two-oracle approach the ‘first apply knowledge then query’ (FAKT/Q) algorithm. We compare FAKT/Q to the active learning approach and provide an extensive benchmark evaluation. As result we find that the number of required user queries is reduced and the inference process is sped up significantly. Finally, with so-called On-The-Fly Markets, we present a motivation and an application of our approach where such knowledge is available. AU - Wever, Marcel Dominik AU - van Rooijen, Lorijn AU - Hamann, Heiko ID - 15025 IS - 2 JF - Evolutionary Computation TI - Multi-Oracle Coevolutionary Learning of Requirements Specifications from Examples in On-The-Fly Markets VL - 28 ER - TY - CONF AU - Castenow, Jannik AU - Kolb, Christina AU - Scheideler, Christian ID - 15169 T2 - Proceedings of the 21st International Conference on Distributed Computing and Networking (ICDCN) TI - A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks ER - TY - JOUR AU - Castenow, Jannik AU - Fischer, Matthias AU - Harbig, Jonas AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ID - 16299 JF - Theoretical Computer Science SN - 0304-3975 TI - Gathering Anonymous, Oblivious Robots on a Grid VL - 815 ER - 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 - JOUR AU - Karl, Holger AU - Kundisch, Dennis AU - Meyer auf der Heide, Friedhelm AU - Wehrheim, Heike ID - 13770 IS - 6 JF - Business & Information Systems Engineering TI - A Case for a New IT Ecosystem: On-The-Fly Computing VL - 62 ER - TY - CONF AU - Baswana, Surender AU - Gupta, Shiv AU - Tulsyan, Ayush ID - 17432 T2 - 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) TI - Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient ER - TY - CONF AB - Resolving distributed attacks benefits from collaboration between networks. We present three approaches for the same multi-domain defensive action that can be applied in such an alliance: 1) Counteract Everywhere, 2) Minimize Countermeasures, and 3) Minimize Propagation. First, we provide a formula to compute efficiency of a defense; then we use this formula to compute the efficiency of the approaches under various circumstances. Finally, we discuss how task execution order and timing influence defense efficiency. Our results show that the Minimize Propagation approach is the most efficient method when defending against the chosen attack. AU - Koning, Ralph AU - Polevoy, Gleb AU - Meijer, Lydia AU - de Laat, Cees AU - Grosso, Paola ID - 17667 KW - computer network security KW - multinetwork environments KW - multidomain defensive action KW - task execution order KW - timing influence defense efficiency KW - distributed attacks KW - collaborative security defence approach KW - minimize propagation approach KW - minimize countermeasure approach KW - counteract everywhere approach KW - Conferences KW - Cloud computing KW - Computer crime KW - Edge computing KW - Security KW - Defense Approaches KW - Multi-Domain Defense KW - Collaborative Defense KW - Defense Algorithms KW - Computer Networks SN - null T2 - 2019 6th IEEE International Conference on Cyber Security and Cloud Computing (CSCloud)/ 2019 5th IEEE International Conference on Edge Computing and Scalable Cloud (EdgeCom) TI - Approaches for Collaborative Security Defences in Multi Network Environments ER - TY - THES AU - Malatyali, Manuel ID - 18975 TI - Big Data: Sublinear Algorithms for Distributed Data Streams ER - TY - THES AB - This thesis investigates approximate pure Nash equilibria in different game-theoretic models. In such an outcome, no player can improve her objective by more than a given factor through a deviation to another strategy. In the first part, we investigate two variants of Congestion Games in which the existence of pure Nash equilibria is guaranteed through a potential function argument. However, the computation of such equilibria might be hard. We construct and analyze approximation algorithms that enable the computation of states with low approximation factors in polynomial time. To show their guarantees we use sub games among players, bound the potential function values of arbitrary states and exploit a connection between Shapley and proportional cost shares. Furthermore, we apply and analyze sampling techniques for the computation of approximate Shapley values in different settings. In the second part, we concentrate on the existence of approximate pure Nash equilibria in games in which no pure Nash equilibria exist in general. In the model of Coevolving Opinion Formation Games, we bound the approximation guarantees for natural states nearly independent of the specific definition of the players' neighborhoods by applying a concept of virtual costs. For the special case of only one influential neighbor, we even show lower approximation factors for a natural strategy. Then, we investigate a two-sided Facility Location Game among facilities and clients on a line with an objective function consisting of distance and load. We show tight bounds on the approximation factor for settings with three facilities and infinitely many clients. For the general scenario with an arbitrary number of facilities, we bound the approximation factor for two promising candidates, namely facilities that are uniformly distributed and which are paired. AU - Feldotto, Matthias ID - 8080 TI - Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games ER - TY - CONF AU - Jansen, Klaus AU - Maack, Marten AU - Mäcker, Alexander ID - 8866 T2 - Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS) TI - Scheduling on (Un-)Related Machines with Setup Times ER - TY - CONF AB - We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular. Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1-e) approximation mechanism, matching the best known bounds for the single-item setting. AU - Lazos, Philip AU - Goldberg, Paul AU - Skopalik, Alexander AU - Gerstgrasser, Matthias AU - de Keijzer, Bart ID - 5471 T2 - Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI) TI - Multi-unit Bilateral Trade 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) TI - Managing Multiple Mobile Resources ER - TY - THES AU - Mäcker, Alexander ID - 14851 TI - On Scheduling with Setup Times ER - TY - GEN AB - We present a technique for rendering highly complex 3D scenes in real-time by generating uniformly distributed points on the scene's visible surfaces. The technique is applicable to a wide range of scene types, like scenes directly based on complex and detailed CAD data consisting of billions of polygons (in contrast to scenes handcrafted solely for visualization). This allows to visualize such scenes smoothly even in VR on a HMD with good image quality, while maintaining the necessary frame-rates. In contrast to other point based rendering methods, we place points in an approximated blue noise distribution only on visible surfaces and store them in a highly GPU efficient data structure, allowing to progressively refine the number of rendered points to maximize the image quality for a given target frame rate. Our evaluation shows that scenes consisting of a high amount of polygons can be rendered with interactive frame rates with good visual quality on standard hardware. AU - Brandt, Sascha AU - Jähn, Claudius AU - Fischer, Matthias AU - Meyer auf der Heide, Friedhelm ID - 16341 T2 - arXiv:1904.08225 TI - Rendering of Complex Heterogenous Scenes using Progressive Blue Surfels 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 -