@inproceedings{563,
  abstract     = {{Dominating set based virtual backbones are used for rou-ting in wireless ad-hoc networks. Such backbones receive and transmit messages from/to every node in the network. Existing distributed algorithms only consider undirected graphs, which model symmetric networks with uniform transmission ranges. We are particularly interested in the well-established disk graphs, which model asymmetric networks with non-uniform transmission ranges. The corresponding graph theoretic problem seeks a strongly connected dominating-absorbent set of minimum cardinality in a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent set if the subgraph induced by these nodes is strongly connected and each node in the graph is either in the set or has both an in-neighbor and an out-neighbor in it. We introduce the first distributed algorithm for this problem in disk graphs. The algorithm gives an O(k^4) -approximation ratio and has a runtime bound of O(Diam) where Diam is the diameter of the graph and k denotes the transmission ratio r_{max}/r_{min} with r_{max} and r_{min} being the maximum and minimum transmission range, respectively. Moreover, we apply our algorithm on the subgraph of disk graphs consisting of only bidirectional edges. Our algorithm gives an O(ln k) -approximation and a runtime bound of O(k^8 log^∗ n) , which, for bounded k , is an optimal approximation for the problem, following Lenzen and Wattenhofer’s Ω(log^∗ n) runtime lower bound for distributed constant approximation in disk graphs.}},
  author       = {{Markarian, Christine and Meyer auf der Heide, Friedhelm and Schubert, Michael}},
  booktitle    = {{Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)}},
  pages        = {{217--227}},
  title        = {{{A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks}}},
  doi          = {{10.1007/978-3-642-45346-5_16}},
  year         = {{2013}},
}

@inproceedings{564,
  abstract     = {{We consider the problem of resource discovery in distributed systems. In particular we give an algorithm, such that each node in a network discovers the add ress of any other node in the network. We model the knowledge of the nodes as a virtual overlay network given by a directed graph such that complete knowledge of all nodes corresponds to a complete graph in the overlay network. Although there are several solutions for resource discovery, our solution is the first that achieves worst-case optimal work for each node, i.e. the number of addresses (O(n)) or bits (O(nlogn)) a node receives or sendscoincides with the lower bound, while ensuring only a linearruntime (O(n)) on the number of rounds.}},
  author       = {{Kniesburges, Sebastian and Koutsopoulos, Andreas and Scheideler, Christian}},
  booktitle    = {{Proceedings of 20th International Colloqium on Structural Information and Communication Complexity (SIROCCO)}},
  pages        = {{165--176}},
  title        = {{{A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery}}},
  doi          = {{10.1007/978-3-319-03578-9_14}},
  year         = {{2013}},
}

@article{2519,
  author       = {{Haake, Claus-Jochen and Martini, Jan Thomas}},
  issn         = {{0926-2644}},
  journal      = {{Group Decision and Negotiation}},
  number       = {{4}},
  pages        = {{657--680}},
  publisher    = {{Springer Nature}},
  title        = {{{Negotiating Transfer Prices}}},
  doi          = {{10.1007/s10726-012-9286-6}},
  volume       = {{22}},
  year         = {{2012}},
}

@article{2521,
  author       = {{Haake, Claus-Jochen and Krieger, Tim and Minter, Steffen}},
  issn         = {{1612-4804}},
  journal      = {{International Economics and Economic Policy}},
  number       = {{4}},
  pages        = {{583--612}},
  publisher    = {{Springer Nature}},
  title        = {{{On the institutional design of burden sharing when financing external border enforcement in the EU}}},
  doi          = {{10.1007/s10368-012-0226-3}},
  volume       = {{10}},
  year         = {{2012}},
}

