TY - CONF
AB - We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the sum of the maintenance cost for the facilities and the connection cost for the clients is at most a constant factor larger than the current optimal cost. In our scenario, each point can open a facility and moves continuously along a known trajectory in a d-dimensional Euclidean space where d is a constant.
Our kinetic data structure has a storage requirement of O(n (log^d(n)+log(nR))), where n is the number of points and R is the ratio of the product of the maximum maintenance cost and demand to the product of their corresponding minimum values. In the case that each trajectory can be described by a bounded degree polynomial, the data structure processes O(n^2 log^2(nR)) events, each requiring only O(log(nR)) facility changes and O(log^(d+1)(n) log(nR)) time. This results in a total processing time of O(n^2 log^(d+1)(n) log^3(nR)). To the best of our knowledge, this is the first kinetic data structure for the facility location problem.
AU - Gehweiler, Joachim
AU - Lammersen, Christiane
AU - Degener, Bastian
ID - 19004
T2 - Proceedings of the 24th European Workshop on Computational Geometry
TI - The Kinetic Facility Location Problem
ER -
TY - CHAP
AU - Seng, Eva- Maria
ED - Stolzenberg, Jürgen
ID - 19073
T2 - Hallesche Beiträge zur Europäischen Aufklärung
TI - „… Der Hauptzweck ist, die große Welt … allhier im kleineren beisammen zu haben“. Kunst- und Wunderkammern als Bildungseinrichtungen
ER -
TY - BOOK
AU - Eke, Norbert Otto
AU - Olasz-Eke, Dagmar
ID - 19105
TI - Thomas Valentin Lesebuch (Edition)
VL - 16
ER -
TY - CHAP
AU - Eke, Norbert Otto
ED - Pontzen, Alexandra
ED - Preußer, Heinz-Peter
ID - 19319
T2 - Schuld und Scham
TI - „Gott schütz uns vor den guten Menschen“. Reinigungsrituale und Beschämungsstrategien im deutsch-jüdischen Verhältnis
VL - 3
ER -
TY - CHAP
AU - Eke, Norbert Otto
ID - 19460
T2 - Werner Fritsch/Johanna Fritsch: Das Meer rauscht und rauscht – bis es lauscht. Hörstück
TI - Vorwort
ER -
TY - GEN
AU - Eke, Norbert Otto
ID - 19509
IS - H. 1/2
T2 - Germanistik
TI - Stefan Hulfeld: Theatergeschichtsschreibung als kulturelle Praxis. Wie Wissen über Theater entsteht. Zürich: Chronos, 2007
VL - 49
ER -
TY - THES
AU - Lürwer-Brüggemeier, Katharina
ID - 19605
TI - Mächtigkeit und Komplexität von Berechnungen mit der ganzzahligen Division
ER -
TY - JOUR
AB - We present a game theoretic study of hybrid communication networks in which mobile devices can connect in an ad hoc fashion to a base station, possibly via a few hops using other mobile devices as intermediate nodes. The maximal number of allowed hops might be bounded with the motivation to guarantee small latency. We introduce hybrid connectivity games to study the impact of selfishness on this kind of infrastructure.
Mobile devices are represented by selfish players, each of which aims at establishing an uplink path to the base station minimizing its individual cost. Our model assumes that intermediate nodes on an uplink path are reimbursed for transmitting the packets of other devices. The reimbursements can be paid either by a benevolent network operator or by the senders of the packets using micropayments via a clearing agency that possibly collects a small percentage as commission. These different ways to implement the payments lead to different variants of the hybrid connectivity game. Our main findings are: (1) If there is no constraint on the number of allowed hops on the path to the base station, then the existence of equilibria is guaranteed regardless of whether the network operator or the senders pay for forwarding packets. (2) If the network operator pays, then the existence of equilibria is guaranteed only if at most one intermediate node is allowed, i.e., for at most two hops on the uplink path of a device, but not if the maximal number of allowed hops is three or larger. (3) In contrast, if the senders pay for forwarding their packets, then equilibria are guaranteed to exist given any bound on the number of allowed hops.
The equilibrium analysis presented in this paper gives a first game theoretical motivation for the implementation of micropayment schemes in which senders pay for forwarding their packets. We further support this evidence by giving an upper bound on the Price of Anarchy for this kind of hybrid connectivity games that is independent of the number of nodes, but only depends on the number of hops and the power gradient.
AU - Ackermann, Heiner
AU - Briest, Patrick
AU - Fanghänel, Alexander
AU - Vöcking, Berthold
ID - 18570
IS - 4
JF - Internet Mathematics
SN - 9783540771043
TI - Who Should Pay for Forwarding Packets?
VL - 5
ER -
TY - CONF
AU - Briest, Patrick
ID - 19686
SN - 0302-9743
T2 - Proceedings of the 35th InternationalColloquium on Automata, Languages and Programming (ICALP)
TI - Uniform Budgets and the Envy-Free Pricing Problem
ER -
TY - CONF
AB - The paper describes an approach for an aggregated animation of a simulation experiment in an interactive 3D environment, visualizing multiple, distributed simulation runs. Although the general approach of a 3-dimensional visualization of material flow simulation helps to understand the dynamic behavior of a system better as well as faster, it remains unclear, how typical the animated simulation represents the model, if there is a stochastic influence for even some parameters. By the integrated visualization of multiple distributed simulation runs, this uncertainty can be solved, which will be shown in this paper for a typical simulation study of a queuing system.
AU - Dangelmaier, Wilhelm
AU - Fischer, Matthias
AU - Huber, Daniel
AU - Laroque, Christoph
AU - Süß, Tim
ID - 17868
SN - 9781424427079
T2 - 2008 Winter Simulation Conference
TI - Aggregated 3D-visualization of a distributed simulation experiment of a queuing system
ER -