TY - THES
AU - Fischer, Matthias
ID - 17413
SN - 3-935433-73-5
TI - Design, analysis, and evaluation of a data structure for distributed virtual environments
VL - 164
ER -
TY - JOUR
AB - Nowadays companies operate in a difficult environment: the dynamics of innovations increase and product life cycles become shorter. Furthermore products and the corresponding manufacturing processes get more and more complex. Therefore, companies need new methods for the planning of manufacturing systems. One promising approach in this context is digital factory/virtual productionthe modeling and analysis of computer models of the planned factory with the objective to reduce time and costs. For the modeling and analysis various simulation methods and programs have been developed. They are a highly valuable support for planning and visualizing the manufacturing system. But there is one major disadvantage: only experienced and long trained experts are able to operate with these programs. The graphical user interface is very complex and not intuitive to use. This results in an extensive and error-prone modeling of complex simulation models and a time-consuming interpretation of the simulation results.
To overcome these weak points, intuitive and understandable manmachine interfaces like augmented and virtual reality can be used. This paper describes the architecture of a system which uses the technologies of augmented and virtual reality to support the planning process of complex manufacturing systems. The proposed system assists the user in modeling, the validation of the simulation model, and the subsequent optimization of the production system. A general application of the VR- and AR-technologies and of the simulation is realized by the development of appropriate linking and integration mechanisms. For the visualization of the arising 3D-data within the VR- and AR-environments, a dedicated 3D-rendering library is used.
AU - Dangelmaier, Wilhelm
AU - Fischer, Matthias
AU - Gausemeier, Jürgen
AU - Grafe, Michael
AU - Matysczok, Carsten
AU - Mueck, Bengt
ID - 17414
JF - Computers in Industry
SN - 0166-3615
TI - Virtual and augmented reality support for discrete manufacturing system simulation
ER -
TY - CONF
AU - Fischer, Matthias
AU - Mueck, B.
AU - Mahajan, K.
AU - Kortenjan, M.
AU - Laroque, C.
AU - Dangelmaier, W.
ID - 17415
SN - 0780395190
T2 - Proceedings of the Winter Simulation Conference
TI - Multi-User Support and Motion Planning of Humans and Humans Driven Vehicles in Interactive 3D Material Flow Simulations
ER -
TY - JOUR
AB - Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs . We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension , then the property has an efficient tester.
We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size.
Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties.
AU - Czumaj, Artur
AU - Sohler, Christian
ID - 18763
IS - 3
JF - SIAM Journal on Computing
SN - 0097-5397
TI - Abstract Combinatorial Programs and Efficient Property Testers
VL - 34
ER -
TY - CONF
AU - Bădoiu, Mihai
AU - Czumaj, Artur
AU - Indyk, Piotr
AU - Sohler, Christian
ID - 18768
SN - 0302-9743
T2 - Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP)
TI - Facility Location in Sublinear Time
ER -
TY - CONF
AB - A dynamic geometric data stream consists of a sequence of m insert/delete operations of points from the discrete space {1,..., ∆} d [26]. We develop streaming (1 + ɛ)-approximation algorithms for k-median, k-means, MaxCut, maximum weighted matching (MaxWM), maximum travelling salesperson (MaxTSP), maximum spanning tree (MaxST), and average distance over dynamic geometric data streams. Our algorithms maintain a small weighted set of points (a coreset) that approximates with probability 2/3 the current point set with respect to the considered problem during the m insert/delete operations of the data stream. They use poly(ɛ −1, log m, log ∆) space and update time per insert/delete operation for constant k and dimension d. Having a coreset one only needs a fast approximation algorithm for the weighted problem to compute a solution quickly. In fact, even an exponential algorithm is sometimes feasible as its running time may still be polynomial in n. For example one can compute in poly(log n, exp(O((1+log(1/ɛ)/ɛ) d−1))) time a solution to k-median and k-means [21] where n is the size of the current point set and k and d are constants. Finding an implicit solution to MaxCut can be done in poly(log n, exp((1/ɛ) O(1))) time. For MaxST and average distance we require poly(log n, ɛ −1) time and for MaxWM we require O(n 3) time to do this.
AU - Sohler, Christian
AU - Frahling, Gereon
ID - 18787
T2 - Proceedings of the 37th ACM Symposium on Theory of Computing (STOC)
TI - Coresets in Dynamic Geometric Data Streams
ER -
TY - JOUR
AU - Czumaj, Artur
AU - Sohler, Christian
ID - 18790
IS - 1
JF - Theoretical Computer Science
SN - 0304-3975
TI - Testing hypergraph colorability
VL - 331
ER -
TY - JOUR
AB - We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries.
Read More: https://epubs.siam.org/doi/10.1137/S0097539703435297
AU - Czumaj, Artur
AU - Ergün, Funda
AU - Fortnow, Lance
AU - Magen, Avner
AU - Newman, Ilan
AU - Rubinfeld, Ronitt
AU - Sohler, Christian
ID - 18855
IS - 1
JF - SIAM Journal on Computing
SN - 0097-5397
TI - Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
VL - 35
ER -
TY - CONF
AB - Modern computer graphics systems are able to render sophisticated 3D szenes consisting of millions of polygons. In this paper we address the problem of occlusion culling. Aila, Miettinen, and Nordlund suggested to implement a FIFO buffer on graphics cards which is able to delay the polygons before drawing them. When one of the polygons within the buffer is occluded or masked by another polygon arriving later from the application, the rendering engine can drop the occluded one without rendering, saving important rendering time.
We introduce a theoretical online model to analyse these problems in theory using competitive analysis. For different cost measures addressed we invent the first competitive algorithms for online occlusion culling. Our implementation shows that these algorithms outperform known ones for real 3D scenes as well.
AU - Frahling, Gereon
AU - Krokowski, Jens
ID - 18867
SN - 0302-9743
T2 - Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)
TI - Online Occlusion Culling
VL - 3669
ER -
TY - CONF
AB - We consider Dynamic Page Migration (DPM) problem, one of the fundamental subproblems of data management in dynamically changing networks. We investigate a hybrid scenario, where access patterns to the shared object are dictated by an adversary, and each processor performs a random walk in X. We extend the previous results of [4]: we develop algorithms for the case where X is a ring, and prove that with high probability they achieve a competitive ratio of O~(min{D−−√4,n}), where D is the size of the shared object and n is the number of nodes in the network. These results hold also for any d-dimensional torus or mesh with diameter at least Ω~(D−−√).
AU - Bienkowski, Marcin
AU - Korzeniowski, Miroslaw
ID - 18912
SN - 0302-9743
T2 - Proc. of the European Conference in Parallel Processing (Euro-Par)
TI - Dynamic Page Migration Under Brownian Motion
ER -
TY - CONF
AB - We present a simple two-person Bucket Game, based on throwing balls into buckets, and we
discuss possible players' strategies.
We use these strategies to create an approximation algorithm for a generalization of
the well known Set Cover problem, where we need to cover each element by at least $k$ sets.
Furthermore, we apply these strategies to construct a randomized algorithm for Dynamic Page Migration
problem achieving the optimal competitive ratio against an oblivious adversary.
AU - Bienkowski, Marcin
AU - Byrka, Jarosław
ID - 18915
SN - 0302-9743
T2 - Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)
TI - Bucket Game with Applications to Set Multicover and Dynamic Page Migration
VL - 3669
ER -
TY - CONF
AB - The page migration problem is one of subproblems of data management in networks. It occurs
in a distributed network of processors sharing one indivisible memory page of size D. During runtime,
the processors access a unit of data from the page, and the system is allowed to migrate the page
between the processors. The problem is to compute (on-line) a schedule of page movements
to minimize the total communication cost.
The Dynamic Page Migration problem is an extension to the page migration.
It attempts to model the network dynamics, occurring, for example, in mobile networks.
However, the pace of changes is restricted, i.e. the distances between processors can
change only by a constant per round.
The movement of the nodes induce changes in the communication cost between each pair of nodes,
which is proportional to the distance between them raised to some power $alpha$.
This is typical for mobile wireless networks, where nodes can move with a constant speed,
and the cost of communication is measured in terms of energy used for sending the data.
Thus, by setting $alpha$ equal to the propagation exponent of the medium,
cost minimization becomes minimizing the total energy consumption in the system.
However, as proven in citedynamic-page-migration, if both network mobility and
request sequence are created by an adversary, then the competitive ratio is polynomially large in D and
in the number of the nodes. In our search for a reasonable, close-to-reality model, in this paper we
consider a scenario in which the network mobility is adversarial, but the requests are
generated randomly by a stochastic process. We design an algorithm MTFR for this scenario,
and prove that it is O(1)-competitive, on expectation and with high probability.
AU - Bienkowski, Marcin
ID - 18917
T2 - Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005)
TI - Dynamic Page Migration with Stochastic Requests
ER -
TY - CONF
AB - Bluetooth is a wireless communication standard developed for personal area networks (PAN) that gained popularity in the last years. It was designed to connect a few devices together, however nowadays there is a need to build larger networks. Construction and maintenance algorithms have great effect on performance of the network. We present an algorithm based on Cube Connected Cycles (CCC) topology and show how to maintain the network so that it is easily scalable. Our design guarantees good properties such as constant degree and logarithmic dilation. Besides, the construction costs are proven to be at most constant times larger than any other algorithm would need.
AU - Bienkowski, Marcin
AU - Brinkmann, André
AU - Korzeniowski, Miroslaw
AU - Orhan, Orhan
ID - 18924
SN - 0302-9743
T2 - Proceedings of the 4th International Conference on Networking
TI - Cube Connected Cycles Based Bluetooth Scatternet Formation
VL - 3420
ER -
TY - CONF
AB - The dynamic page migration problem citedynamic-page-migration is defined in
a distributed network of $n$ mobile nodes sharing one indivisible memory page
of size $D$. During runtime, the nodes can both access a unit of data from
the page and move with a constant speed, thus changing the costs of communication.
The problem is to compute online a schedule of page movements
to minimize the total communication cost.
In this paper we construct and analyze the first deterministic algorithm for this problem.
We prove that it achieves an (up to a constant factor) optimal competitive ratio
$O(n cdot sqrtD)$. We show that the randomization of this algorithm
improves this ratio to $O(sqrtD cdot log n)$ (against an oblivious adversary).
This substantially improves an $O(n cdot sqrtD)$ upper bound from citedynamic-page-migration.
We also give an almost matching lower bound of $Omega(sqrtD cdot sqrtlog n)$ for this problem.
AU - Bienkowski, Marcin
AU - Dynia, Miroslaw
AU - Korzeniowski, Miroslaw
ID - 18925
SN - 0302-9743
T2 - Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)
TI - Improved Algorithms for Dynamic Page Migration
ER -
TY - THES
AU - Räcke, Harald
ID - 18967
SN - 3-935433-63-8
TI - Data Management and Routing in General Networks
VL - 154
ER -
TY - CONF
AB - A dynamic geometric data stream is a sequence of m Add/Remove operations of points from a discrete geometric space (1,...,Δ)d [21]. Add(p) inserts a point p from (1,...,Δ)d into the current point set, Remove(p) deletes p from P. We develop low-storage data structures to (i) maintain ε-approximations of range spaces of P with constant VC-dimension and (ii) maintain an ε-approximation of the weight of the Euclidean minimum spanning tree of P. Our data structures use O(log3ε • log3(1/ε) • log(1/ε)/ε2) and O(log (1/δ) • (log Δ/ε)O(d)) bits of memory, respectively (we assume that the dimension d is a constant), and they are correct with probability 1-δ. These results are based on a new data structure that maintains a set of elements chosen (almost) uniformly at random from P.
AU - Frahling, Gereon
AU - Indyk, Piotr
AU - Sohler, Christian
ID - 23883
T2 - Proceedings of the twenty-first annual symposium on Computational geometry - SCG '05
TI - Sampling in dynamic data streams and applications
ER -
TY - CHAP
AU - Köhler, Sven
AU - Schindelhauer, Christian
AU - Ziegler, Martin
ID - 17988
SN - 0302-9743
T2 - Fundamentals of Computation Theory
TI - On Approximating Real-World Halting Problems
ER -
TY - CHAP
AU - Meer, Klaus
AU - Ziegler, Martin
ID - 17989
SN - 0302-9743
T2 - Fundamentals of Computation Theory
TI - An Explicit Solution to Post’s Problem over the Reals
ER -
TY - CONF
AB - The sometimes so-called Main Theorem of Recursive Analysis implies that any computable real function is necessarily continuous. We consider three relaxations of this common notion of real computability for the purpose of treating also discontinuous functions f:R->R:
*) non-deterministic computation;
*) relativized computation, specifically given access to oracles like 0' or 0'';
*) encoding input x and/or output y=f(x) in weaker ways according to the Real Arithmetic Hierarchy.
It turns out that, among these approaches, only the first one provides the required power.
AU - Ziegler, Martin
ID - 18280
SN - 0302-9743
T2 - Proc. CiE 2005: New Computational Paradigms
TI - Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism
VL - 3526
ER -
TY - JOUR
AU - Ziegler, Martin
ID - 18282
IS - 11
JF - International Journal of Theoretical Physics
SN - 0020-7748
TI - Computational Power of Infinite Quantum Parallelism
VL - 44
ER -
TY - CONF
AU - Dangelmaier, Wilhelm
AU - Mueck, Bengt
AU - Fischer, Matthias
AU - Mahajan, Kiran
AU - Laroque, Christoph
ID - 18366
T2 - Simulation in wider Europe - 19th European Conference on Modelling and Simulation ECMS 2005
TI - Methods to lead the user to significant processes in a 3D material flow simulation
ER -
TY - CONF
AU - Loeser, Christoph
AU - Drüke, Isabell
AU - Oesterdiekhoff, Brigitte
ID - 18449
T2 - IEEE International Conference on Industrial Informatics (INDIN)
TI - Glaschick, Rainer: Integrative Approach of Web Services and Universal Plug and Play within an AV Scenario
ER -
TY - CONF
AU - Oesterdiekhoff, Brigitte
ID - 18450
T2 - IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)
TI - Glaschick, Rainer; Service Oriented Interface Design for Embedded Devices
ER -
TY - CHAP
AU - Bienkowski, Marcin
AU - Korzeniowski, Miroslaw
AU - Meyer auf der Heide, Friedhelm
ID - 16468
SN - 0302-9743
T2 - Peer-to-Peer Systems IV
TI - Dynamic Load Balancing in Distributed Hash Tables
ER -
TY - CHAP
AU - Bienkowski, Marcin
AU - Meyer auf der Heide, Friedhelm
ID - 16469
SN - 0302-9743
T2 - Mathematical Foundations of Computer Science 2005
TI - Page Migration in Dynamic Networks
ER -
TY - CONF
AB - We present a web computing library (PUBWCL) in Java that allows to execute strongly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style on PCs distributed over the internet whose owners are willing to donate their unused computation power.
PUBWCL is realized as a peer-to-peer system and features migration and restoration of BSP processes executed on it.
The use of Java guarantees a high level of security and makes PUBWCL platform independent. In order to estimate the loss of efficiency inherent in such a Java-based system, we have compared it to our C-based PUB-Library.
AU - Bonorden, Olaf
AU - Gehweiler, Joachim
AU - Meyer auf der Heide, Friedhelm
ID - 16470
SN - 0302-9743
T2 - Proceeedings of 6th International Conference on Parallel Processing and Applied Mathematics (PPAM)
TI - A Web Computing Environment for Parallel Algorithms in Java
ER -
TY - CONF
AB - We compare different load balancing strategies for Bulk-Synchronous Parallel (BSP) programs in a web computing environment. In order to handle the influence of the fluctuating available computation power, we classify the external work load.
We evaluate the load balancing algorithms using our web computing library for BSP programs in Java (PUBWCL). Thereby we simulated the external work load in order to have repeatable testing conditions.
With the best performing load balancing strategy we could save 39% of the execution time averaged and even up to 50% in particular cases.
AU - Bonorden, Olaf
AU - Gehweiler, Joachim
AU - Meyer auf der Heide, Friedhelm
ID - 16471
SN - 0302-9743
T2 - Proceeedings of 6th International Conference on Parallel Processing and Applied Mathematics (PPAM)
TI - Load Balancing Strategies in a Web Computing Environment
ER -
TY - CONF
AU - Bienkowski, Marcin
AU - Damerow, Valentina
AU - Meyer auf der Heide, Friedhelm
AU - Sohler, Christian
ID - 17112
T2 - Proceedings of the 21st European Workshop on Computational Geometry, Eindhoven, The Netherlands, March 9-11, 2005
TI - Average case complexity of Voronoi diagrams of n sites from the unit cube
ER -
TY - GEN
ED - Leonardi, Stefano
ED - Meyer auf der Heide, Friedhelm
ED - Wagner, Dorothea
ID - 17113
TI - Abstracts Collection -- Algorithmic Aspects of Large and Complex Networks
VL - 05361
ER -
TY - JOUR
AU - Ziegler, Martin
ID - 15058
JF - Theoretical Computer Science
SN - 0304-3975
TI - Stability versus speed in a computable algebraic model
ER -
TY - THES
AU - Salzwedel, Kay
ID - 19616
SN - 3-935433-62-X
TI - Data Distribution Algorithms for Storage Networks
VL - 153
ER -
TY - CONF
AU - Briest, Patrick
AU - Brockhoff, Dimo
AU - Degener, Bastian
AU - Englert, Matthias
AU - Gunia, Christian
AU - Heering, Oliver
AU - Jansen, Thomas
AU - Leifhelm, Michael
AU - Plociennik, Kai
AU - Röglin, Heiko
AU - Schweer, Andrea
AU - Sudholt, Dirk
AU - Tannenbaum, Stefan
AU - Wegener, Ingo
ID - 19692
SN - 0302-9743
T2 - Parallel Problem Solving from Nature - PPSN VIII
TI - The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes
ER -
TY - CONF
AU - Schweer, Andrea
AU - Leifhelm, Michael
AU - Degener, Bastian
AU - Heering, Oliver
AU - Tannenbaum, Stefan
AU - Röglin, Heiko
AU - Gunia, Christian
AU - Englert, Matthias
AU - Briest, Patrick
AU - Sudholt, Dirk
AU - Brockhoff, Dimo
AU - Wegener, Ingo
AU - Jansen, Thomas
AU - Plociennik, Kai
ID - 19693
T2 - Parallel Problem Solving from Nature - PPSN VIII
TI - Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization
ER -
TY - CONF
AB - Redundant arrays of independent disks, also called RAID arrays, have gained a wide popularity in the last twenty years. Most of the disks used in the server market are currently based on RAID technology. The primary reason for introducing RAID technology in 1988 has been the fact that large disk systems have become much slower and more expensive than the connection of a large number of inexpensive disks and the use of them as an array. The times seem to repeat themselves. Today, large scale RAID arrays have become incredible big and expensive. It seems that it makes sense to replace them by a collection of smaller and inexpensive arrays of JBODs or mid-ranged RAID arrays. In this paper we will show that combining these systems with state-of-the-art virtualization technology can lead to a system that is faster and less expensive than an enterprise storage system, while being as easy to manage and as reliable. Therefore we will outline the most important features of storage management and compare there realization in enterprise class storage systems and in current and future virtualization environments.
AU - Brinkmann, André
AU - Salzwedel, Kay
AU - Vodisek, Mario
ID - 19800
T2 - Proceedings of the international workshop on Storage network architecture and parallel I/Os - SNAPI '04
TI - A case for virtualized arrays of RAID
ER -
TY - CONF
AB - Wireless connectivity is state of the art for local area networks. Currently, most W-LAN networks rely on a centralized design with access points routing all inner and outbound traffic. These access points are intrinsic communication bottlenecks. Mobile Ad Hoc Networks (MANET) overcome this problem, because every participant works as well as a simple node and as a router. Current MANETs are restricted in scalability, because they rely on flooding mechanisms or complete routing tables. Other approaches, providing better scalability use clustering, yet network performance deteriorates in case of high node mobility. We describe the design of a PAMANET, the Paderborn Mobile Ad Hoc Network, a MANET overcoming these problems providing scalability and reliability in a mobile scenario. When implemented, PAMANET works with standard W-LAN IEEE 802.11 radio devices, provides IPv6 communication interfaces and works on personal computers under a standard Linux distribution. First, we present current routing protocols and classify them with respect to scalability and stability in dynamically evolving MANETs. Then, we discuss related research in the area of distributed hash tables and consistent hashing, used for relieving hot spots in the Web, storage area networks and peerto-peer networks, which inspires the design of PAMANET. PAMANET consists of three main components: First, the embedding of the routing layer into IEEE 802.11 and IPv6 by using techniques used at the ad hoc support library (aslib) by Gupta et al. Second, the routing layer which combines a landmark routing, hierarchical clustering, consistent hashing for providing location dependent addresses and lookup-service for the location of nodes. Third, a peerto-peer data storage system based on egoistic distributed caches enabling hop and traffic efficient data access on replicated data partitions.
The routing layer incorporates a variety of new approaches. Link distances reflect the failure probability of links, which is estimated by the reciprocal age of the link. Then, we combine a landmarking system on this metric with the hierarchical layer graph yielding small landmark addresses and small routing tables. To balance the load of the distributed lookup-service for landmark addresses, a hierarchical weighted consistent hashing scheme is used. This ensures that each node receives an equal part of all landmark addresses. Using these mechanisms (regularly and on demand) PAMANET adjusts IPv6 routing tables such that short stable routes are preferred. For the distribution of control data like landmark information PAMANET uses a message box system interface to provide fast one-hop communication. On top of this system, PAMANET provides a peer-to-peer data storage and lookup system that realizes time, traffic, and load efficient access using egoistic caches and data segmentation strategies.
AU - Schindelhauer, Christian
AU - Böttcher, Stefan
AU - Rammig, Franz
ID - 19807
SN - 1581139209
T2 - Proceedings of the second international workshop on Mobility management & wireless access protocols
TI - The design of PaMaNet the Paderborn mobile ad-hoc network
ER -
TY - CONF
AB - The Internet-SCSI protocol [iSCSI] allows a client to interact with a remote SCSI-capable target by means of block-oriented commands encapsulated within TCP/IP packets. Thereby, iSCSI greatly simplifies storage virtualization, since clients can access storage in a unified manner, no matter whether the I/O-path is short or long distance. Intermediate devices located on the path between a client and a target can easily intercept iSCSI sessions and rewrite packets for the sake of load balancing, prefetching, or redundancy, to mention just a few beneficial applications. Within this paper we describe the design and implementation of such an iSCSI capable intermediate device that deploys prefetching strategies in combination with redundant disks to reduce average I/O-latency. Depending on its location within the network, this virtualization and prefetching device can hide wide area access latency and reduce network contention targeting remote SCSI-devices to a large extent.
AU - Bleckmann, Peter
AU - Schomaker, Gunnar
AU - Slowik, Adrian
ID - 19851
IS - 2
T2 - Proceeding of International Workshop on Storage Network Architecture and Parallel I/O
TI - Virtualization with prefetching abilities based on iSCSI
ER -
TY - JOUR
AU - Klein, Jan
AU - Zachmann, Gabriel
ID - 19879
IS - 6
JF - Computers and Graphics
TI - Point Cloud Surfaces using Geometric Proximity Graphs
VL - 28
ER -
TY - CONF
AU - Klein, Jan
AU - Zachmann, Gabriel
ID - 19883
T2 - Eurographics Symposium on Point-Based Grahics (SPBG'04)
TI - Proximity Graphs for Defining Surfaces over Point Clouds
ER -
TY - CONF
AU - Klein, Jan
AU - Zachmann, Gabriel
ID - 19889
T2 - SIGGRAPH 2004, Sketches
TI - Nice and Fast Implicit Surfaces over Noisy Point Clouds
ER -
TY - CONF
AU - Klein, Jan
AU - Zachmann, Gabriel
ID - 19891
T2 - Computer Graphics Forum (Proceedings of EUROGRAPHICS 2004)
TI - Point Cloud Collision Detection
ER -
TY - CONF
AU - Volbert, Klaus
ID - 26411
T2 - Proceedings of the 2004 joint workshop on Foundations of mobile computing - DIALM-POMC '04
TI - Experimental analysis of adjustable sectorized topologies for static ad hoc networks
ER -
TY - GEN
AU - Rührup, Stefan
AU - Schindelhauer, Christian
ID - 26992
TI - Traffic and Hop Efficient Position-based Routing using a Cell Structure
ER -
TY - CONF
AU - Brinkmann, André
AU - Heidebuer, Michael
AU - Meyer auf der Heide, Friedhelm
AU - Rückert, Ulrich
AU - Salzwedel, Kay
AU - Vodisek, Mario
ED - Kobler, Ben
ED - Hariharan, P. C.
ID - 17346
T2 - 21st {IEEE} Conference on Mass Storage Systems and Technologies / 12th {NASA} Goddard Conference on Mass Storage Systems and Technologies, Greenbelt, Maryland, USA
TI - V:Drive - Costs and Benefits of an Out-of-Band Storage Virtualization System
ER -
TY - CONF
AU - Sohler, Christian
AU - Damerow, Valentina
ID - 18777
T2 - Proceedings of the 20th European Workshop on Computational Geometry (EWCG'04)
TI - Smoothed Number of Extreme Points under Uniform Noise
ER -
TY - CONF
AB - Given a point set P in the d-dimensional unit hypercube, we give upper bounds on the maximal expected number of extreme points when each point is perturbed by small random noise chosen independently for each point from the same noise distribution Δ. Our results are parametrized by the variance of the noise distribution. For large variance we essentially consider the average case for distribution Δ while for variance 0 we consider the worst case. Hence our results give upper bounds on the number of extreme points where our input distributions range from average case to worst case.
Our main contribution is a rather general lemma that can be used to obtain upper bounds on the expected number of extreme points for a large class of noise distributions. We then apply this lemma to obtain explicit bounds for random noise coming from the Gaussian normal distribution of variance σ² and the uniform distribution in a hypercube of side length &epsilon. For these noise distributions we show upper bounds of O( (1/ σ )^d * log^3/2 * d - 1 n ) and O( ( (n log n) / ε )^d/(d+1) ), respectively. Besides its theoretical motivation our model is also motivated by the observation that in many applications of convex hull algorithms the input data is inherently noisy, e.g. when the data comes from physical measurement or imprecise arithmetic is used.
AU - Damerow, Valentina
AU - Sohler, Christian
ID - 18778
SN - 0302-9743
T2 - Proceedings of the 12th European Symposium on Algorithms (ESA'04)
TI - Extreme Points Under Random Noise
ER -
TY - CONF
AB - A limiting factor in the performance of a render- ing system is the number of state changes, i.e., changes of the attributes material, texture, shader program, etc., in the stream of rendered primitives. We propose to include a small buffer between appli- cation and graphics hardware in the rendering sys- tem. This pipeline buffer is used to rearrange the incoming sequence of primitives on-line and locally in such a way that the number of state changes is minimized. This method is generic; it can be easily integrated into existing rendering systems. In our experiments a pipeline buffer reduces the number of state changes by an order of magnitude and achieves almost the same rendering time as an optimal, i.e., presorted, sequence without pipeline buffer. Due to its simple structure and its low mem- ory requirements this method can easily be imple- mented in software or even hardware.
AU - Sohler, Christian
AU - Krokowski, Jens
AU - Räcke, Harald
AU - Westermann, Matthias
ID - 18785
T2 - Proceedings of the Vision, Modeling, and Visualization Conference (VMV 2004)
TI - Reducing State Changes with a Pipeline Buffer
ER -
TY - CONF
AU - Sohler, Christian
AU - Czumaj, Artur
ID - 18786
IS - 1
T2 - Automata, Languages and Programming (ICALP)
TI - Sublinear-Time Approximation for Clustering via Random Sampling
ER -
TY - JOUR
AU - Ziegler, Martin
AU - Brattka, Vasco
ID - 17986
IS - 1-3
JF - Theoretical Computer Science
TI - Computability in linear algebra
VL - 326
ER -
TY - CONF
AB - For uniform computability of regular sets in Euclidean space, previous work has identified twelve 'basic' notions, to (pairs of) which many previous notions considered in literature were shown to be equivalent.
With respect to those basic notions, we now investigate on the computability of natural OPERATIONS on regular sets: union, intersection, complement, convex hull, image, and pre-image under suitable classes of functions.
AU - Ziegler, Martin
ID - 18260
IS - 4-5
SN - 0942-5616
T2 - Computability and Complexity in Analysis
TI - Computable operators on regular sets
VL - 50
ER -
TY - CONF
AB - We generalize univariate multipoint evaluation of polynomials of degree n at sublinear amortized cost per point. More precisely, it is shown how to evaluate a bivariate polynomial p of maximum degree less than n, specified by its n^2 coefficients, simultaneously at n^2 given points using a total of O(n^2.667) arithmetic operations. In terms of the input size N being quadratic in n, this amounts to an amortized cost of O(N^0.334) per point.
AU - Nüsken, Michael
AU - Ziegler, Martin
ID - 18263
SN - 0302-9743
T2 - Proc. 12th Annual Symposium on Algorithms (ESA'04)
TI - Fast Multipoint Evaluation of Bivariate Polynomials
VL - 3221
ER -
TY - CONF
AB - For $c in REAL$, a $c$-spanner is a subgraph of a complete Euclidean graph satisfying that between any two vertices there exists a path of weighted length at most $c$ times their geometric distance. Based on this property to approximate a complete weighted graph, sparse spanners have found many applications, e.g., in FPTAS, geometric searching, and radio networks. For geometric searching, it turned out to suffice whether the radius rather than the length of some path between any two vertices is bounded relatively to their geometric distance; this is the defining property of weak spanners. Finally regarding radio network applications, a power spanner accounts for the total energy afforded for a wireless transmission with the requirement that the sum of the squares of the lengths of some path between any two planar vertices must be bounded relatively to the square of their geometric distance (or higher powers up to 6 or even 8).
While it is known that any $c$-spanner is also both a weak $C_1$-spanner and a $C_2$-power spanner (for appropriate $C_1,C_2$ depending only on $c$ but not on the graph under consideration), we show that the converse fails: There exists a family of $c_1$-power spanners that are no weak $C$-spanners and also a family of weak $c_2$-spanners that are no $C$-spanners for any fixed $C$ (and thus no uniform spanners, either). However the deepest result of the present work reveals that, surprisingly, any weak spanner is also a uniform power spanner. We further generalize the latter notion by considering $(c,delta)$-power spanners where the sum of the $delta$-th powers of the lengths has to be bounded; so $(cdot,2)$-power spanners coincide with the usual power spanners and $(cdot,1)$-power spanners are classical spanners. Interestingly, these $(cdot,delta)$-power spanners form a strict hierarchy where the above results still hold for any $deltageq2$; some even hold for $delta>1$ while counterexamples reveal others to fail for $delta<2$. In fact we show that in general every self-similar curve of fractal dimension $d>delta$ is no $(C,delta)$-power spanner for any fixed $C$.
AU - Schindelhauer, Christian
AU - Volbert, Klaus
AU - Ziegler, Martin
ID - 18279
SN - 0302-9743
T2 - Proc. of 15th Annual International Symposium on Algorithms and Computation (ISAAC'04)
TI - Spanners, Weak Spanners, and Power Spanners for Wireless Networks
VL - 3341
ER -
TY - CONF
AB - The visualisation of manufacturing-processes assists the user in understanding and analysis.
Typically he can move free and unguided in a virtual environment which visualizes the entire
process. Thus knowledge and conclusions are to some extend acquired on a random base.
This article describes the development of a tool, which enables the user to interactively improve
significant production processes in the simulation. He moves in a virtual 3D-environment
(walkthrough system) and is able to acquire automatically calculated indications for significant
processes. At the same time the simulation considers significant objects in a more detailed way. If
the viewer is interested in a significant process, he is automatically guided to the relevant location
where he can examine the critical situation by modification of the simulation model.
AU - Mueck, Bengt
AU - Dangelmaier, Wilhelm
AU - Laroque, Christoph
AU - Fischer, Matthias
AU - Kortenjan, Michael
ID - 18364
T2 - Simulation and Visualisation 2004
TI - Guidance of Users in Interactive 3D-Visualisations of Material Flow Simulations
ER -
TY - JOUR
AU - Oesterdiekhoff, Brigitte
ID - 18447
IS - 5
JF - Informatik Spektrum
TI - Transcoding von Webinhalten
VL - 27
ER -
TY - CONF
AU - Oesterdiekhoff, Brigitte
ID - 18448
T2 - Proceedings of IFIP Working Conference on Distributed and Parallel Embedded Systems (DIPES'04)
TI - Internet Premium Services for Flexible Format Distributed Devices
ER -
TY - CONF
AB - Given n distinct points p1, p2, ... , pn in the plane, the map labeling
problem with four squares is to place n axis-parallel equi-sized squares Q1, ... ,Qn
of maximum possible size such that pi is a corner of Qi and no two squares overlap.
This problem is NP-hard and no algorithm with approximation ratio better
than 1/2 exists unless P = NP [10].
In this paper, we consider a scenario where we want to visualize the information
gathered by smart dust, i.e. by a large set of simple devices, each consisting of
a sensor and a sender that can gather sensor data and send it to a central station.
Our task is to label (the positions of) these sensors in a way described by the
labeling problem above. Since these devices are not positioned accurately (for
example, they might be dropped from an airplane), this gives rise to consider the
map labeling problem under the assumption, that the positions of the points are
not fixed precisely, but perturbed by random noise. In other words, we consider
the smoothed complexity of the map labeling problem. We present an algorithm
that, under such an assumption and Gaussian random noise with sufficiently large
variance, has linear smoothed complexity.
AU - Bansal, Vikas
AU - Meyer auf der Heide, Friedhelm
AU - Sohler, Christian
ID - 16474
SN - 0302-9743
T2 - 12th Annual European Symposium on Algorithms (ESA 2004)
TI - Labeling Smart Dust
VL - 3221
ER -
TY - CONF
AU - Bienkowski, Marcin
AU - Korzeniowski, Miroslaw
AU - Meyer auf der Heide, Friedhelm
ID - 16475
SN - 1581138407
T2 - Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures - SPAA '04
TI - Fighting against two adversaries
ER -
TY - JOUR
AU - Meyer auf der Heide, Friedhelm
AU - Schindelhauer, Christian
AU - Volbert, Klaus
AU - Grünewald, Matthias
ID - 16477
JF - Theory of Computing Systems
SN - 1432-4350
TI - Congestion, Dilation, and Energy in Radio Networks
ER -
TY - CONF
AU - Leonardi, S.
AU - Marchetti-Spaccamela, A.
AU - Meyer auf der Heide, Friedhelm
ID - 16480
SN - 1581138407
T2 - SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures
TI - Scheduling against an adversarial network
ER -
TY - JOUR
AB - We present a new data structure for rendering highly complex virtual environments of arbitrary topology. The special feature of our approach is that it allows an interactive navigation in very large scenes (30 GB/400 million polygons in our benchmark scenes) that cannot be stored in main memory, but only on a local or remote hard disk. Furthermore, it allows interactive rendering of substantially more complex scenes by instantiating objects.
The sampling process is done in the preprocessing. There, the polygons are randomly distributed in our hierarchical data structure, the randomized sample tree. This tree only uses space that is linear in the number of polygons. In order to produce an approximate image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk.
We implemented our algorithm in a prototypical walkthrough system. Analysis and experiments show that the quality of our images is comparable to images computed by the conventional z-buffer algorithm regardless of the scene topology.
AU - Klein, Jan
AU - Krokowski, Jens
AU - Fischer, Matthias
AU - Wand, Michael
AU - Wanka, Rolf
AU - Meyer auf der Heide, Friedhelm
ID - 16399
JF - Presence: Teleoperators and Virtual Environments
SN - 1054-7460
TI - The Randomized Sample Tree: A Data Structure for Interactive Walk-Throughs in Externally Stored Virtual Environments
ER -
TY - CONF
AU - Liu Jing, Michelle
AU - Ruehrup, Stefan
AU - Schindelhauer, Christian
AU - Volbert, Klaus
AU - Dierkes, Martin
AU - Bellgardt, Andreas
AU - Ibers, Rüdiger
AU - Hilleringmann, Ulrich
ID - 13071
T2 - {GOR/NGB Conference Tilburg 2004}
TI - Sensor Networks with More Features Using Less Hardware
ER -
TY - JOUR
AB - The Paderborn University BSP (PUB) library is a C communication library based on the BSP model. The basic library supports buffered as well as unbuffered non-blocking communication between any pair of processors and a mechanism for synchronizing the processors in a barrier style. In addition, PUB provides non-blocking collective communication operations on arbitrary subsets of processors, the ability to partition the processors into independent groups that execute asynchronously from each other, and a zero-cost synchronization mechanism. Furthermore, some techniques used in the implementation of the PUB library deviate significantly from the techniques used in other BSP libraries.
AU - Bonorden, Olaf
AU - Juurlink, Bernhardus
AU - von Otte, Ingo
AU - Rieping, Ingo
ID - 19726
JF - Parallel Computing
SN - 0167-8191
TI - The Paderborn University BSP (PUB) library
ER -
TY - JOUR
AU - Salzwedel, Kay A.
ID - 19785
JF - Algorithms for Memory Hierarchies
SN - 0302-9743
TI - Algorithmic Approaches for Storage Networks
VL - 2625
ER -
TY - CONF
AB - The advances in Internet technology have led to tremendous improvements in business, education, and science and have changed the way we think, live, and communicate. Information exchange has become ubiquitous by the possibilities offered through modern technologies. We are able to offer information 24 hours a day through our web sites and can leave messages every time and from anywhere in the world. This change in communication has led to new challenges. Enterprises have to deal with an information amount that doubles every year. The technological foundation to cope with this information explosion is given by Storage Area Networks (SANs), which are able to connect a great number of storage systems over a fast interconnection network. However, to be able to use the benefits of a SAN, an easy-to-use and efficient management support has to be given to the storage administrator. In this paper, we will suggest new storage management concepts and we will introduce a new management environment that is able to significantly reduce management costs and increases the performance and resource utilization of the given SAN infrastructure.
AU - Scheideler, Christian
AU - Salzwedel, Kay
AU - Meyer auf der Heide, Friedhelm
AU - Brinkmann, André
AU - Vodisek, Mario
AU - Rückert, Ulrich
ID - 19790
T2 - Proceedings of SSGRR 2003
TI - Storage Management as Means to cope with Exponential Information Growth
ER -
TY - CONF
AB - We try to close the gap between theoretical investigations of wireless network topologies and realistic wireless environments. For point-to-point communication, we examine theoretically well-analyzed sparse graphs, i.e. the Yao-graph, the SparsY-graph, and the SymmY-graph. We present distributed algorithms that can be used to build up these graphs in time $O(log n)$ per node without the use of any geo-graphical positioning system. Our algorithms are based only on local knowledge and local decisions and make use of power control to establish communication links with low energy-cost. We compare these algorithms with respect to congestion, dilation, and energy. For congestion we introduce different measures that allow us to investigate the difference between real-world wireless networks and models for wireless communication at a high level of abstraction. For more realistic simulations we extend our simulation environment SAHNE. We use a realistic transmission model for directed communication that uses sector subdivision. Finally, our experimental results show that our topologies and algorithms work well in a distributed environment and we give some recommendations for the topology control based on our simulations.
AU - Rührup, Stefan
AU - Schindelhauer, Christian
AU - Volbert, Klaus
AU - Grünewald, M.
ID - 19806
SN - 0769519261
T2 - Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS)
TI - Performance of distributed algorithms for topology control in wireless networks
ER -
TY - GEN
AU - Mahlmann, Peter
ID - 19828
TI - Implementierung und Vergleich von Verfahren zum Information Retrieval im World Wide Web
ER -
TY - CONF
AB - Communication facilities are important in Robotics if several robots have to work together. In this paper, we describe problems and solutions encountered while designing an infrared-based communication device for the mini robot Khepera. In contrast to traditional omnidirectional systems, it features directed, power-variable transmission in eight directions at unit[23.4]kbps up to a range of unit[1m]. It can differentiate incoming data signals from interference from adjacent sectors and can estimate their direction-of-arrival. We model the transmission over the infrared channel and show how interference influences the reception of the data signals. We also describe methods how to reduce these effects. We have tested the performance of the resulted signal processing in a worst case scenario by simulations and in experiments with a prototype implementation. The resulted module is especially suited for experimental evaluation of ad hoc network protocols and for position estimation.
AU - Volbert, Klaus
AU - Grünewald, Matthias
AU - Schindelhauer, Christian
AU - Rückert, Ulrich
ID - 19833
T2 - Proceedings of the 2nd International Conference on Autonomous Minirobots for Research and Edutainment
TI - Directed power-variable infrared communication for the mini robot Khepera
ER -
TY - CONF
AB - We present a novel framework for hierarchical collision detection that can be applied to virtually all bounding volume (BV) hierarchies. It allows an application to trade quality for speed. Our algorithm yields an estimation of the quality, so that applications can specify the desired quality. In a timecritical system, applications can specify the maximum time budget instead, and quantitatively assess the quality of the results returned by the collision detection afterwards.
AU - Klein, Jan
AU - Zachmann, Gabriel
ID - 19874
T2 - Proc. 8th International Fall Workshop Vision, Modeling, and Visualization (VMV 2003)
TI - ADB-Trees: Controlling the Error of Time-Critical Collision Detection
ER -
TY - CONF
AU - Klein, Jan
AU - Zachmann, Gabriel
ID - 19900
T2 - Proc. ACM Symposium on Virtual Reality Software and Technology (VRST 2003)
TI - Time-Critical Collision Detection Using an Average-Case Approach
ER -
TY - CONF
AB - Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory is that it is mainly of theoretical importance. The main purpose of this paper is to show how very deep min-max and duality theorems from Graph Minors can be used to obtain essential speed-up to many known algorithms on different domination problems.
AU - Fomin, Fedor V.
AU - Thilikos, Dimitrios M.
ID - 19952
SN - 0097-5397
T2 - Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)
TI - Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
ER -
TY - CONF
AU - Terbahl, Martina
AU - Krokowski, Jens
ID - 24273
T2 - Proceedings of 5. GI-Informatiktage 2003
TI - Verteiltes Rendern durch dynamische Bildaufteilung
ER -
TY - CONF
AU - Ziegler, Martin
ID - 26263
T2 - Proc. 5th Conference on Real Numbers and Computers (RNC5), INRIA
TI - Stability versus Speed in a Computable Algebraic Model
ER -
TY - CONF
AU - Ziegler, Martin
ID - 26277
T2 - Computability and Complexity in Analysis
TI - Computable Operators on Regular Sets
VL - 302-8/2003
ER -
TY - CONF
AU - Damerow, Valentina
AU - Meyer auf der Heide, Friedhelm
AU - Räcke, Harald
AU - Scheideler, Christian
AU - Sohler, Christian
ID - 2128
T2 - ESA
TI - Smoothed Motion Complexity
VL - 2832
ER -
TY - CONF
AU - Awerbuch, Baruch
AU - Brinkmann, André
AU - Scheideler, Christian
ID - 2129
T2 - ICALP
TI - Anycasting in Adversarial Systems: Routing and Admission Control
VL - 2719
ER -
TY - CONF
AU - Mueck, Bengt
AU - Dangelmaier, Wilhelm
AU - Fischer, Matthias
ID - 17423
T2 - 15th European Simulation Symposium (ESS 2003)
TI - Components for the Active Support of the Analysis of Material Flow Simulations in a Virtual Environment
ER -
TY - CONF
AB - We consider the problem of finding the weight of a Euclidean minimum spanning tree for a set of n points in ℝd. We focus on the situation when the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within 1 + ε using only \~{O}(√ poly(1/ε)) queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbors queries.
AU - Magen, Avner
AU - Ergun, Funda
AU - Sohler, Christian
AU - Rubinfeld, Ronitt
AU - Czumaj, Artur
AU - Newman, Ilan
AU - Fortnow, Lance
ID - 18791
SN - 0898715385
T2 - Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)
TI - Sublinear Approximation of Euclidean Minimum Spanning Tree
ER -
TY - CONF
AB - In a (randomized) oblivious routing scheme the path chosen for a request
between a source $s$ and a target $t$ is independent from the current traffic
in the network. Hence, such a scheme consists of probability distributions
over $s-t$ paths for every source-target pair $s,t$ in the network.
In a recent result citeR02 it was shown that for any undirected network
there is an oblivious routing scheme that achieves a polylogarithmic
competitive ratio with respect to congestion. Subsequently, Azar et
al. citeACF+03 gave a polynomial time algorithm that for a given network
constructs the best oblivious routing scheme, i.e. the scheme that guarantees
the best possible competitive ratio.
Unfortunately, the latter result is based on the Ellipsoid algorithm; hence
it is unpractical for large networks.
In this paper we present a combinatorial algorithm for constructing an
oblivious routing scheme that guarantees a competitive ratio of $O(log^4n)$
for undirected networks. Furthermore, our approach yields a proof
for the existence of an oblivious routing scheme with competitive ratio
$O(log^3n)$, which is much simpler than the original proof from citeR02.
AU - Bienkowski, Marcin
AU - Korzeniowski, Miroslaw
AU - Räcke, Harald
ID - 18907
SN - 1581136617
T2 - Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03
TI - A practical algorithm for constructing oblivious routing schemes
ER -
TY - CONF
AB - In this paper, we define a Petri net model for the network or routing layer of a mobile ad hoc network. Such networks require routing strategies substantially different from those used in static communication networks. The model pre- sented consists of two layers, a location service and a po- sition based routing. Both are described in detail. Our ap- proach considers a very strong definition of fault tolerance thereby improving state-of-the-art ad hoc routing protocols in several respects. Modeling of the communication archi- tecture for mobile ad hoc networks is part of our overall effort towards a design methodology for distributed embed- ded real-time systems including dynamically evolving com- ponents.
AU - Rust, Carsten
AU - Stappert, Friedhelm
AU - Lukovszki, Tamás
ID - 18947
T2 - 7th World Multiconference on Systemics, Cybernetics and Informatics
TI - A Petri Net Model for the Network Layer of a Mobile Ad Hoc Network Architecture
ER -
TY - CONF
AB - We investigate distributed algorithms for mobile ad hoc networks for moving radio stations with adjustable transmission power in a worst case scenario. We consider two models to find a reasonable restriction on the worst-case mobility. In the pedestrian model we assume a maximum speed $v_max$ of the radio stations, while in the vehicular model we assume a maximum acceleration $a_max$ of the points. Our goal is to maintain persistent routes with nice communication network properties like hop-distance, energy-consumption, congestion and number of interferences. A route is persistent, if we can guarantee that all edges of this route can be uphold for a given time span $Delta$, which is a parameter denoting the minimum time the mobile network needs to adopt changes, i.e. update routing tables, change directory entries, etc. This $Delta$ can be used as the length of an update interval for a proactive routing scheme. We extend some known notions such as transmission range, interferences, spanner, power spanner and congestion to both mobility models and introduce a new parameter called crowdedness that states a lower bound on the number of radio interferences. Then we prove that a mobile spanner hosts a path system that polylogarithmically approximates the optimal congestion. We present distributed algorithms based on a grid clustering technique and a high-dimensional representation of the dynamical start situation which construct mobile spanners with low congestion, low interference number, low energy-consumption, and low degree. We measure the optimality of the output of our algorithm by comparing it with the optimal choice of persistent routes under the same circumstances with respect to pedestrian or vehicular worst-case movements. Finally, we present solutions for dynamic position information management under our mobility models.
AU - Schindelhauer, Christian
AU - Lukovszki, Tamás
AU - Rührup, Stefan
AU - Volbert, Klaus
ID - 18960
SN - 1581136617
T2 - Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03)
TI - Worst case mobility in ad hoc networks
ER -
TY - CONF
AB - A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately, Räcke's construction is not polynomial time. We give a polynomial time construction that guarantees Räcke's bounds, and more generally gives the true optimal ratio for any (undirected or directed) network.
AU - Azar, Yossi
AU - Cohen, Edith
AU - Fiat, Amos
AU - Kaplan, Haim
AU - Racke, Harald
ID - 18966
SN - 1581136749
T2 - Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC '03
TI - Optimal oblivious routing in polynomial time
ER -
TY - GEN
AB - In dieser Studienarbeit wurde ein System entworfen und implementiert, das der Ausführung paralleler Algorithmen nach dem Bulk-Synchronous Parallel (BSP)-Modell dient. Von der Paderborn University BSP Library (PUB) unterscheidet es sich dadurch, dass es vom Einsatzgebiet her nicht für Parallelrechner konzipiert ist, sondern vielmehr für eine Ansammlung von PCs und Workstations, die über das gesamte Internet verteilt sind.
Gegenüber anderen bekannten Web-Computing Projekten wie z.B. SETI@home oder distributed.net zeichnet sich dieses System dadurch aus, dass nicht Clients von einem zentralen Server "häppchenweise" unabhängige Teilprobleme anfordern und lösen, sondern dass die Clients gemeinsam an einem Problem arbeiten, indem sie nach dem BSP-Modell miteinander kommunizieren und sich synchronisieren.
AU - Gehweiler, Joachim
ID - 18982
TI - Entwurf und Implementierung einer Laufzeitumgebung für parallele Algorithmen in Java
ER -
TY - JOUR
AU - Hamann, Heiko
ID - 20435
IS - 3
JF - Complex Systems
TI - Definition and Behavior of Langton's Ant in Three Dimensions
VL - 14
ER -
TY - CONF
AB - Fast algorithms for arithmetic on real or complex polynomials are well-known and have proven to be not only asymptotically efficient but also very practical. Based on FAST FOURIER TRANSFORM, they for instance multiply two polynomials of degree up to N or multi-evaluate one at N points simultaneously within quasi-linear time O(N polylog N). An extension to (and in fact the mere definition of) polynomials over fields R and C to the SKEW-field H of quaternions is promising but still missing. The present work proposes three approaches which in the commutative case coincide but for H turn out to differ, each one satisfying some desirable properties while lacking others. For each notion, we devise algorithms for according arithmetic; these are quasi-optimal in that their running times match lower complexity bounds up to polylogarithmic factors.
AU - Ziegler, Martin
ID - 18196
SN - 0302-9743
T2 - Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC'03)
TI - Quasi-optimal Arithmetic for Quaternion Polynomials
ER -
TY - CHAP
AB - Multi-evaluation of the Coulomb potential induced by N particles is a central part of N-body simulations. In 3D, known subquadratic time algorithms return approximations up to given ABSOLUTE precision. By combining data structures from Computational Geometry with fast polynomial arithmetic, the present work obtains approximations of prescribable RELATIVE error e>0 in time O(1/e*N*polylog N).
AU - Ziegler, Martin
ED - Dehne, F.
ED - Sack, JR.
ED - Smid, M.
ID - 18258
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Fast Relative Approximation of Potential Fields
VL - 2748
ER -
TY - CONF
AB - Unternehmen operieren zunehmend in einem schwierigen Umfeld: Die Innovationsdynamik nimmt zu; die Produktlebenszyklen werden kürzer; gleichzeitig werden die Produkte komplexer; der harte Wettbewerb zwingt die Unternehmen, auf Marktveränderungen zu reagieren. Aus dieser Entwicklung resultieren hohe Anforderungen an die Gestaltung der Fertigungsprozesse. Im Wesentlichen kommt es darauf an, die Fertigungsprozesse möglichst rasch an die neuen Gegebenheiten anzupassen, bzw. neue Fertigungsprozesse so zu planen, dass sie auf Anhieb die erforderlichen Resultate bringen.
Ein wichtiges Mittel hierfür der Einsatz von Materialflusssimulationen. Hierzu ist zunächst die Erstellung eines Simulationsmodells notwendig. Dafür wird in einem ersten Schritt das zu betrachtende System analysiert und ein rechnerinternes Modell erzeugt. Dieses beinhaltet die Modellierung von Funktionen, Prozessen, Verhaltensweisen oder Regeln, die im Modell die tatsächlichen Wirkzusammenhänge im Unternehmen widerspiegeln sollen. Die so modellierten Aspekte sind untereinander so vernetzt, dass alle Funktionen des Modells ein Ganzes ergeben. Für viele Fragenstellungen werden umfangreiche Modelle mit einem komplexen Verhalten benötigt. Andererseits steigt mit zunehmender Größe und Komplexität des Simulationsmodells auch der Modellierungsaufwand, die Fehleranfälligkeit, die Laufzeit und der Interpretationsaufwand bei der Ergebnisauswertung. Fehler bei der Modellbildung führen bei der Simulation zu Fehlinterpretationen und falschen Ergebnissen.
Einen wesentlichen Anteil daran hat die Gestaltung der Benutzungsschnittstelle: Das übliche, wenig intuitive WIMP-Interface (Windows, Icons, Mouse, Pointer) erfordert sehr gut geschulte Benutzer, sodass die Erzeugung der meist komplexen Simulationsmodelle mit großen Zeitaufwand verbunden ist. Die Präsentation der Simulationsergebnisse erfolgt in Form von Wertetabellen und zweidimensionalen, abstrakten Darstellungen des Fertigungssystems. Für die Simulationsexperten erscheint dies ausreichend, für ein aus verschiedenen Bereichen und Disziplinen zusammengesetztes Planungsteam ist das aber nicht akzeptabel. So können Fehlinterpretationen aufgrund der unklaren Darstellungen auftreten.
Durch eine durchgängige Unterstützung von der Modellierung über die Ausführung bis zur Analyse von Simulationen durch Augmented-Reality und Virtual-Reality werden viele dieser Probleme überwunden aber viele neue Probleme entstehen.
Marktgängige Simulatoren unterstützen zwar z.T. schon Virtual Reality; eine durchgängige Simulationsunterstützung wird aber in der Virtuellen Umgebung nicht geboten. Argumented Reality-Komponenten sind bisher nicht bekannt.
In diesem Artikel werden nach einer Analyse der benötigten Technologien die Nutzenpotentiale insb. durch den Einsatz von AR ausgelotet.
AU - Fischer, Matthias
AU - Grafe, Michael
AU - Matysczok, Carsten
AU - Mueck, Bengt
AU - Schoo, Michael
ID - 18367
T2 - Human Aspects in Production Management - Proceedings of the IFIP WG 5.7 Working Conference on Human Aspects in Production Management
TI - Virtual and Augmented Reality Support for Discrete Manufacturing System Simulation
VL - 5
ER -
TY - CONF
AB - Simulation und Visualisierung sind anerkannte Mittel zum Verstehen und Analysieren von Fertigungsprozessen. In Visualisierungen von Fertigungsprozessen können Betrachter frei und ungeleitet umherwandern. Erkenntnisse werden so aber eher zufällig erworben. Dieser Artikel skizziert ein System und Methoden, die den Betrachter unterstützen auf auffällige/signifikante Prozesse/ Punkte in Materialflusssimulationen aufmerksam zu werden und diese zu entschärfen.
Es wird der Entwurf eines Werkzeugs beschrieben, dass den Betrachter einer Simulation die Möglichkeit bietet, signifikante Produktionsprozesse interaktiv zu verbessern. Der Benutzer wird sich in einer virtuellen 3D-Umgebung (Walkthrough-System) bewegen können und automatisch ermittelte Indizien für signifikante Abläufe erhalten. Zugleich soll die Simulation signifikante Objekte genauer simulieren. Bekundet der Benutzer Interesse an einem signifikanten Prozess, wird er automatisch zu dem jeweiligen Ort geführt werden und dort durch Eingriffe in die Simulation die kritische Situation experimentell untersuchen können. Da der kritische Moment in der Vergangenheit liegt und somit vom Betrachter schon verpasst ist, wird es dem Betrachter möglich sein, die Simulation auf einen Zeitpunkt vor dem Eintreten zurück zu setzen.
Die virtuelle Szene (3D-Grafik-Modelle) einer typischen dynamischen Simulationsumgebung ist in der Regel zu komplex, um sie in Echtzeit in einem Walkthrough-System zu visualisieren und darzustellen. Typischerweise werden Approximationsverfahren eingesetzt, um die Komplexität zu reduzieren und ein flüssiges Navigieren des Betrachters zu erlauben. Durch spezifische Simulations-Anforderungen ist bekannt, an welchen Objekten des Simulationsmodells Probleme auftreten; sie sind für den Betrachter wichtig. Die zugehörigen virtuellen 3D-Repräsentanten, können von den Approximationsalgorithmen mit einer besonders hohen Darstellungsqualität dargestellt werden und die übrigen Teile der virtuellen Szene entsprechend vernachlässigt werden. Solche Approximationsalgorithmen und Datenstrukturen nutzen die spezifischen Eigenschaften virtueller Simulationsumgebungen aus, um eine hohe Darstellungsqualität und Darstellungsperformance zu erreichen.
AU - Dangelmaier, Wilhelm
AU - Franke, Werner
AU - Mueck, Bengt
AU - Fischer, Matthias
ID - 18372
T2 - 2. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung
TI - Komponenten zur aktiven Unterstützung der Analyse von Materialflusssimulationen in virtuellen Umgebungen
VL - 123
ER -
TY - CONF
AB - In der heutigen Zeit operieren Unternehmen zunehmend in einem schwierigen Umfeld: Die Innovationsdynamik nimmt zu und die Produktlebenszyklen werden kürzer. Daraus resultieren hohe Anforderungen an die Planung von Fertigungssysteme. Um diesen Prozess zu unterstützen, sollen die Technologien Augmented Reality und Virtual Reality in einem integrierten System genutzt werden. Dieses System unterstützt den Anwender bei der Modellbildung, der Validierung des Simulationsmodells sowie der folgenden Optimierung des Fertigungssystems. Durch die Entwicklung geeigneter Kopplungs- bzw. Integrationsmechanismen wird eine durchgängige Nutzung der Technologien AR, VR und Simulation realisiert. Die Visualisierung der anfallenden 3D-Daten innerhalb der VR- und ARUmgebungen erfolgt mittels einer 3D-Renderinglibrary, die es durch den Einsatz von neuen entwickelten Verfahren ermöglicht, die verwendeten 3D-Modelle weitgehend automatisiert aus unternehmensinternen 3D-CAD-Modellen zu generieren.
AU - Fischer, Matthias
AU - Grafe, Michael
AU - Matysczok, Carsten
AU - Schoo, Michael
AU - Mueck, Bengt
ID - 18374
T2 - 2. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung
TI - Planung von komplexen Fertigungssystemen durch Einsatz einer VR/AR-unterstützten Simulation
VL - 123
ER -
TY - JOUR
AU - Adler, Micah
AU - Vöcking, Berthold
AU - Sohler, Christian
AU - Räcke, Harald
AU - Sivadasan, Naveen
ID - 18567
JF - Combinatorics, Probability & Computing
TI - Randomized Pursuit-Evasion in Graphs
ER -
TY - THES
AU - Sohler, Christian
ID - 18573
SN - 3-935433-28-X
TI - Property Testing and Geometry
VL - 119
ER -
TY - JOUR
AB - ZusammenfassungVernetzte Systeme sind zu unverzichtbaren Bestandteilen unseres Umfelds geworden, zum Beispiel als Höchstleistungsrechner, als Kommunikations- und Informationssysteme oder als Planungs- und Steuerungskomponenten von Transport- und Produktionssystemen. Die ständig wachsende Komplexität solcher Systeme stellt Informatiker und Ingenieure vor immer neue Herausforderungen. In diesem Beitrag beschreibe ich die Zielsetzungen und die Struktur des SFB 376 Massive Parallelität: Algorithmen – Entwurfsmethoden – Anwendungen. Als Beispiel für unsere Arbeiten beschreibe ich einen algorithmisch orientierten Forschungszweig, in dem wir, ausgehend von theoretischen Problemen über effiziente Simulationen zwischen parallelen Rechenmodellen, Methoden, Techniken und Implementierungen entwickelt haben, die zu produktnahen Prototypen für die Speichervirtualisierung in verteilten Datenservern führen.
AU - Meyer auf der Heide, Friedhelm
ID - 16481
JF - it - Information Technology
SN - 2196-7032
TI - Sonderforschungsbereich 376 Massive Parallelität: Algorithmen – Entwurfsmethoden – Anwendungen (Massively Parallel Computing: Algorithms – Design Methods – Applications)
ER -
TY - JOUR
AU - Juurlink, Bernhardus
AU - Kolman, Petr
AU - Meyer auf der Heide, Friedhelm
AU - Rieping, Ingo
ID - 16482
JF - Journal of Discrete Algorithms
SN - 1570-8667
TI - Optimal broadcast on parallel locality models
ER -
TY - GEN
ED - Rosenberg, Arnold L.
ED - Meyer auf der Heide, Friedhelm
ID - 16484
SN - 1581136617
TI - Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03
ER -
TY - CONF
AU - Bonorden, Olaf
AU - Bruls, N.
AU - Kastens, U.
AU - Le, D. K.
AU - Meyer auf der Heide, Friedhelm
AU - Niemann, J.-C.
AU - Porrmann, M.
AU - Rückert, U.
AU - Slowik, A.
AU - Thies, M.
ID - 16720
T2 - 28th Annual IEEE International Conference on Local Computer Networks
TI - A holistic methodology for network processor design
ER -
TY - CONF
AU - Bonorden, Olaf
AU - Meyer auf der Heide, Friedhelm
AU - Wanka, Rolf
ID - 19727
T2 - Int. Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA)
TI - Composition of Efficient Nested BSP Algorithms: Minimum Spanning Tree Computation as an Instructive Example
ER -
TY - CONF
AU - Wanka, Rolf
ID - 19850
SN - 0302-9743
T2 - Proc. Workshop on Graph-Theoretic Concepts in Computer Science (WG)
TI - Any Load-Balancing Regimen for Evolving Tree Computations on Circulant Graphs Is Asymptotically Optimal
ER -
TY - CONF
AB - We present a new and easy to use framework for navigating through scenes of arbitrary complexity and topology. In the preprocessing, images for discrete viewpoints and viewing directions are rendered and stored on an external volume. During navigation each image can be displayed within a very short time by loading it from the volume. For acceleration, our prefetching strategy loads possibly needed images for the next few frames if the viewer takes a break. The measurements show that we achieve interactive frame rates, whereby the difference between the minimal and maximal display time is very small. Our system works well with scenes modelled by polygons, but also digital photos can easily be used for describing a 3D scene.
AU - Klein, Jan
AU - Krokowski, Jens
AU - Cuntz, Nicolas
ID - 19873
T2 - Proc. of 4. GI-Informatiktage
TI - Realtime Navigation in Highly Complex 3D-Scenes Using JPEG Compression
ER -
TY - JOUR
AB - We define here a distributed abstract state machine (DASM) [7] of
the network or routing layer of mobile ad hoc networks [13]. Such networks re-
quire routing strategies substantially different from those used in static commu-
nication networks, since storing and updating large routing tables at mobile
hosts would congest the network with administration packets very fast. In [1],
the hypercubic location service is presented, which considers a very strong
definition of fault-tolerance thereby improving state-of-the-art ad hoc routing
protocols in several respects. Our goal in modeling the protocols for the distrib-
uted location service and the position based routing is twofold. First, we support
the definition and validation of wireless communication protocols and imple-
mentations based thereon. Second, we feel that the abstract computation model
naturally reflects the layering principle of communication architectures in com-
bination with an uncompromisingly local view of the application domain. Thus
we can identify fundamental semantic concepts, such as concurrency, reactivity
and asynchronism, directly with the related concepts as imposed by the given
application context.
AU - Benczúr, András
AU - Glässer, Uwe
AU - Lukovszki, Tamás
ID - 24336
JF - Proc. of 10th International Workshop on Abstract State Machines, LNCS
TI - Formal Description of a Distributed Location Service for Mobile Ad Hoc Networks
ER -
TY - CONF
AU - Grünewald, Matthias
AU - Lukovszki, Tamás
AU - Schindelhauer, Christian
AU - Volbert, Klaus
ID - 24338
SN - 0302-9743
T2 - Proceedings of the 8th International Euro-Par Conference
TI - Distributed Maintenance of Resource Efficient Wireless Network Topologies
ER -
TY - CONF
AU - Volbert, Klaus
ID - 26412
T2 - Proceedings 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing
TI - A simulation environment for ad hoc networks using sector subdivision
ER -
TY - CONF
AU - Brinkmann, André
AU - Salzwedel, Kay
AU - Scheideler, Christian
ID - 2136
T2 - SPAA
TI - Compact, adaptive placement schemes for non-uniform requirements
ER -