18 Search Results for "Meyer auf der Heide, Friedhelm"

Document
DOI: 10.4230/LIPIcs.OPODIS.2022.15
A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility

Authors: Jannik Castenow, Jonas Harbig, Daniel Jung, Peter Kling, Till Knollmann, and Friedhelm Meyer auf der Heide

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
We consider a swarm of n robots in a d-dimensional Euclidean space. The robots are oblivious (no persistent memory), disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task Gathering requires that all robots reach the same, not predefined position. In the related NearGathering task, they must reach distinct positions in close proximity such that every robot sees the entire swarm. In the considered setting, Gathering can be solved in 𝒪(n + Δ²) synchronous rounds both in two and three dimensions, where Δ denotes the initial maximal distance of two robots [Hideki Ando et al., 1999; Michael Braun et al., 2020; Bastian Degener et al., 2011]. In this work, we formalize a key property of efficient Gathering protocols and use it to define λ-contracting protocols. Any such protocol gathers n robots in the d-dimensional space in 𝒪(Δ²) synchronous rounds, for d ≥ 2. For d = 1, any λ-contracting protocol gathers in optimal time 𝒪(Δ). Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside the local convex hulls of their neighborhoods - λ-contracting protocols have this property - requires Ω(Δ²) rounds to gather all robots (d > 1). Among others, we prove that the d-dimensional generalization of the GTC-protocol [Hideki Ando et al., 1999] is λ-contracting. Remarkably, our improved and generalized runtime bound is independent of n and d. We also introduce an approach to make any λ-contracting protocol collision-free (robots never occupy the same position) to solve NearGathering. The resulting protocols maintain the runtime of Θ (Δ²) and work even in the semi-synchronous model. This yields the first NearGathering protocols for disoriented robots and the first proven runtime bound. In particular, combined with results from [Paola Flocchini et al., 2017] for robots with global visibility, we obtain the first protocol to solve Uniform Circle Formation (arrange the robots on the vertices of a regular n-gon) for oblivious, disoriented robots with limited visibility.
Cite as

