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 - 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 - 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 - 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 - 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
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 - 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 - THES
AU - Malatyali, Manuel
ID - 18975
TI - Big Data: Sublinear Algorithms for Distributed Data Streams
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 - 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 -