@inproceedings{18656,
  abstract     = {{In the StrSort model [2], the input is given as a stream, e.g. a sequence of points, and an algorithm can perform (a) streaming and (b) sorting passes to process the stream. A streaming pass reads the input stream from left to right and writes an output stream, which is the input of the next pass. A sorting pass is a black box operation that sorts a stream according to some partial order. In this paper, we develop algorithms for two basic geometric problems in the StrSort model. At first, we propose a divide-and-conquer algorithm that computes the convex hull of a point set in 2D in O(log2 n) passes using O(1) memory. Then we give a StrSort algorithm to compute a (1+ε)-spanner for a point set in Rd for constant d and constant epsilon that uses O(logd-1 n) passes and O(log n) space. This result implies a (1+ε)-approximation of the Euclidean minimum spanning tree in Rd, for constant d and ε.}},
  author       = {{Sohler, Christian and Lammersen, Christiane}},
  booktitle    = {{Proceedings of the 23rd European Workshop on Computational Geometry (EWCG)}},
  pages        = {{69--72}},
  title        = {{{StrSort Algorithms for Geometric Problems}}},
  year         = {{2007}},
}

@inproceedings{18660,
  author       = {{Sohler, Christian  and Czumaj, Artur}},
  booktitle    = {{Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS)}},
  pages        = {{570 -- 578}},
  title        = {{{Testing Expansion in Bounded-Degree Graphs}}},
  year         = {{2007}},
}

