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 -