@article{570,
  abstract     = {{This article studies the construction of self-stabilizing topologies for distributed systems. While recent research has focused on chain topologies where nodes need to be linearized with respect to their identiers, we explore a natural and relevant 2-dimensional generalization. In particular, we present a local self-stabilizing algorithm DStab which is based on the concept of \local Delaunay graphs" and which forwards temporary edges in greedy fashion reminiscent of compass routing. DStab constructs a Delaunay graph from any initial connected topology and in a distributed manner in time O(n3) in the worst-case; if the initial network contains the Delaunay graph, the convergence time is only O(n) rounds. DStab also ensures that individual node joins and leaves aect a small part of the network only. Such self-stabilizing Delaunay networks have interesting applications and our construction gives insights into the necessary geometric reasoning that is required for higherdimensional linearization problems.Keywords: Distributed Algorithms, Topology Control, Social Networks}},
  author       = {{Jacob, Riko and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan}},
  journal      = {{Theoretical Computer Science}},
  pages        = {{137--148}},
  publisher    = {{Elsevier}},
  title        = {{{Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs}}},
  doi          = {{10.1016/j.tcs.2012.07.029}},
  year         = {{2012}},
}

@article{574,
  abstract     = {{We present Tiara — a self-stabilizing peer-to-peer network maintenance algorithm. Tiara is truly deterministic which allows it to achieve exact performance bounds. Tiara allows logarithmic searches and topology updates. It is based on a novel sparse 0-1 skip list. We then describe its extension to a ringed structure and to a skip-graph.Key words: Peer-to-peer networks, overlay networks, self-stabilization.}},
  author       = {{Clouser, Thomas and Nesterenko, Mikhail and Scheideler, Christian}},
  journal      = {{Theoretical Computer Science}},
  pages        = {{18--35}},
  publisher    = {{Elsevier}},
  title        = {{{Tiara: A self-stabilizing deterministic skip list and skip graph}}},
  doi          = {{10.1016/j.tcs.2011.12.079}},
  year         = {{2012}},
}

@misc{575,
  author       = {{Bremer, Lars}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Symbiotic Coupling of Peer-to-Peer and Cloud Systems}}},
  year         = {{2012}},
}

@techreport{578,
  abstract     = {{This paper analyzes the stability of capital tax harmonization agreements in a stylized model where countries have formed coalitions which set a common tax rate in order to avoid the inefficient fully non-cooperative Nash equilibrium. In particular, for a given coalition structure we study to what extend the stability of tax agreements is affected by the coalitions that have formed. In our set-up, countries are symmetric, but coalitions can be of arbitrary size. We analyze stability by means of a repeated game setting employing simple trigger strategies and we allow a sub-coalition to deviate from the coalitional equilibrium. For a given form of punishment we are able to rank the stability of different coalition structures as long as the size of the largest coalition does not change. Our main results are: (1) singleton regions have the largest incentives to deviate, (2) the stability of cooperation depends on the degree of cooperative behavior ex-ante.}},
  author       = {{Brangewitz, Sonja and Brockhoff, Sarah}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Stability of Coalitional Equilibria within Repeated Tax Competition}}},
  year         = {{2012}},
}

@article{579,
  abstract     = {{A left-to-right maximum in a sequence of n numbers s_1, …, s_n is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of n numbers s_i ∈ [0,1] that are perturbed by uniform noise from the interval [-ε,ε], the expected number of left-to-right maxima is Θ(&sqrt;n/ε + log n) for ε>1/n. For Gaussian noise with standard deviation σ we obtain a bound of O((log3/2 n)/σ + log n).We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of Θ(&sqrt;n/ε + log n) and Θ(n/ε+1&sqrt;n/ε + n log n), respectively, for uniform random noise from the interval [-ε,ε]. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to smoothed motion complexity, a concept we describe in this article. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in d-dimensional space.}},
  author       = {{Damerow, Valentina and Manthey, Bodo and Meyer auf der Heide, Friedhelm and Räcke, Harald and Scheideler, Christian and Sohler, Christian and Tantau, Till}},
  journal      = {{Transactions on Algorithms}},
  number       = {{3}},
  pages        = {{30}},
  publisher    = {{ACM}},
  title        = {{{Smoothed analysis of left-to-right maxima with applications}}},
  doi          = {{10.1145/2229163.2229174}},
  year         = {{2012}},
}

@misc{582,
  author       = {{Strothmann, Thim Frederik}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Self-Optimizing Binary Search Trees - A Game Theoretic Approach}}},
  year         = {{2012}},
}