@inproceedings{18662,
  author       = {{Sohler, Christian and Czumaj, Artur}},
  booktitle    = {{Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS'07)}},
  pages        = {{536--548}},
  title        = {{{Small Space Representations for Metric Min-Sum k-Clustering and their Applications}}},
  year         = {{2007}},
}

@article{18665,
  abstract     = {{We present a novel analysis of a random sampling approach for four clustering problems in metric spaces: k-median, k-means, min-sum k-clustering, and balanced k-median. For all these problems, we consider the following simple sampling scheme: select a small sample set of input points uniformly at random and then run some approximation algorithm on this sample set to compute an approximation of the best possible clustering of this set. Our main technical contribution is a significantly strengthened analysis of the approximation guarantee by this scheme for the clustering problems.The main motivation behind our analyses was to design sublinear-time algorithms for clustering problems. Our second contribution is the development of new approximation algorithms for the aforementioned clustering problems. Using our random sampling approach, we obtain for these problems the first time approximation algorithms that have running time independent of the input size, and depending on k and the diameter of the metric space only. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007A preliminary extended abstract of this work appeared in Proceedings of the 31st Annual International Colloquium on Automata, Languages and Programming (ICALP), pp. 396407, 2004.}},
  author       = {{Sohler, Christian and Czumaj, Artur}},
  journal      = {{Random Structures & Algorithms}},
  number       = {{1-2}},
  pages        = {{226 ---- 256}},
  title        = {{{Sublinear-time approximation algorithms for clustering via random sampling}}},
  volume       = {{30}},
  year         = {{2007}},
}

@inproceedings{18668,
  author       = {{Sohler, Christian and Monemizahdeh, Morteza and Feldman, Dan}},
  booktitle    = {{Proceedings of the 23rd annual symposium on computational geometry (SoCG'07)}},
  pages        = {{11--18}},
  title        = {{{A PTAS for k-means clustering based on weak coresets}}},
  year         = {{2007}},
}

@inproceedings{18669,
  author       = {{Sohler, Christian and Czumaj, Artur and Frahling, Gereon}},
  booktitle    = {{Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG)}},
  pages        = {{157--160}},
  title        = {{{Efficient kinetic data structures for MaxCut}}},
  year         = {{2007}},
}

@inproceedings{2214,
  abstract     = {{We present a randomized block-level storage virtualization for arbitrary heterogeneous storage systems that can distribute data in a fair and redundant way and can adapt this distribution in an efficient way as storage devices enter or leave the system. More precisely, our virtualization strategies can distribute a set of data blocks among a set of storage devices of arbitrary non-uniform capacities so that a storage device representing x% of the capacity in the system will get x% of the data (as long as this is in principle possible) and the different copies of each data block are stored so that no two copies of a data block are located in the same device. Achieving these two properties is not easy, and no virtualization strategy has been presented so far that has been formally shown to satisfy fairness and redundancy while being time- and space-eflcient and allowing an efficient adaptation to a changing set of devices.}},
  author       = {{Brinkmann, André and Effert, Sascha and Meyer auf der Heide, Friedhelm and Scheideler, Christian}},
  booktitle    = {{IEEE International Conference on Distributed Computing Systems (ICDCS)}},
  title        = {{{Dynamic and redundant data placement}}},
  year         = {{2007}},
}

@inproceedings{7970,
  abstract     = {{We consider the problem of exploring an unknown environment using a swarm of autonomous robots with collective behavior emerging from their local rules. Each robot has only a very restricted view on the environment which makes cooperation difficult. We introduce a software system which is capable of simulating a large number of such robots (e.g. 1000) on highly complex terrains with millions of obstacles. Its main purpose is to easily integrate and evaluate any kind of algorithm for controlling the robot behavior. The simulation may be observed in real-time via a visualization that displays both the individual and the collective progress of the robots. We present the system design, its main features and underlying concepts.}},
  author       = {{Arens, Stephan and Buss, Alexander and Deck, Helena and Dynia, Miroslaw and Fischer, Matthias and Hagedorn, Holger and Isaak, Peter and Kutylowski, Jaroslaw and Meyer auf der Heide, Friedhelm and Nesterow, Viktor and Ogiermann, Adrian and Stobbe, Boris and Storm, Thomas and Wachsmuth, Henning}},
  booktitle    = {{Proceedings of the 4th International Symposium on Autonomous Minirobots for Research and Edutainment}},
  pages        = {{215--222}},
  publisher    = {{Heinz Nixdorf Institut, University of Paderborn}},
  title        = {{{Smart Teams: Simulating Large Robotic Swarms in Vast Environments}}},
  year         = {{2007}},
}

@inproceedings{16467,
  author       = {{Dynia, Miroslaw and Kutylowski, Jaroslaw and Meyer auf der Heide, Friedhelm and Schrieb, Jonas}},
  booktitle    = {{Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures  - SPAA '07}},
  isbn         = {{9781595936677}},
  title        = {{{Local strategies for maintaining a chain of relay stations between an explorer and a base station}}},
  doi          = {{10.1145/1248377.1248420}},
  year         = {{2007}},
}

@phdthesis{19612,
  author       = {{Klein, Jan}},
  isbn         = {{3-939350-05-2}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Efficient Collision Detection for Point and Polygon Based Models}}},
  volume       = {{186}},
  year         = {{2006}},
}

@phdthesis{19613,
  author       = {{Rührup, Stefan}},
  isbn         = {{978-3-939350-22-4}},
  publisher    = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}},
  title        = {{{Position-based Routing Strategies}}},
  volume       = {{203}},
  year         = {{2006}},
}

@inproceedings{19690,
  author       = {{Briest, Patrick and Krysta, Piotr}},
  booktitle    = {{Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA)}},
  title        = {{{Single-Minded Unlimited Supply Pricing on Sparse Instances}}},
  year         = {{2006}},
}

@inproceedings{19691,
  author       = {{Briest, Patrick and Gunia, Christian}},
  booktitle    = {{Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC)}},
  title        = {{{Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels}}},
  year         = {{2006}},
}

@misc{19718,
  author       = {{Degener, Bastian}},
  title        = {{{Die Analyse von Estimation-of-Distribution-Algorithmen auf ausgewählten Funktionen}}},
  year         = {{2006}},
}

