@article{17980, author = {{Ziegler, Martin}}, issn = {{1571-0661}}, journal = {{Electronic Notes in Theoretical Computer Science}}, pages = {{255--274}}, title = {{{Revising Type-2 Computation and Degrees of Discontinuity}}}, doi = {{10.1016/j.entcs.2006.08.015}}, year = {{2007}}, } @article{17981, author = {{Ziegler, Martin}}, issn = {{1432-4350}}, journal = {{Theory of Computing Systems}}, pages = {{177--206}}, title = {{{Real Hypercomputation and Continuity}}}, doi = {{10.1007/s00224-006-1343-6}}, year = {{2007}}, } @inbook{17982, author = {{Ziegler, Martin}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540730002}}, issn = {{0302-9743}}, title = {{{(Short) Survey of Real Hypercomputation}}}, doi = {{10.1007/978-3-540-73001-9_86}}, year = {{2007}}, } @inbook{17983, author = {{Meer, Klaus and Ziegler, Martin}}, booktitle = {{Mathematical Foundations of Computer Science 2007}}, isbn = {{9783540744559}}, issn = {{0302-9743}}, title = {{{Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation}}}, doi = {{10.1007/978-3-540-74456-6_64}}, year = {{2007}}, } @unpublished{17984, abstract = {{The unit cost model is both convenient and largely realistic for describing integer decision algorithms over (+,*). Additional operations like division with remainder or bitwise conjunction, although equally supported by computing hardware, may lead to a considerable drop in complexity. We show a variety of concrete problems to benefit from such NON-arithmetic primitives by presenting and analyzing corresponding fast algorithms.}}, author = {{Lürwer-Brüggemeier, Katharina and Ziegler, Martin}}, booktitle = {{arXiv:0709.0624}}, title = {{{On Faster Integer Calculations using Non-Arithmetic Primitives}}}, year = {{2007}}, } @techreport{18285, author = {{Ziegler, Martin}}, title = {{{Real Computability and Hypercomputation}}}, year = {{2007}}, } @inproceedings{18347, abstract = {{The validation of material flow models as well as the selection of promising strategies for the generation of a successful experiment plan is a time-consuming process. A new approach is presented, which supports the simulation expert in his working process by giving him the opportunity to modify the simulated simulation run and afterwards compare the effects of his modification with the original setting, online and in one user interface, implemented by switching the visualizations between the simulation runs or opening up to 5 parallel 3D windows. The method developed therefore clones existing simulation runs online and allows the navigation within these existing simulation runs. The method has been implemented and is validated by a test model, which describes in detail the new working process of a modeler. New research questions are derived from this work, which will define following working steps. }}, author = {{Fischer, Matthias and Laroque, Christoph and Huber, Daniel and Krokowski, Jens and Mueck, Bengt and Kortenjan, Michael and Aufenanger, Mark and Dangelmaier, Wilhelm}}, booktitle = {{European Simulation and Modelling Conference (ESM 2007)}}, pages = {{499----505}}, title = {{{Interactive Refinement of a Material Flow Simulation Model by Comparing Multiple Simulation Runs in one 3D Environment}}}, year = {{2007}}, } @inproceedings{18349, author = {{Dangelmaier, Wilhelm and Laroque, Christoph and Fischer, Matthias}}, booktitle = {{Augmented & Virtual Reality in der Produktentstehung}}, pages = {{95--110}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Ein ganzheitlicher Ansatz zur immersiven 3D-Materialflusssimulation innerhalb der Digitalen Fabrik}}}, volume = {{209}}, year = {{2007}}, } @inproceedings{18572, abstract = {{We present random sampling algorithms that with probability at least 1 − δ compute a (1 ±ε)-approximation of the clustering coefficient and of the number of bipartite clique subgraphs of a graph given as an incidence stream of edges. The space used by our algorithm to estimate the clustering coefficient is inversely related to the clustering coefficient of the network itself. The space used by our algorithm to compute the number K 3,3 of bipartite cliques is proportional to the ratio between the number of K 1,3 and K 3,3 in the graph. Since the space complexity depends only on the structure of the input graph and not on the number of nodes, our algorithms scale very well with increasing graph size. Therefore they provide a basic tool to analyze the structure of dense clusters in large graphs and have many applications in the discovery of web communities, the analysis of the structure of large social networks and the probing of frequent patterns in large graphs. We implemented both algorithms and evaluated their performance on networks from different application domains and of different size; The largest instance is a webgraph consisting of more than 135 million nodes and 1 billion edges. Both algorithms compute accurate results in reasonable time on the tested instances.}}, author = {{Buriol, Luciana S. and Frahling, Gereon and Leonardi, Stefano and Sohler, Christian}}, booktitle = {{Proceedings of the 15th European Symposium on Algorithms (ESA)}}, isbn = {{9783540755197}}, pages = {{618--632}}, publisher = {{Springer}}, title = {{{Estimating Clustering Indexes in Data Streams}}}, doi = {{10.1007/978-3-540-75520-3_55}}, volume = {{4698}}, year = {{2007}}, } @inproceedings{18655, abstract = {{We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is believed that almost all, even very simple graph properties require a large complexity to be tested for arbitrary (bounded degree) graphs. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. We call a graph family non-expanding if every graph in this family is not a weak expander (its expansion is O(1/log2 n), where n is the graph size). A graph family is hereditary if it is closed under vertex removal. Similarly, a graph property is hereditary if it is closed under vertex removal. Next, we call a graph property Π to be testable for a graph family F if for every graph G ε F, in time independent of the size of G we can distinguish between the case when G satisfies property Π and when it is far from every graph satisfying property Π. In this paper we prove thatIn the bounded degree graph model, any hereditary property is testable if the input graph belongs to a hereditary and non-expanding family of graphs.As an application, our result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before and prior to our work, in the bounded degree graph model very few graph properties have been known to be testable for any graph classes.}}, author = {{Sohler, Christian and Czumaj, Artur}}, booktitle = {{Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'07)}}, isbn = {{9780898716245}}, pages = {{494--501}}, title = {{{On Testable Properties in Bounded Degree Graphs}}}, year = {{2007}}, } @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}}, }