Jannik Castenow, Jonas Harbig, Daniel Jung, Peter Kling, Till Knollmann, and Friedhelm Meyer auf der Heide. A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 15:1-15:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{castenow_et_al:LIPIcs.OPODIS.2022.15,
  author =	{Castenow, Jannik and Harbig, Jonas and Jung, Daniel and Kling, Peter and Knollmann, Till and Meyer auf der Heide, Friedhelm},
  title =	{{A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{15:1--15:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.15},
  URN =		{urn:nbn:de:0030-drops-176350},
  doi =		{10.4230/LIPIcs.OPODIS.2022.15},
  annote =	{Keywords: mobile robots, gathering, limited visibility, runtime, collision avoidance, near-gathering}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.22
Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets

Authors: Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
The modern warehouse is partially automated by robots. Instead of letting human workers walk into shelfs and pick up the required stock, big groups of autonomous mobile robots transport the inventory to the workers. Typically, these robots have an electric drive and need to recharge frequently during the day. When we scale this approach up, it is essential to place recharging stations strategically and as soon as needed so that all robots can survive. In this work, we represent a warehouse topology by a graph and address this challenge with the Online Connected Dominating Set problem (OCDS), an online variant of the classical Connected Dominating Set problem [Guha and Khuller, 1998]. We are given an undirected connected graph G = (V, E) and a sequence of subsets of V arriving over time. The goal is to grow a connected subgraph that dominates all arriving nodes and contains as few nodes as possible. We propose an O(log^2 n)-competitive randomized algorithm for OCDS in general graphs, where n is the number of nodes in the input graph. This is the best one can achieve due to Korman's randomized lower bound of Omega(log n log m) [Korman, 2005] for the related Online Set Cover problem [Alon et al., 2003], where n is the number of elements and m is the number of subsets. We also run extensive simulations to show that our algorithm performs well in a simulated warehouse, where the topology of a warehouse is modeled as a randomly generated geometric graph.
Cite as

Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby. Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hamann_et_al:LIPIcs.FUN.2018.22,
  author =	{Hamann, Heiko and Markarian, Christine and Meyer auf der Heide, Friedhelm and Wahby, Mostafa},
  title =	{{Pick, Pack, \& Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.22},
  URN =		{urn:nbn:de:0030-drops-88136},
  doi =		{10.4230/LIPIcs.FUN.2018.22},
  annote =	{Keywords: connected dominating set, online algorithm, competitive analysis, geometric graph, robot warehouse, recharging stations}
}
Document
DOI: 10.4230/DagSemProc.05361.1
05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks

Authors: Stefano Leonardi, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
From 04.09.05 to 09.09.05, the Dagstuhl Seminar 05361 ``Algorithmic Aspects of Large and Complex Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Stefano Leonardi, Friedhelm Meyer auf der Heide, and Dorothea Wagner. 05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{leonardi_et_al:DagSemProc.05361.1,
  author =	{Leonardi, Stefano and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.1},
  URN =		{urn:nbn:de:0030-drops-5702},
  doi =		{10.4230/DagSemProc.05361.1},
  annote =	{Keywords: Algorithms, Large and Complex Networks}
}
Document
DOI: 10.4230/DagSemProc.05361.2
A Cost Mechanism for Fair Pricing of Resource Usage

Authors: Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of $m$ resources by $n$ selfish agents. Each agent has an individual demand; demands are drawn according to some probability distribution. The cost paid by an agent for a resource she chooses is the total demand put on the resource divided by the number of agents who chose that same resource. So, resources charge costs in an equitable, fair way, while each resource makes no profit out of the agents. We call our model the Fair Pricing model. Its fair cost mechanism induces a non-cooperative game among the agents. To evaluate the Nash equilibria of this game, we introduce the Diffuse Price of Anarchy, as an extension of the Price of Anarchy that takes into account the probability distribution on the demands. We prove: (1) Pure Nash equilibria may not exist, unless all chosen demands are identical; in contrast, a fully mixed Nash equilibrium exists for all possible choices of the demands. Further on, the fully mixed Nash equilibrium is the unique Nash equilibrium in case there are only two agents. (2) In the worst-case choice of demands, the Price of Anarchy is $Theta (n)$; for the special case of two agents, the Price of Anarchy is less than $2 - frac{1}{m}$. (3) Assume now that demands are drawn from a bounded, independent probability distribution, where all demands are identically distributed and each is at most a (universal for the class) constant times its expectation. Then, the Diffuse Price of Anarchy is at most that same constant, which is just $2$ when each demand is distributed symmetrically around its expectation.
Cite as

Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis. A Cost Mechanism for Fair Pricing of Resource Usage. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{mavronicolas_et_al:DagSemProc.05361.2,
  author =	{Mavronicolas, Marios and Panagopoulou, Panagiota and Spirakis, Paul G.},
  title =	{{A Cost Mechanism for Fair Pricing of Resource Usage}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.2},
  URN =		{urn:nbn:de:0030-drops-5646},
  doi =		{10.4230/DagSemProc.05361.2},
  annote =	{Keywords: Cost Sharing, Diffuse Price of Anarchy, Fair Pricing, Resources}
}
Document
DOI: 10.4230/DagSemProc.05361.3
A Hybrid Model for Drawing Dynamic and Evolving Graphs

Authors: Marco Gaertler and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
Dynamic processes frequently occur in many applications. Visualizations of dynamically evolving data, for example as part of the data analysis, are typically restricted to a cumulative static view or an animation/sequential view. Both methods have their benefits and are often complementary in their use. We present a hybrid model that combines the two techniques. This is accomplished by 2.5D drawings which are calculated in an incremental way. The method has been evaluated on collaboration networks.
Cite as

Marco Gaertler and Dorothea Wagner. A Hybrid Model for Drawing Dynamic and Evolving Graphs. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gaertler_et_al:DagSemProc.05361.3,
  author =	{Gaertler, Marco and Wagner, Dorothea},
  title =	{{A Hybrid Model for Drawing Dynamic and Evolving Graphs}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.3},
  URN =		{urn:nbn:de:0030-drops-5683},
  doi =		{10.4230/DagSemProc.05361.3},
  annote =	{Keywords: Visualization dynamic/evolving graphs 2.5D}
}
Document
DOI: 10.4230/DagSemProc.05361.4
Computing earliest arrival flows with multiple sources

Authors: Nadine Baumann and Martin Skutella

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
Earliest arrival flows are motivated by applications related to evacuation. Given a network with capacities and transit times on the arcs, a subset of source nodes with supplies and a sink node, the task is to send the given supplies from the sources to the sink "as quickly as possible". The latter requirement is made more precise by the earliest arrival property which requires that the total amount of flow that has arrived at the sink is maximal for all points in time simultaneously. It is a classical result from the 1970s that, for the special case of a single source node, earliest arrival flows do exist and can be computed by essentially applying the Successive Shortest Path Algorithm for min-cost flow computations. While it has previously been observed that an earliest arrival flow still exists for multiple sources, the problem of computing one efficiently has been open. We present an exact algorithm for this problem whose running time is strongly polynomial in the input plus output size of the problem.
Cite as

Nadine Baumann and Martin Skutella. Computing earliest arrival flows with multiple sources. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{baumann_et_al:DagSemProc.05361.4,
  author =	{Baumann, Nadine and Skutella, Martin},
  title =	{{Computing earliest arrival flows with multiple sources}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.4},
  URN =		{urn:nbn:de:0030-drops-5672},
  doi =		{10.4230/DagSemProc.05361.4},
  annote =	{Keywords: Networks, flows over time, dynamic flows, earliest arrival, evacuation}
}
Document
DOI: 10.4230/DagSemProc.05361.5
Cost Sharing Mechanisms for Fair Pricing of Resources Usage

Authors: Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of $m$ resources by $n$ selfish agents. Each agent has an individual demand; demands are drawn according to some probability distribution. The cost paid by an agent for a resource she chooses is the total demand put on the resource divided by the number of agents who chose that same resource. So, resources charge costs in an equitable, fair way, while each resource makes no profit out of the agents. We call our model the Fair Pricing model. Its fair cost mechanism induces a non-cooperative game among the agents. To evaluate the Nash equilibria of this game, we introduce the Diffuse Price of Anarchy, as an extension of the Price of Anarchy that takes into account the probability distribution on the demands. We prove: (1) Pure Nash equilibria may not exist, unless all chosen demands are identical. In contrast, we have been able to prove that pure Nash equilibria do exist for two closely related cost sharing models, namely the Average Cost Pricing and the Serial Cost Sharing models. (2) A fully mixed Nash equilibrium exists for all possible choices of the demands. Further on, the fully mixed Nash equilibrium is the unique Nash equilibrium in case there are only two agents. (3) In the worst-case choice of demands, the Price of Anarchy is $Theta (n)$; for the special case of two agents, the Price of Anarchy is less than $2 - frac{1}{m}$. (4) Assume now that demands are drawn from a bounded, independent probability distribution, where all demands are identically distributed and each is at most a (universal for the class) constant times its expectation. Then, the Diffuse Price of Anarchy is at most that same constant, which is just 2 when each demand is distributed symmetrically around its expectation.
Cite as

Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis. Cost Sharing Mechanisms for Fair Pricing of Resources Usage. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{mavronicolas_et_al:DagSemProc.05361.5,
  author =	{Mavronicolas, Marios and Panagopoulou, Panagiota and Spirakis, Paul G.},
  title =	{{Cost Sharing Mechanisms for Fair Pricing of Resources Usage}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.5},
  URN =		{urn:nbn:de:0030-drops-5665},
  doi =		{10.4230/DagSemProc.05361.5},
  annote =	{Keywords: Cost Sharing, Diffuse Price of Anarchy, Fair Pricing, Resources}
}
Document
DOI: 10.4230/DagSemProc.05361.6
Deterministic boundary recongnition and topology extraction for large sensor networks

Authors: Sándor Fekete, Alexander Kröller, Dennis Pfisterer, and Stefan Fischer

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
We present a new framework for the crucial challenge of self-organization of a large sensor network. The basic scenario can be described as follows: Given a large swarm of immobile sensor nodes that have been scattered in a polygonal region, such as a street network. Nodes have no knowledge of size or shape of the environment or the position of other nodes. Moreover, they have no way of measuring coordinates, geometric distances to other nodes, or their direction. Their only way of interacting with other nodes is to send or to receive messages from any node that is within communication range. The objective is to develop algorithms and protocols that allow self-organization of the swarm into large-scale structures that reflect the structure of the street network, setting the stage for global routing, tracking and guiding algorithms. Our algorithms work in two stages: boundary recognition and topology extraction. All steps are strictly deterministic, yield fast distributed algorithms, and make no assumption on the distribution of nodes in the environment, other than sufficient density.
Cite as

Sándor Fekete, Alexander Kröller, Dennis Pfisterer, and Stefan Fischer. Deterministic boundary recongnition and topology extraction for large sensor networks. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.05361.6,
  author =	{Fekete, S\'{a}ndor and Kr\"{o}ller, Alexander and Pfisterer, Dennis and Fischer, Stefan},
  title =	{{Deterministic boundary recongnition and topology extraction for large sensor networks}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.6},
  URN =		{urn:nbn:de:0030-drops-5632},
  doi =		{10.4230/DagSemProc.05361.6},
  annote =	{Keywords: Distributed algorithms, sensor networks, boundary recognition, topology extraction}
}
Document
DOI: 10.4230/DagSemProc.05361.7
Force-Directed Approaches to Sensor Network Localization

Authors: Stephen G. Kobourov, Alon Efrat, David Forrester, and Anand Iyer

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
In many sensor network applications it is necessary to compute low-error localization of the sensor nodes. Although embedding a GPS unit on each node would solve the problem for many outdoor applications, the cost of this solution for large networks is prohibitively high. We consider static and mobile network localization approaches that make use of the local neighborhood information, in the form of relative distances and angles to nearby nodes, gathered through simpler and less costly devices (RF, ultrasound based range sensors, or antenna arrays). Our algorithms do not make any assumptions about the existence of anchor nodes capable of locating themselves, nor about the knowledge of an initial localization to start with. Instead, we rely on a multi-scale force-directed approach, utilizing range and angle data through dead reckoning. We show that our localization algorithms are robust and scale well with network size.
Cite as

Stephen G. Kobourov, Alon Efrat, David Forrester, and Anand Iyer. Force-Directed Approaches to Sensor Network Localization. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kobourov_et_al:DagSemProc.05361.7,
  author =	{Kobourov, Stephen G. and Efrat, Alon and Forrester, David and Iyer, Anand},
  title =	{{Force-Directed Approaches to Sensor Network Localization}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.7},
  URN =		{urn:nbn:de:0030-drops-5693},
  doi =		{10.4230/DagSemProc.05361.7},
  annote =	{Keywords: Sensor network localization, multi-scale force-directed approach, dead reckoning}
}
Document
DOI: 10.4230/DagSemProc.05361.8
Friends for Free: Self-Organizing Artificial Social Networks for Trust and Cooperation

Authors: David Hales and Stefano Arteconi

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
By harvesting friendship networks from e-mail contacts or instant message "buddy lists" Peer-to-Peer (P2P) applications can improve performance in low trust environments such as the Internet. However, natural social networks are not always suitable, reliable or available. We propose an algorithm (SLACER) that allows peer nodes to create and manage their own friendship networks. We evaluate performance using a canonical test application, requiring cooperation between peers for socially optimal outcomes. The Artificial Social Networks (ASN) produced are connected, cooperative and robust - possessing many of the disable properties of human friendship networks such as trust between friends (directly linked peers) and short paths linking everyone via a chain of friends. In addition to new application possibilities, SLACER could supply ASN to P2P applications that currently depend on human social networks thus transforming them into fully autonomous, self-managing systems.
Cite as

David Hales and Stefano Arteconi. Friends for Free: Self-Organizing Artificial Social Networks for Trust and Cooperation. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{hales_et_al:DagSemProc.05361.8,
  author =	{Hales, David and Arteconi, Stefano},
  title =	{{Friends for Free: Self-Organizing Artificial Social Networks for Trust and Cooperation}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.8},
  URN =		{urn:nbn:de:0030-drops-5659},
  doi =		{10.4230/DagSemProc.05361.8},
  annote =	{Keywords: Evolution of cooperation, Evolving Networks, P2P, Prisoner's Dilemma, Tags}
}
Document
DOI: 10.4230/DagSemRep.391
Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 03361)

Authors: Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner. Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 03361). Dagstuhl Seminar Report 391, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{adler_et_al:DagSemRep.391,
  author =	{Adler, Micah and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 03361)}},
  pages =	{1--5},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{391},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.391},
  URN =		{urn:nbn:de:0030-drops-152711},
  doi =		{10.4230/DagSemRep.391},
}
Document
DOI: 10.4230/DagSemRep.320
Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 01381)