@inproceedings{19808,
  abstract     = {{We study the problem of designing an adaptive hash table for redundant data storage in a system of storage devices with arbitrary capacities. Ideally, such a hash table should make sure that (a) a storage device with x% of the available capacity should get x% of the data, (b) the copies of each data item are distributed among the storage devices so that no two copies are stored at the same device, and (c) only a near-minimum amount of data replacements is necessary to preserve (a) and (b) under any change in the system. Hash tables satisfying (a) and (c) are already known, and it is not difficult to construct hash tables satisfying (a) and (b). However, no hash table is known so far that can satisfy all three properties as long as this is in principle possible. We present a strategy called SPREAD that solves this problem for the first time. As long as (a) and (b) can in principle be satisfied, SPREAD preserves (a) for every storage device nearly optimal, with high probability, guarantees (b) for every data item, and only needs a constant factor more data replacements than minimum possible in order to preserve (a) and (b).}},
  author       = {{Mahlmann, Peter and Schindelhauer, Christian}},
  booktitle    = {{Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures  - SPAA '06}},
  isbn         = {{1595934529}},
  pages        = {{308----317}},
  title        = {{{Distributed random digraph transformations for peer-to-peer networks}}},
  doi          = {{10.1145/1148109.1148162}},
  year         = {{2006}},
}

@inproceedings{19838,
  author       = {{Rührup, Stefan and Schindelhauer, Christian}},
  booktitle    = {{Proc. of the 17th International Symposium on Algorithms and Computation (ISAAC 2006)}},
  isbn         = {{9783540496946}},
  issn         = {{0302-9743}},
  title        = {{{Online Multi-path Routing in a Maze}}},
  doi          = {{10.1007/11940128_65}},
  year         = {{2006}},
}

@inproceedings{19839,
  abstract     = {{Storage Area Networks commonly consist a more or less static set of n data servers that handle a dynamic collection of m documents. Such SANs can minimize the access time to documents by distributing each document among several servers, allowing users to access documents in parallel. This paper describes an efficient solution for providing parallel access to multiple hard disks for popular content. In extension to previous approaches we provide an efficient and elegant hash table data structure for utilizing the full capacity of each data server. Concerning the dynamics, documents as well as server may be added or removed from the system causing only local changes. We consider sequential and parallel access to data in the average case. For the average time model we present a fast optimal algorithm.}},
  author       = {{Schindelhauer, Christian and Schomaker, Gunnar}},
  booktitle    = {{5th International Conference on Networking (ICN)}},
  isbn         = {{0769525520}},
  title        = {{{SAN Optimal Multi Parameter Access Scheme}}},
  doi          = {{10.1109/icniconsmcl.2006.190}},
  year         = {{2006}},
}

@techreport{19840,
  author       = {{Rührup, Stefan and Schindelhauer, Christian}},
  title        = {{{Improved Bounds for Online Multi-Path Routing in Faulty Mesh Networks}}},
  year         = {{2006}},
}

@inproceedings{19854,
  abstract     = {{In previous publications there have been several proposals<br>regarding replica generation and placement of movie content in<br>content-distribution-networks or P2P overlays. Within this paper<br>we extend approaches for heterogeneous placement scenarios<br>described in prior publications. Therefor we presume heterogeneous<br>server peers' bandwidth, HD capacity, and movie popularities.<br>Movie documents are replicated and placed onto server peers with<br>respect to the predicted popularity values. Thus each document<br>aims to gain fair networks resources according to its popularity.<br>We present simulation results of heuristics of different placement<br>strategies and compare them with a near optimal technique.}},
  author       = {{Schomaker, Gunnar and Loeser, Christoph and Schubert, Matthias}},
  booktitle    = {{5th International Conference on Networking (ICN).}},
  title        = {{{Predictive Replication and Placement Strategies for Movie Documents in heterogeneous Content Delivery Networks}}},
  year         = {{2006}},
}

@inproceedings{19870,
  author       = {{Brinkmann, Andre and Effert, Sascha and Heidebuer, Michael and Vodisek, Mario}},
  booktitle    = {{5th International Conference on Networking (ICN)}},
  isbn         = {{0769525520}},
  title        = {{{Realizing Multilevel Snapshots in Dynamically Changing Virtualized Storage Environments}}},
  doi          = {{10.1109/icniconsmcl.2006.182}},
  year         = {{2006}},
}