TY - CHAP
AU - Degener, Bastian
AU - Kempkes, Barbara
AU - Kling, Peter
AU - Meyer auf der Heide, Friedhelm
ID - 16365
SN - 0302-9743
T2 - Structural Information and Communication Complexity
TI - A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots
ER -
TY - BOOK
ED - Abramsky, Samson
ED - Gavoille, Cyril
ED - Kirchner, Claude
ED - Meyer auf der Heide, Friedhelm
ED - Spirakis, Paul G.
ID - 16403
SN - 0302-9743
TI - Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II.
ER -
TY - BOOK
ED - Abramsky, Samson
ED - Gavoille, Cyril
ED - Kirchner, Claude
ED - Meyer auf der Heide, Friedhelm
ED - Spirakis, Paul G.
ID - 16404
SN - 0302-9743
TI - Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I.
ER -
TY - CHAP
AU - Trier, Matthias
AU - Müller, Claudia
ID - 13301
SN - 0302-9743
T2 - Practical Aspects of Knowledge Management
TI - Towards a Systematic Approach for Capturing Knowledge-Intensive Business Processes
ER -
TY - CHAP
AB - We introduce a geometric multi-robot assignment problem. Robots positioned in a Euclidean space have to be assigned to treasures in such a way that their joint strength is sufficient to unearth a treasure with a given weight. The robots have a limited range and thus can only be assigned to treasures in their proximity. The objective is to unearth as many treasures as possible. We investigate the complexity of several variants of this problem and show whether they are in $\classP$ or are $\classNP$-complete. Furthermore, we provide a distributed and local constant-factor approximation algorithm using constant-factor resource augmentation for the two-dimensional setting with $\bigO(\log^*n)$ communication rounds.
AU - Bonorden, Olaf
AU - Degener, Bastian
AU - Kempkes, Barbara
AU - Pietrzyk, Peter
ID - 19724
SN - 0302-9743
T2 - Algorithmic Aspects of Wireless Sensor Networks
TI - Complexity and Approximation of a Geometric Local Robot Assignment Problem
ER -
TY - CHAP
AU - Kakvi, Saqib
ID - 2920
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Reinforcement Learning for Blackjack
ER -
TY - CHAP
AU - Schrieb, Jonas
AU - Wehrheim, Heike
AU - Wonisch, Daniel
ID - 3000
SN - 0302-9743
T2 - FM 2009: Formal Methods
TI - Three-Valued Spotlight Abstractions
ER -
TY - CHAP
AB - In a Stackelberg pricing game a leader aims to set prices on a subset of a given collection of items, such as to maximize her revenue from a follower purchasing a feasible subset of the items. We focus on the case of computationally bounded followers who cannot optimize exactly over the range of all feasible subsets, but apply some publicly known algorithm to determine the set of items to purchase. This corresponds to general multi-dimensional pricing assuming that consumers cannot optimize over the full domain of their valuation functions but still aim to act rationally to the best of their ability.
We consider two versions of this novel type of Stackelberg pricing games. Assuming that items are weighted objects and the follower seeks to purchase a min-cost selection of objects of some minimum weight (the Min-Knapsack problem) and uses a simple greedy 2-approximate algorithm, we show how an extension of the known single-price algorithm can be used to derive a polynomial-time (2 + ε)-approximation algorithm for the leader’s revenue maximization problem based on so-called near-uniform price assignments. We also prove the problem to be strongly NP-hard.
Considering the case that items are subsets of some ground set which the follower seeks to cover (the Set-Cover problem) via a standard primal-dual approach, we prove that near-uniform price assignments fail to yield a good approximation guarantee. However, in the special case of elements with frequency 2 (the Vertex-Cover problem) it turns out that exact revenue maximization can be done in polynomial-time. This stands in sharp contrast to the fact that revenue maximization becomes APX-hard already for elements with frequency 3.
AU - Briest, Patrick
AU - Hoefer, Martin
AU - Gualà, Luciano
AU - Ventre, Carmine
ID - 23744
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - On Stackelberg Pricing with Computationally Bounded Consumers
ER -
TY - CHAP
AU - Biermann, Thorsten
AU - Schwabe, Arne
AU - Karl, Holger
ID - 1830
SN - 0302-9743
T2 - NETWORKING 2009
TI - Creating Butterflies in the Core – A Network Coding Extension for MPLS/RSVP-TE
ER -
TY - CHAP
AU - Kakvi, Saqib
ID - 9616
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Reinforcement Learning for Blackjack
ER -
TY - CONF
AU - Briest, Patrick
ID - 19686
SN - 0302-9743
T2 - Proceedings of the 35th InternationalColloquium on Automata, Languages and Programming (ICALP)
TI - Uniform Budgets and the Envy-Free Pricing Problem
ER -
TY - CONF
AU - Degener, Bastian
AU - Gehweiler, Joachim
AU - Lammersen, Christiane
ID - 19003
SN - 0302-9743
T2 - Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT)
TI - The Kinetic Facility Location Problem
ER -
TY - CONF
AU - Hamann, Heiko
AU - Wörn, Heinz
ID - 20367
SN - 0302-9743
T2 - The tenth International Conference on Simulation of Adaptive Behavior (SAB'08)
TI - Aggregating Robots Compute: An Adaptive Heuristic for the Euclidean Steiner Tree Problem
VL - 5040
ER -
TY - CHAP
AU - Lürwer-Brüggemeier, Katharina
AU - Ziegler, Martin
ID - 17978
SN - 0302-9743
T2 - Unconventional Computing
TI - On Faster Integer Calculations Using Non-arithmetic Primitives
ER -
TY - CONF
AB - We define a natural generalization of the prominent k-server problem, the k-resource problem. It occurs in metric spaces with some demands and resources given at its points. The demands may vary with time, but the total demand may never exceed k. The goal of an online algorithm is to satisfy demands by moving resources, while minimizing the cost for transporting resources. We give an asymptotically optimal O(log(min {n,k}))-competitive randomized algorithm and an O(min {k,n})-competitive deterministic one for the k-resource problem on uniform metric spaces consisting of n points. This extends known results for paging to the more general setting of k-resource.
Basing on the results for uniform metric spaces, we develop a randomized algorithm solving the k-resource and the k-server problem on metric spaces which can be decomposed into components far away from each other. The algorithm achieves a competitive ratio of O(log(min {n,k})), provided that it has some extra resources more than the optimal algorithm.
AU - Bienkowski, Marcin
AU - Kutyłowski, Jarosław
ID - 24276
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces
ER -
TY - CHAP
AU - May, Alexander
ID - 3019
SN - 0302-9743
T2 - Advances in Cryptology — CRYPTO 2002
TI - Cryptanalysis of Unbalanced RSA with Small CRT-Exponent
ER -
TY - CHAP
AU - Blömer, Johannes
AU - May, Alexander
ID - 3020
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Low Secret Exponent RSA Revisited
ER -
TY - CHAP
AU - Blömer, Johannes
AU - May, Alexander
ID - 3021
SN - 0302-9743
T2 - Selected Areas in Cryptography
TI - Key Revocation with Interval Cover Families
ER -
TY - CHAP
AU - May, Alexander
AU - Silverman, Joseph H.
ID - 3022
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Dimension Reduction Methods for Convolution Modular Lattices
ER -
TY - CHAP
AU - Blömer, Johannes
ID - 3026
SN - 0302-9743
T2 - Algorithms — ESA’ 98
TI - A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers
ER -
TY - CONF
AU - Dynia, Miroslaw
AU - Korzeniowski, Miroslaw
AU - Kutyłowski, Jarosław
ID - 18929
SN - 0302-9743
T2 - Proc. of the 33rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'07)
TI - Competitive Maintenance of Minimum Spanning Trees in Dynamic Graphs
VL - 4362
ER -
TY - CHAP
AU - Ziegler, Martin
ID - 17982
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - (Short) Survey of Real Hypercomputation
ER -
TY - CHAP
AU - Meer, Klaus
AU - Ziegler, Martin
ID - 17983
SN - 0302-9743
T2 - Mathematical Foundations of Computer Science 2007
TI - Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation
ER -
TY - CHAP
AU - Monien, Burkhard
AU - Preis, Robert
ID - 16640
SN - 0302-9743
T2 - Mathematical Foundations of Computer Science 2001
TI - Upper Bounds on the Bisection Width of 3- and 4-Regular Graphs
ER -
TY - CONF
AU - Böttcher, Stefan
AU - Steinmetz, Rita
ID - 15144
SN - 0302-9743
T2 - Data Management. Data, Data Everywhere, 24th British National Conference on Databases, BNCOD 24
TI - Evaluating XPath Queries on XML Data Streams
ER -
TY - CONF
AU - Böttcher, Stefan
AU - Steinmetz, Rita
ID - 15146
SN - 0302-9743
T2 - Database and Expert Systems Applications, 18th International Conference, DEXA 2007
TI - Data Management for Mobile Ajax Web 2.0 Applications
ER -
TY - CONF
AU - Rührup, Stefan
AU - Schindelhauer, Christian
ID - 19838
SN - 0302-9743
T2 - Proc. of the 17th International Symposium on Algorithms and Computation (ISAAC 2006)
TI - Online Multi-path Routing in a Maze
ER -
TY - CONF
AB - We propose a dynamic, ad-hoc communication network consisting of mobile units that can warn about traffic jams on motorways.
Our goal is to provide a practical, low cost solution. Therefore we consider very simple wireless communication hardware, without collision detection, with very small bandwidth and a probabilistic model of link failure.
We provide a complete system architecture. For this purpose we design and analyze solutions for size approximation, leader election and broadcasting. Our algorithms are fine-tuned for fast operation in a practical setting. We provide both a theoretical and experimental evaluation of our solutions.
Our contribution is much different from the previous work, where either pure theoretical models with a pure theoretical analysis are provided or algorithms working in practical models are evaluated only through simulations.
AU - Kutyłowski, Jarosław
AU - Zagórski, Filip
ID - 24277
SN - 0302-9743
T2 - SOFSEM 2006: Theory and Practice of Computer Science
TI - Reliable Broadcasting Without Collision Detection
ER -
TY - CHAP
AU - Blömer, Johannes
AU - Krummel, Volker
ID - 3004
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Fault Based Collision Attacks on AES
ER -
TY - CHAP
AU - Blömer, Johannes
AU - Otto, Martin
ID - 3005
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Wagner’s Attack on a Secure CRT-RSA Algorithm Reconsidered
ER -
TY - CHAP
AU - Blömer, Johannes
AU - Otto, Martin
AU - Seifert, Jean-Pierre
ID - 3007
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Sign Change Fault Attacks on Elliptic Curve Cryptosystems
ER -
TY - CONF
AU - Dynia, Miroslaw
AU - Korzeniowski, Miroslaw
AU - Schindelhauer, Christian
ID - 18926
IS - 3894
SN - 0302-9743
T2 - Architecture of Computing Systems - ARCS
TI - Power-Aware Collective Tree Exploration
ER -
TY - CHAP
AU - Meer, Klaus
AU - Ziegler, Martin
ID - 17987
SN - 0302-9743
T2 - Logical Approaches to Computational Barriers
TI - Uncomputability Below the Real Halting Problem
ER -
TY - CHAP
AU - Demaine, Erik D.
AU - Meyer auf der Heide, Friedhelm
AU - Pagh, Rasmus
AU - Pǎtraşcu, Mihai
ID - 16472
SN - 0302-9743
T2 - LATIN 2006: Theoretical Informatics
TI - De Dictionariis Dynamicis Pauco Spatio Utentibus ({lat.} On Dynamic Dictionaries Using Little Space)
ER -
TY - CHAP
AU - Dynia, M.
AU - Kutyłowski, J.
AU - Meyer auf der Heide, Friedhelm
AU - Schindelhauer, Christian
ID - 16473
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Smart Robot Teams Exploring Sparse Trees
ER -
TY - CONF
AU - Böttcher, Stefan
AU - Steinmetz, Rita
ID - 15150
SN - 0302-9743
T2 - Flexible and Efficient Information Handling, 23rd British National Conference on Databases, BNCOD 23
TI - DTD-Driven Structure Preserving XML Compression
ER -
TY - CONF
AU - Böttcher, Stefan
AU - Steinmetz, Rita
ID - 15152
SN - 0302-9743
T2 - Secure Data Management, Third VLDB Workshop, SDM 2006
TI - Information Disclosure by XPath Queries
ER -
TY - CHAP
AB - We establish a link between some heuristic asymptotic formulas (due to Cohen and Lenstra) concerning the moments of the p–part of the class groups of quadratic fields and formulas giving the frequency of the values of the p–rank of these class groups.
AU - Fouvry, Étienne
AU - Klüners, Jürgen
ID - 35958
SN - 0302-9743
T2 - Lecture Notes in Computer Science
TI - Cohen–Lenstra Heuristics of Quadratic Number Fields
ER -
TY - CONF
AB - The Hierarchical Layer Graph (HL graph) is a promising network topology for wireless networks with
variable transmission ranges. It was introduced and analyzed by Meyer auf der Heide et al. 2004.
In this paper we present a distributed, localized and resource-efficient algorithm for constructing this graph. The qualtiy of the HL graph depends on the domination radius and the publication radius, which affect the amount of interference in the network. These parameters also determine whether the HL graph is a c-spanner, which implies an energy-efficient topology. We investigate the performance on randomly distributed node sets and show that the restrictions on these parameters derived from a worst case analysis are not so tight using realistic settings.
Here, we present the results of our extensive experimental evaluation, measuring congestion, dilation and energy. Congestion includes the load that is induced by interfering edges. We distinguish between congestion and realistic congestion where we also take the signal-to-interference ratio into account.
Our experiments show that the HL graph contains energy-efficient paths as well as paths with a few number of hops while preserving a low congestion.
AU - Rührup, Stefan
AU - Schindelhauer, Christian
AU - Volbert, Klaus
ID - 19835
SN - 0302-9743
T2 - Proc. of 4th International Conference on Ad-Hoc, Mobile & Wireless Networks (ADHOC-NOW 2005)
TI - Performance Analysis of the Hierarchical Layer Graph for Wireless Networks
VL - 3738
ER -
TY - CHAP
AU - Schindelhauer, Christian
AU - Voß, Kerstin
ID - 19836
SN - 0302-9743
T2 - Proc. of 4th International Conference on Ad-Hoc Networks & Wireless (ADHOC-NOW 2005)
TI - Probability Distributions for Channel Utilisation
ER -
TY - CONF
AU - Loeser, Chris
AU - Schomaker, Gunnar
AU - Brinkmann, André
AU - Vodisek, Mario
AU - Heidebuer, Michael
ID - 19912
SN - 0302-9743
T2 - Proceedings of the 4th International Conference on Networking
TI - Content Distribution in Heterogenous Video-on-Demand P2P Networks with ARIMA Forecasts
VL - 3421
ER -
TY - CHAP
AU - Blömer, Johannes
AU - May, Alexander
ID - 3006
SN - 0302-9743
T2 - EUROCRYPT 2005
TI - A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers
ER -
TY - CHAP
AU - Ernst, Matthias
AU - Jochemsz, Ellen
AU - May, Alexander
AU - de Weger, Benne
ID - 3010
SN - 0302-9743
T2 - EUROCRYPT 2005
TI - Partial Key Exposure Attacks on RSA up to Full Size Exponents
ER -
TY - CHAP
AU - Rührup, Stefan
AU - Schindelhauer, Christian
ID - 26991
SN - 0302-9743
T2 - Algorithms – ESA 2005
TI - Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio
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 - 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 - 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 -