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 - 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

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 - CHAP AU - Schindlmayr, Arno ED - Blügel, Stefan ED - Brückel, Thomas ED - Schneider, Claus Michael ID - 18608 SN - 1433-5506 T2 - Magnetism goes Nano TI - Magnetic excitations VL - 26 ER - TY - CHAP AU - Eke, Norbert Otto ED - Eke, Norbert Otto ED - Wahrenburg, Fritz ID - 19346 T2 - Vormärz und Exil – Vormärz im Exil. Forum Vormärz Forschung. Jahrbuch 2004 TI - „Wie fern der Heimath! Mein Herz wie schwer!“ Vormärz und Exil – Vormärz im Exil ER - TY - GEN AU - Eke, Norbert Otto ID - 19531 T2 - IASLonline TI - „Gesucht die Lücke im Ablauf“ – nicht gerichtete Utopiekonzepte. (zu: Corinna Mieth: Das Utopische in Literatur und Philosophie. Zur Ästhetik Heiner Müllers und Alexander Kluges. Tübingen: A. Francke 2003) ER - TY - GEN AU - Eke, Norbert Otto ID - 19529 T2 - IASLonline TI - Totgesagte leben länger. (zu: Ingo Breuer: Theatralität und Gedächtnis. Deutschsprachiges Geschichtsdrama seit Brecht. Köln: Böhlau 2004) ER - TY - CONF AB - We present k-Flipper, a graph transformation algorithm that transforms regular undirected graphs. Given a path of k+2 edges it interchanges the end vertices of the path. By definition this operation preserves regularity and connectivity. We show that every regular connected graph can be reached by a series of these operations for all k ¡Ý 1. We use a randomized version, called Random k-Flipper, in order to create random regular connected undirected graphs that may serve as a backbone for peer-to-peer networks. We prove for degree d¡Ê ¦¸(log n) that a series of O(dn) Random k-Flipper operations with k ∈ ¦¨(d2n2 log 1/¦Å) transforms any graph into an expander graph with high probability, i.e. 1-n-¦¨(1). The Random 1-Flipper is symmetric, i.e. the transformation probability from any labeled

The cell structure has two advantages for applying position-based routing: It helps to determine local minima for greedy forwarding and improves recovery from such minima, because for recovery all edges can be used in contrast to other topology-based rules that can be appliedonly on a planar subgraph.

For the analysis of position-based routing algorithms the measures time and traffic are based on the cell structure. The difficulty of exploring the network is expressed by the size of the barriers (i.e. the number of cells in the perimeters). Exploration can be done in parallel, but with increasing traffic. We propose a comparative measure to assess both time and traffic, the combined comparative ratio, which is the maximum of the ratio of routing time and optimal time and the ratio of the traffic and the minimum exploration costs.

While flooding and common single-path strategies have a linear ratio, we present a simple algorithm that has a sub-linear

combined comparative ratio of O(sqrt(h)), where h is the minimal hop distance between source and target. AU - Rührup, S. AU - Schindelhauer, C. ID - 19834 SN - 0769523129 T2 - 19th IEEE International Parallel and Distributed Processing Symposium TI - Competitive Time and Traffic Analysis of Position-Based Routing using a Cell Structure ER - TY - CONF AB - Recent developments both in the business and the technological domain have led to a significant increase in demand for Business Intelligence (BI) infrastructures that can handle huge amounts of data in small time frames. BI applications are increasingly used by large user bases on all management levels; support tasks spanning the complete value chain are based on transactional data and are directly coupled with operational systems in closed loop approaches.

To effectively handle the resulting data volume turns out to be an extremely challenging task which encompasses a variety of issues on different levels. We propose an integrated multi layer tool for monitoring, benchmarking, analyzing, and optimizing the performance of such BI infrastructures.

Inside this paper we give a coarse outline of the tools architecture and demonstrate the value of distinct measurement points at operating system layer. For that purpose we introduce a kernel based benchmark environment and present first measurement results. The gathered data clearly indicates that a meaningful analysis of performance benchmarks without kernel trace points is of limited value - which shows the necessity to consider a separate component within the tools architecture. AU - Brinkmann, André AU - Effert, Sascha AU - Heidebuer, Michael AU - Vodisek, Mario AU - Baars, Henning ID - 19872 T2 - In Proceedings of the International Workshop on Storage Network Architecture and Parallel I/Os TI - An integrated Architecture for Business Intelligence support from Application down to Storage ER - TY - JOUR AU - Meschut, Gerson ID - 21219 JF - Konstruktion SN - ISSN 0947-9333 TI - Mischbauweise sorgt für frischen Wind VL - 04 ER - TY - CONF AU - Redmer, B. AU - Goetz, F. AU - Domik, Gitta ID - 16885 TI - ARIDA - Eine Abstraktion von Eingabegeräten zur Verwendung in augmented Reality Anwendungen, Virtuelle und Erweiterte Realität ER -