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 - TY - CHAP AU - Kling, Peter AU - Meyer auf der Heide, Friedhelm ID - 13939 T2 - Distributed Computing by Mobile Entities, Current Research in Moving and Computing TI - Continuous Protocols for Swarm Robotics VL - 11340 ER - TY - CONF AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm ID - 13942 T2 - Proceedings of the 8th International Conference on Operations Research and Enterprise Systems TI - Online Algorithms for Leasing Vertex Cover and Leasing Non-metric Facility Location ER - TY - JOUR AU - Abu-Khzam, Faisal N. AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Podlipyan, Pavel ID - 13946 JF - Theoretical Computer Science TI - Efficient parallel algorithms for parameterized problems VL - 786 ER - TY - CONF AU - Castenow, Jannik AU - Kolb, Christina AU - Scheideler, Christian ID - 14539 T2 - Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO) TI - A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks ER - TY - CONF AB - Competing firms tend to select similar locations for their stores. This phenomenon, called the principle of minimum differentiation, was captured by Hotelling with a landmark model of spatial competition but is still the object of an ongoing scientific debate. Although consistently observed in practice, many more realistic variants of Hotelling's model fail to support minimum differentiation or do not have pure equilibria at all. In particular, it was recently proven for a generalized model which incorporates negative network externalities and which contains Hotelling's model and classical selfish load balancing as special cases, that the unique equilibria do not adhere to minimum differentiation. Furthermore, it was shown that for a significant parameter range pure equilibria do not exist. We derive a sharp contrast to these previous results by investigating Hotelling's model with negative network externalities from an entirely new angle: approximate pure subgame perfect equilibria. This approach allows us to prove analytically and via agent-based simulations that approximate equilibria having good approximation guarantees and that adhere to minimum differentiation exist for the full parameter range of the model. Moreover, we show that the obtained approximate equilibria have high social welfare. AU - Feldotto, Matthias AU - Lenzner, Pascal AU - Molitor, Louise AU - Skopalik, Alexander ID - 10281 T2 - Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems TI - From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation ER - TY - GEN AU - Pukrop, Simon ID - 10344 TI - Scheduling Algorithms for Multi-Operation Jobs with Setups on a Single Machine ER - TY - CONF AB - We study the classic bin packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio while repacking items sparingly between updates. Formally, each item i has a movement cost c_i >= 0, and we want to use alpha * OPT bins and incur a movement cost gamma * c_i, either in the worst case, or in an amortized sense, for alpha, gamma as small as possible. We call gamma the recourse of the algorithm. This is motivated by cloud storage applications, where fully-dynamic bin packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure. AU - Feldkord, Björn AU - Feldotto, Matthias AU - Gupta, Anupam AU - Guruganesh, Guru AU - Kumar, Amit AU - Riechers, Sören AU - Wajc, David ED - Chatzigiannakis, Ioannis ED - Kaklamanis, Christos ED - Marx, Dániel ED - Sannella, Donald ID - 2484 SN - 1868-8969 T2 - 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) TI - Fully-Dynamic Bin Packing with Little Repacking VL - 107 ER - TY - CONF AU - Feldkord, Björn AU - Meyer auf der Heide, Friedhelm ID - 2485 T2 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) TI - Online Facility Location with Mobile Facilities ER - TY - GEN AB - 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. AU - Liedtke, David Jan ID - 25121 TI - Influence of Stationary Robots on Continuous Robot Formation Problems ER - TY - GEN AB - We introduce the \emph{Online Connected Dominating Set Leasing} problem (OCDSL) in which we are given an undirected connected graph $G = (V, E)$, a set $\mathcal{L}$ of lease types each characterized by a duration and cost, and a sequence of subsets of $V$ arriving over time. A node can be leased using lease type $l$ for cost $c_l$ and remains active for time $d_l$. The adversary gives in each step $t$ a subset of nodes that need to be dominated by a connected subgraph consisting of nodes active at time $t$. The goal is to minimize the total leasing costs. OCDSL contains the \emph{Parking Permit Problem}~\cite{PPP} as a special subcase and generalizes the classical offline \emph{Connected Dominating Set} problem~\cite{Guha1998}. It has an $\Omega(\log ^2 n + \log |\mathcal{L}|)$ randomized lower bound resulting from lower bounds for the \emph{Parking Permit Problem} and the \emph{Online Set Cover} problem~\cite{Alon:2003:OSC:780542.780558,Korman}, where $|\mathcal{L}|$ is the number of available lease types and $n$ is the number of nodes in the input graph. We give a randomized $\mathcal{O}(\log ^2 n + \log |\mathcal{L}| \log n)$-competitive algorithm for OCDSL. We also give a deterministic algorithm for a variant of OCDSL in which the dominating subgraph need not be connected, the \emph{Online Dominating Set Leasing} problem. The latter is based on a simple primal-dual approach and has an $\mathcal{O}(|\mathcal{L}| \cdot \Delta)$-competitive ratio, where $\Delta$ is the maximum degree of the input graph. AU - Markarian, Christine ID - 19978 T2 - arXiv:1805.02994 TI - Online Connected Dominating Set Leasing ER - TY - CONF AB - We consider a market where final products or services are compositions of a number of basic services. Users are asked to evaluate the quality of the composed product after purchase. The quality of the basic service influences the performance of the composed services but cannot be observed directly. The question we pose is whether it is possible to use user evaluations on composed services to assess the quality of basic services. We discuss how to combine aggregation of evaluations across users and disaggregation of information on composed services to derive valuations for the single components. As a solution we propose to use the (weighted) average as aggregation device in connection with the Shapley value as disaggregation method, since this combination fulfills natural requirements in our context. In addition, we address some occurring computational issues: We give an approximate solution concept using only a limited number of evaluations which guarantees nearly optimal results with reduced running time. Lastly, we show that a slightly modified Shapley value and the weighted average are still applicable if the evaluation profiles are incomplete. AU - Feldotto, Matthias AU - Haake, Claus-Jochen AU - Skopalik, Alexander AU - Stroh-Maraun, Nadja ID - 2831 SN - 978-1-4503-5916-0 T2 - Proceedings of the 13th Workshop on Economics of Networks, Systems and Computation (NetEcon 2018) TI - Disaggregating User Evaluations Using the Shapley Value ER - TY - JOUR AU - Li, Shouwei AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm ID - 2848 IS - 5 JF - Algorithmica TI - Towards Flexible Demands in Online Leasing Problems. VL - 80 ER - TY - JOUR AU - Abu-Khzam, Faisal N. AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Schubert, Michael ID - 2849 JF - Theory of Computing Systems TI - Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks ER - TY - CONF AU - Hamann, Heiko AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm AU - Wahby, Mostafa ID - 2850 T2 - Ninth International Conference on Fun with Algorithms (FUN) TI - Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets ER - TY - CONF AB - We study the Online Prize-collecting Node-weighted Steiner Forest problem (OPC-NWSF) in which we are given an undirected graph \(G=(V, E)\) with \(|V| = n\) and node-weight function \(w: V \rightarrow \mathcal {R}^+\). A sequence of k pairs of nodes of G, each associated with a penalty, arrives online. OPC-NWSF asks to construct a subgraph H such that each pair \(\{s, t\}\) is either connected (there is a path between s and t in H) or its associated penalty is paid. The goal is to minimize the weight of H and the total penalties paid. The current best result for OPC-NWSF is a randomized \(\mathcal {O}(\log ^4 n)\)-competitive algorithm due to Hajiaghayi et al. (ICALP 2014). We improve this by proposing a randomized \(\mathcal {O}(\log n \log k)\)-competitive algorithm for OPC-NWSF, which is optimal up to constant factor since OPC-NWSF has a randomized lower bound of \(\varOmega (\log ^2 n)\) due to Korman [11]. Moreover, our result also implies an improvement for two special cases of OPC-NWSF, the Online Prize-collecting Node-weighted Steiner Tree problem (OPC-NWST) and the Online Node-weighted Steiner Forest problem (ONWSF). In OPC-NWST, there is a distinguished node which is one of the nodes in each pair. In ONWSF, all penalties are set to infinity. The currently best known results for OPC-NWST and ONWSF are a randomized \(\mathcal {O}(\log ^3 n)\)-competitive algorithm due to Hajiaghayi et al. (ICALP 2014) and a randomized \(\mathcal {O}(\log n \log ^2 k)\)-competitive algorithm due to Hajiaghayi et al. (FOCS 2013), respectively. AU - Markarian, Christine ID - 24396 SN - 0302-9743 T2 - International Workshop on Combinatorial Algorithms (IWOCA) TI - An Optimal Algorithm for Online Prize-Collecting Node-Weighted Steiner Forest ER - TY - JOUR AU - König, Jürgen AU - Mäcker, Alexander AU - Meyer auf der Heide, Friedhelm AU - Riechers, Sören ID - 3551 IS - 4 JF - Journal of Combinatorial Optimization TI - Scheduling with interjob communication on parallel processors VL - 36 ER - TY - GEN AU - Koop, Samuel ID - 3851 TI - Congestion Games mit gewichteten Strategien ER - TY - CONF AB - Consider mitigating the effects of denial of service or of malicious traffic in networks by deleting edges. Edge deletion reduces the DoS or the number of the malicious flows, but it also inadvertently removes some of the desired flows. To model this important problem, we formulate two problems: (1) remove all the undesirable flows while minimizing the damage to the desirable ones and (2) balance removing the undesirable flows and not removing too many of the desirable flows. We prove these problems are equivalent to important theoretical problems, thereby being important not only practically but also theoretically, and very hard to approximate in a general network. We employ reductions to nonetheless approximate the problem and also provide a greedy approximation. When the network is a tree, the problems are still MAX SNP-hard, but we provide a greedy-based 2l-approximation algorithm, where l is the longest desirable flow. We also provide an algorithm, approximating the first and the second problem within {\$}{\$}2 {\backslash}sqrt{\{} 2{\backslash}left| E {\backslash}right| {\}}{\$}{\$}and {\$}{\$}2 {\backslash}sqrt{\{}2 ({\backslash}left| E {\backslash}right| + {\backslash}left| {\backslash}text {\{}undesirable flows{\}} {\backslash}right| ){\}}{\$}{\$}, respectively, where E is the set of the edges of the network. We also provide a fixed-parameter tractable (FPT) algorithm. Finally, if the tree has a root such that every flow in the tree flows on the path from the root to a leaf, we solve the problem exactly using dynamic programming. AU - Polevoy, Gleb AU - Trajanovski, Stojan AU - Grosso, Paola AU - de Laat, Cees ED - Kim, Donghyun ED - Uma, R. N. ED - Zelikovsky, Alexander ID - 17651 KW - flow KW - Red-Blue Set Cover KW - Positive-Negative Partial Set Cover KW - approximation KW - tree KW - MAX SNP-hard KW - root KW - leaf KW - dynamic programming KW - FPT SN - 978-3-030-04651-4 T2 - Combinatorial Optimization and Applications TI - Removing Undesirable Flows by Edge Deletion ER - TY - JOUR AB - Software Defined Networks (SDN) and Network Function Virtualisation (NFV) provide the basis for autonomous response and mitigation against attacks on networked computer infrastructures. We propose a new framework that uses SDNs and NFV to achieve this goal: Secure Autonomous Response Network (SARNET). In a SARNET, an agent running a control loop constantly assesses the security state of the network by means of observables. The agent reacts to and resolves security problems, while learning from its previous decisions. Two main metrics govern the decision process in a SARNET: impact and efficiency; these metrics can be used to compare and evaluate countermeasures and are the building blocks for self-learning SARNETs that exhibit autonomous response. In this paper we present the software implementation of the SARNET framework, evaluate it in a real-life network and discuss the tradeoffs between parameters used by the SARNET agent and the efficiency of its actions. AU - Koning, R. AU - de Graaff, B. AU - Polevoy, Gleb AU - Meijer, R. AU - de Laat, C. AU - Grosso, P. ID - 17666 JF - Future Generation Computer Systems KW - Software defined networks KW - Network function virtualization KW - Cyber attacks KW - Cyber security KW - Defense efficiency KW - Overlay networks SN - 0167-739X TI - Measuring the efficiency of SDN mitigations against attacks on computer infrastructures ER - TY - JOUR AU - Althaus, Ernst AU - Brinkmann, Andre AU - Kling, Peter AU - Meyer auf der Heide, Friedhelm AU - Nagel, Lars AU - Riechers, Sören AU - Sgall, Jiri AU - Suess, Tim ID - 63 IS - 1 JF - Journal of Scheduling TI - Scheduling Shared Continuous Resources on Many-Cores VL - 21 ER - TY - CONF AB - While a lot of 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. Considering crashing peers in peer-to-peer networks, it should not be taken for granted that a distributed data structure remains intact. In this work, 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 a wide area of applications including string matching problems 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 $\mathcal{O}(\log |x|)$ hash table read accesses. We show how to maintain the structure in a self-stabilizing way. Our protocol assures low overhead in a legal state and a total (asymptotically optimal) memory demand of $\Theta(d)$ bits, where $d$ is the number of bits needed for storing all keys. AU - Knollmann, Till AU - Scheideler, Christian ED - Izumi, Taisuke ED - Kuznetsov, Petr ID - 4411 KW - Self-Stabilizing KW - Prefix Search KW - Distributed Data Structure T2 - Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) TI - A Self-Stabilizing Hashed Patricia Trie VL - 11201 ER - TY - CONF AB - Routing is a challenging problem for wireless ad hoc networks, especially when the nodes are mobile and spread so widely that in most cases multiple hops are needed to route a message from one node to another. In fact, it is known that any online routing protocol has a poor performance in the worst case, in a sense that there is a distribution of nodes resulting in bad routing paths for that protocol, even if the nodes know their geographic positions and the geographic position of the destination of a message is known. The reason for that is that radio holes in the ad hoc network may require messages to take long detours in order to get to a destination, which are hard to find in an online fashion. In this paper, we assume that the wireless ad hoc network can make limited use of long-range links provided by a global communication infrastructure like a cellular infrastructure or a satellite in order to compute an abstraction of the wireless ad hoc network that allows the messages to be sent along near-shortest paths in the ad hoc network. We present distributed algorithms that compute an abstraction of the ad hoc network in $\mathcal{O}\left(\log ^2 n\right)$ time using long-range links, which results in $c$-competitive routing paths between any two nodes of the ad hoc network for some constant $c$ if the convex hulls of the radio holes do not intersect. We also show that the storage needed for the abstraction just depends on the number and size of the radio holes in the wireless ad hoc network and is independent on the total number of nodes, and this information just has to be known to a few nodes for the routing to work. AU - Jung, Daniel AU - Kolb, Christina AU - Scheideler, Christian AU - Sundermeier, Jannik ID - 4563 KW - greedy routing KW - ad hoc networks KW - convex hulls KW - c-competitiveness T2 - Proceedings of the 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) TI - Competitive Routing in Hybrid Communication Networks ER - TY - CONF AU - Jung, Daniel AU - Kolb, Christina AU - Scheideler, Christian AU - Sundermeier, Jannik ID - 4565 SN - 9781450357999 T2 - Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA) TI - Brief Announcement: Competitive Routing in Hybrid Communication Networks ER - TY - CONF AU - Meyer auf der Heide, Friedhelm AU - Schaefer, Johannes Sebastian ID - 7570 SN - 9781450357999 T2 - Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18 TI - Brief Announcement: Communication in Systems of Home Based Mobile Agents ER - TY - CONF AB - 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. AU - Benter, Markus AU - Knollmann, Till AU - Meyer auf der Heide, Friedhelm AU - Setzer, Alexander AU - Sundermeier, Jannik ID - 4375 KW - Distributed Storage KW - Multi-Dimensional Range Queries KW - Peer-to-Peer KW - Hilbert Curve T2 - Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD) TI - A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension ER - TY - GEN AU - Geromel, Marcel ID - 5403 TI - Mobile Facility Leasing ER - TY - GEN AU - Kolpaczki, Patrick Irenäus ID - 5404 TI - Online Algorithmen für das k-Page Migration Problem ER - TY - JOUR AB - We study a new class of games which generalizes congestion games andits bottleneck variant. We introduce congestion games with mixed objectives to modelnetwork scenarios in which players seek to optimize for latency and bandwidths alike.We characterize the (non-)existence of pure Nash equilibria (PNE), the convergenceof improvement dynamics, the quality of equilibria and show the complexity of thedecision problem. For games that do not possess PNE we give bounds on the approx-imation ratio of approximate pure Nash equilibria. AU - Feldotto, Matthias AU - Leder, Lennart AU - Skopalik, Alexander ID - 669 IS - 4 JF - Journal of Combinatorial Optimization SN - 1382-6905 TI - Congestion games with mixed objectives VL - 36 ER - TY - GEN AU - Kemper, Arne ID - 1186 TI - Pure Nash Equilibria in Robust Congestion Games via Potential Functions ER - TY - GEN AU - Nachtigall, Marcel ID - 1187 TI - Scenario-driven Strategy Analysis in a n-player Composition Game Model ER -