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 -