@phdthesis{17413, author = {{Fischer, Matthias}}, isbn = {{3-935433-73-5}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Design, analysis, and evaluation of a data structure for distributed virtual environments}}}, volume = {{164}}, year = {{2005}}, } @article{17414, abstract = {{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 production—the 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 man–machine 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.}}, author = {{Dangelmaier, Wilhelm and Fischer, Matthias and Gausemeier, Jürgen and Grafe, Michael and Matysczok, Carsten and Mueck, Bengt}}, issn = {{0166-3615}}, journal = {{Computers in Industry}}, pages = {{371--383}}, title = {{{Virtual and augmented reality support for discrete manufacturing system simulation}}}, doi = {{10.1016/j.compind.2005.01.007}}, year = {{2005}}, } @inproceedings{17415, author = {{Fischer, Matthias and Mueck, B. and Mahajan, K. and Kortenjan, M. and Laroque, C. and Dangelmaier, W.}}, booktitle = {{Proceedings of the Winter Simulation Conference}}, isbn = {{0780395190}}, title = {{{Multi-User Support and Motion Planning of Humans and Humans Driven Vehicles in Interactive 3D Material Flow Simulations}}}, doi = {{10.1109/wsc.2005.1574470}}, year = {{2005}}, } @article{18763, abstract = {{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.}}, author = {{Czumaj, Artur and Sohler, Christian}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, number = {{3}}, pages = {{580--615}}, title = {{{Abstract Combinatorial Programs and Efficient Property Testers}}}, doi = {{10.1137/s009753970444199x}}, volume = {{34}}, year = {{2005}}, } @inproceedings{18768, author = {{Bădoiu, Mihai and Czumaj, Artur and Indyk, Piotr and Sohler, Christian}}, booktitle = {{Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP)}}, isbn = {{9783540275800}}, issn = {{0302-9743}}, pages = {{866--877}}, title = {{{Facility Location in Sublinear Time}}}, doi = {{10.1007/11523468_70}}, year = {{2005}}, } @inproceedings{18787, abstract = {{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.}}, author = {{Sohler, Christian and Frahling, Gereon}}, booktitle = {{Proceedings of the 37th ACM Symposium on Theory of Computing (STOC)}}, pages = {{209--217}}, title = {{{Coresets in Dynamic Geometric Data Streams}}}, year = {{2005}}, } @article{18790, author = {{Czumaj, Artur and Sohler, Christian}}, issn = {{0304-3975}}, journal = {{Theoretical Computer Science}}, number = {{1}}, pages = {{37--52}}, title = {{{Testing hypergraph colorability}}}, doi = {{10.1016/j.tcs.2004.09.031}}, volume = {{331}}, year = {{2005}}, } @article{18855, abstract = {{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 }}, author = {{Czumaj, Artur and Ergün, Funda and Fortnow, Lance and Magen, Avner and Newman, Ilan and Rubinfeld, Ronitt and Sohler, Christian}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, number = {{1}}, pages = {{91--109}}, title = {{{Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time}}}, doi = {{10.1137/s0097539703435297}}, volume = {{35}}, year = {{2005}}, } @inproceedings{18867, abstract = {{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.}}, author = {{Frahling, Gereon and Krokowski, Jens}}, booktitle = {{Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)}}, isbn = {{9783540291183}}, issn = {{0302-9743}}, pages = {{758--769}}, publisher = {{Springer}}, title = {{{Online Occlusion Culling}}}, doi = {{10.1007/11561071_67}}, volume = {{3669}}, year = {{2005}}, } @inproceedings{18912, abstract = {{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−−√).}}, author = {{Bienkowski, Marcin and Korzeniowski, Miroslaw}}, booktitle = {{Proc. of the European Conference in Parallel Processing (Euro-Par)}}, isbn = {{9783540287001}}, issn = {{0302-9743}}, title = {{{Dynamic Page Migration Under Brownian Motion}}}, doi = {{10.1007/11549468_105}}, year = {{2005}}, } @inproceedings{18915, abstract = {{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.}}, author = {{Bienkowski, Marcin and Byrka, Jarosław}}, booktitle = {{Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)}}, isbn = {{9783540291183}}, issn = {{0302-9743}}, pages = {{815--826}}, publisher = {{Springer }}, title = {{{Bucket Game with Applications to Set Multicover and Dynamic Page Migration}}}, doi = {{10.1007/11561071_72}}, volume = {{3669}}, year = {{2005}}, } @inproceedings{18917, abstract = {{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.}}, author = {{Bienkowski, Marcin}}, booktitle = {{Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005)}}, location = {{Las Vegas, Nevada, USA}}, pages = {{270--278}}, publisher = {{ACM Press, NY, USA}}, title = {{{Dynamic Page Migration with Stochastic Requests}}}, year = {{2005}}, } @inproceedings{18924, abstract = {{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.}}, author = {{Bienkowski, Marcin and Brinkmann, André and Korzeniowski, Miroslaw and Orhan, Orhan}}, booktitle = {{Proceedings of the 4th International Conference on Networking}}, isbn = {{9783540253396}}, issn = {{0302-9743}}, pages = {{413--420}}, publisher = {{Springer}}, title = {{{Cube Connected Cycles Based Bluetooth Scatternet Formation}}}, doi = {{10.1007/978-3-540-31956-6_49}}, volume = {{3420}}, year = {{2005}}, } @inproceedings{18925, abstract = {{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.}}, author = {{Bienkowski, Marcin and Dynia, Miroslaw and Korzeniowski, Miroslaw}}, booktitle = {{Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)}}, isbn = {{9783540249986}}, issn = {{0302-9743}}, pages = {{365--376}}, title = {{{Improved Algorithms for Dynamic Page Migration}}}, doi = {{10.1007/978-3-540-31856-9_30}}, year = {{2005}}, } @phdthesis{18967, author = {{Räcke, Harald}}, isbn = {{3-935433-63-8}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Data Management and Routing in General Networks}}}, volume = {{154}}, year = {{2005}}, } @inproceedings{23883, abstract = {{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.}}, author = {{Frahling, Gereon and Indyk, Piotr and Sohler, Christian}}, booktitle = {{Proceedings of the twenty-first annual symposium on Computational geometry - SCG '05}}, title = {{{Sampling in dynamic data streams and applications}}}, doi = {{10.1145/1064092.1064116}}, year = {{2005}}, } @inbook{17988, author = {{Köhler, Sven and Schindelhauer, Christian and Ziegler, Martin}}, booktitle = {{Fundamentals of Computation Theory}}, isbn = {{9783540281931}}, issn = {{0302-9743}}, title = {{{On Approximating Real-World Halting Problems}}}, doi = {{10.1007/11537311_40}}, year = {{2005}}, } @inbook{17989, author = {{Meer, Klaus and Ziegler, Martin}}, booktitle = {{Fundamentals of Computation Theory}}, isbn = {{9783540281931}}, issn = {{0302-9743}}, title = {{{An Explicit Solution to Post’s Problem over the Reals}}}, doi = {{10.1007/11537311_41}}, year = {{2005}}, } @inproceedings{18280, abstract = {{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.}}, author = {{Ziegler, Martin}}, booktitle = {{Proc. CiE 2005: New Computational Paradigms}}, isbn = {{9783540261797}}, issn = {{0302-9743}}, pages = {{562--571}}, publisher = {{Springer}}, title = {{{Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism}}}, doi = {{10.1007/11494645_68}}, volume = {{3526}}, year = {{2005}}, } @article{18282, author = {{Ziegler, Martin}}, issn = {{0020-7748}}, journal = {{International Journal of Theoretical Physics}}, number = {{11}}, pages = {{2059--2071}}, title = {{{Computational Power of Infinite Quantum Parallelism}}}, doi = {{10.1007/s10773-005-8984-0}}, volume = {{44}}, year = {{2005}}, }