Authors: Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner. Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 01381). Dagstuhl Seminar Report 320, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{adler_et_al:DagSemRep.320,
  author =	{Adler, Micah and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 01381)}},
  pages =	{1--21},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{320},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.320},
  URN =		{urn:nbn:de:0030-drops-152041},
  doi =		{10.4230/DagSemRep.320},
}
Document
DOI: 10.4230/DagSemRep.246
Parallel and Distributed Algorithms (Dagstuhl Seminar 99291)

Authors: Bruce Maggs, Friedhelm Meyer auf der Heide, and Ernst W. Mayr

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Bruce Maggs, Friedhelm Meyer auf der Heide, and Ernst W. Mayr. Parallel and Distributed Algorithms (Dagstuhl Seminar 99291). Dagstuhl Seminar Report 246, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{maggs_et_al:DagSemRep.246,
  author =	{Maggs, Bruce and Meyer auf der Heide, Friedhelm and Mayr, Ernst W.},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 99291)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{246},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.246},
  URN =		{urn:nbn:de:0030-drops-151326},
  doi =		{10.4230/DagSemRep.246},
}
Document
DOI: 10.4230/DagSemRep.188
Parallel and Distributed Algorithms (Dagstuhl Seminar 9737)

Authors: Ernst W. Mayr, Friedhelm Meyer auf der Heide, and Larry Rudolph

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Ernst W. Mayr, Friedhelm Meyer auf der Heide, and Larry Rudolph. Parallel and Distributed Algorithms (Dagstuhl Seminar 9737). Dagstuhl Seminar Report 188, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{mayr_et_al:DagSemRep.188,
  author =	{Mayr, Ernst W. and Meyer auf der Heide, Friedhelm and Rudolph, Larry},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 9737)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{188},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.188},
  URN =		{urn:nbn:de:0030-drops-150752},
  doi =		{10.4230/DagSemRep.188},
}
Document
DOI: 10.4230/DagSemRep.125
Parallel and Distributed Algorithms (Dagstuhl Seminar 9537)

