Disaggregating User Evaluations Using the Shapley Value - Feldotto, Matthias; Haake, Claus-Jochen; Skopalik, Alexander; Stroh-Maraun, Nadja (Proceedings of the 13th Workshop on Economics of Networks, Systems and Computation (NetEcon 2018))
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.

Towards Flexible Demands in Online Leasing Problems. - Li, Shouwei; Markarian, Christine; Meyer auf der Heide, Friedhelm (Algorithmica)

Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks - Abu-Khzam, Faisal N.; Markarian, Christine; Meyer auf der Heide, Friedhelm; Schubert, Michael (Theory of Computing Systems)

Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets - Hamann, Heiko; Markarian, Christine; Meyer auf der Heide, Friedhelm; Wahby, Mostafa (Ninth International Conference on Fun with Algorithms (FUN))

An Optimal Algorithm for Online Prize-Collecting Node-Weighted Steiner Forest - Markarian, Christine (International Workshop on Combinatorial Algorithms (IWOCA))
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 → \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.

Scheduling with interjob communication on parallel processors - König, Jürgen; Mäcker, Alexander; Meyer auf der Heide, Friedhelm; Riechers, Sören (Journal of Combinatorial Optimization)

Congestion Games mit gewichteten Strategien - Koop, Samuel

Removing Undesirable Flows by Edge Deletion - Polevoy, Gleb; Trajanovski, Stojan; Grosso, Paola; de Laat, Cees (Combinatorial Optimization and Applications)
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.
Keywords: flow; Red-Blue Set Cover; Positive-Negative Partial Set Cover; approximation; tree; MAX SNP-hard; root; leaf; dynamic programming; FPT

Measuring the efficiency of SDN mitigations against attacks on computer infrastructures - Koning, R.; de Graaff, B.; Polevoy, Gleb; Meijer, R.; de Laat, C.; Grosso, P. (Future Generation Computer Systems)
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.
Keywords: Software defined networks; Network function virtualization; Cyber attacks; Cyber security; Defense efficiency; Overlay networks

Scheduling Shared Continuous Resources on Many-Cores - Althaus, Ernst; Brinkmann, Andre; Kling, Peter; Meyer auf der Heide, Friedhelm; Nagel, Lars; Riechers, Sören; Sgall, Jiri; Suess, Tim (Journal of Scheduling)

A Self-Stabilizing Hashed Patricia Trie - Knollmann, Till; Scheideler, Christian (Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS))
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 $Θ(d)$ bits, where $d$ is the number of bits needed for storing all keys.
Keywords: Self-Stabilizing; Prefix Search; Distributed Data Structure

Competitive Routing in Hybrid Communication Networks - Jung, Daniel; Kolb, Christina; Scheideler, Christian; Sundermeier, Jannik (Proceedings of the 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS))
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.
Keywords: greedy routing; ad hoc networks; convex hulls; c-competitiveness

Brief Announcement: Competitive Routing in Hybrid Communication Networks - Jung, Daniel; Kolb, Christina; Scheideler, Christian; Sundermeier, Jannik (Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA))

Brief Announcement: Communication in Systems of Home Based Mobile Agents - Meyer auf der Heide, Friedhelm; Schaefer, Johannes Sebastian (Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures - SPAA '18)

A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension - Benter, Markus; Knollmann, Till; Meyer auf der Heide, Friedhelm; Setzer, Alexander; Sundermeier, Jannik (Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD))
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.
Keywords: Distributed Storage; Multi-Dimensional Range Queries; Peer-to-Peer; Hilbert Curve

Mobile Facility Leasing - Geromel, Marcel

Online Algorithmen für das k-Page Migration Problem - Kolpaczki, Patrick Irenäus

Congestion games with mixed objectives - Feldotto, Matthias; Leder, Lennart; Skopalik, Alexander (Journal of Combinatorial Optimization)
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.

Pure Nash Equilibria in Robust Congestion Games via Potential Functions - Kemper, Arne

Scenario-driven Strategy Analysis in a n-player Composition Game Model - Nachtigall, Marcel