@misc{583,
  author       = {{Drücker, Julian}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Revenue-maximizing Order of Sale in Sequential Auctions}}},
  year         = {{2012}},
}

@misc{584,
  author       = {{Hohenberger, Till}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Queuing Latency at Cooperative Base Stations}}},
  year         = {{2012}},
}

@misc{592,
  author       = {{Celik, Aydin}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Penny Auctions: Design und Strategisches Verhalten}}},
  year         = {{2012}},
}

@misc{593,
  author       = {{Rojahn, Tobias}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Optimale Zuteilung von Nutzern zu verteilten Cloud-Standorten}}},
  year         = {{2012}},
}

@misc{594,
  author       = {{Klerx, Timo}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen}}},
  year         = {{2012}},
}

@inproceedings{597,
  abstract     = {{We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist [15, 16], a mixed equilibrium for such games, called a V -equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question for a particular concave valuation: expectation plus variance, denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria:- A collection of general structural properties of RA-equilibria connecting to (i) E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable equilibrium properties.- A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. Using examples, we provide the first demonstration that going from E to RA may as well create new mixed (RA-)equilibria.- A purification technique to transform a player-specific scheduling game on identical links into a player-specific scheduling game so that all non-pure RA-equilibria are eliminated while new pure equilibria cannot be created; so, a particular game on two identical links yields one with no RA-equilibrium. As a by-product, the first-completeness result for the computation of RA-equilibria follows.}},
  author       = {{Mavronicolas, Marios and Monien, Burkhard}},
  booktitle    = {{Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)}},
  pages        = {{239--250}},
  title        = {{{Minimizing Expectation Plus Variance}}},
  doi          = {{10.1007/978-3-642-33996-7_21}},
  year         = {{2012}},
}

@misc{598,
  author       = {{Mammadov, Fuad}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Methoden zur Bestimmung von innerbetrieblichen Verrechnungspreisen}}},
  year         = {{2012}},
}

@misc{599,
  author       = {{Löwen, Xenia}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Managerial Delegation and Capacity Choices: An Analysis of the Cournot-Nash Equilibrium}}},
  year         = {{2012}},
}

@misc{600,
  author       = {{Feldkord, Björn}},
  publisher    = {{Universität Paderborn}},
  title        = {{{Lokale Swaps und überholte Informationen in Basic Network Creation Games}}},
  year         = {{2012}},
}

@phdthesis{601,
  abstract     = {{Wir betrachten eine Gruppe von mobilen, autonomen Robotern in einem ebenen Gel{\"a}nde. Es gibt keine zentrale Steuerung und die Roboter m{\"u}ssen sich selbst koordinieren. Zentrale Herausforderung dabei ist, dass jeder Roboter nur seine unmittelbare Nachbarschaft sieht und auch nur mit Robotern in seiner unmittelbaren Nachbarschaft kommunizieren kann. Daraus ergeben sich viele algorithmische Fragestellungen. In dieser Arbeit wird untersucht, unter welchen Voraussetzungen die Roboter sich auf einem Punkt versammeln bzw. eine Linie zwischen zwei festen Stationen bilden k{\"o}nnen. Daf{\"u}r werden mehrere Roboter-Strategien in verschiedenen Bewegungsmodellen vorgestellt. Diese Strategien werden auf ihre Effizienz hin untersucht. Es werden obere und untere Schranken f{\"u}r die ben{\"o}tigte Anzahl Runden und die Bewegungsdistanz gezeigt. In einigen F{\"a}llen wird außerdem die ben{\"o}tigte Bewegungsdistanz mit derjenigen Bewegungsdistanz verglichen, die eine optimale globale Strategie auf der gleichen Instanz ben{\"o}tigen w{\"u}rde. So werden kompetititve Faktoren hergeleitet.}},
  author       = {{Kempkes, Barbara}},
  isbn         = {{978-3-942647-21-2}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Local strategies for robot formation problems}}},
  volume       = {{302}},
  year         = {{2012}},
}