Authors: Cynthia Dwork, Ernst W. Mayr, and Friedhelm Meyer auf der Heide

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Cynthia Dwork, Ernst W. Mayr, and Friedhelm Meyer auf der Heide. Parallel and Distributed Algorithms (Dagstuhl Seminar 9537). Dagstuhl Seminar Report 125, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1995)

Copy BibTex To Clipboard

@TechReport{dwork_et_al:DagSemRep.125,
  author =	{Dwork, Cynthia and Mayr, Ernst W. and Meyer auf der Heide, Friedhelm},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 9537)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{1995},
  type = 	{Dagstuhl Seminar Report},
  number =	{125},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.125},
  URN =		{urn:nbn:de:0030-drops-150135},
  doi =		{10.4230/DagSemRep.125},
}
  • Refine by Author
  • 10 Meyer auf der Heide, Friedhelm
  • 6 Mayr, Ernst W.
  • 4 Wagner, Dorothea
  • 2 Adler, Micah
  • 2 Cole, Richard
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 2 Cost Sharing
  • 2 Diffuse Price of Anarchy
  • 2 Fair Pricing
  • 2 Resources
  • 1 Algorithms
  • Show More...

  • Refine by Type
  • 18 document

  • Refine by Publication Year
  • 8 2006
  • 1 1991
  • 1 1992
  • 1 1993
  • 1 1995
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact