Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems - Brauer, Sascha (Lecture Notes in Computer Science)
Metric facility location and K-means are well-known problems of combinatorial optimization. Both admit a fairly simple heuristic called single-swap, which adds, drops or swaps open facilities until it reaches a local optimum. For both problems, it is known that this algorithm produces a solution that is at most a constant factor worse than the respective global optimum. In this paper, we show that single-swap applied to the weighted metric uncapacitated facility location and weighted discrete K-means problem is tightly PLS-complete and hence has exponential worst-case running time.

Policy Dependent and Independent Information Flow Analyses - Töws, Manuel; Wehrheim, Heike (Formal Methods and Software Engineering - 19th International Conference on Formal Engineering Methods (ICFEM 2017))
Information Flow Analysis (IFA) aims at detecting illegal flows of information between program entities. “Legality” is therein specified in terms of various security policies. For the analysis, this opens up two possibilities: building generic, policy independent and building specific, policy dependent IFAs. While the former needs to track all dependencies between program entities, the latter allows for a reduced and thus more efficient analysis. In this paper, we start out by formally defining a policy independent information flow analysis. Next, we show how to specialize this IFA via policy specific variable tracking, and prove soundness of the specialization. We furthermore investigate refinement relationships between policies, allowing an IFA for one policy to be employed for its refinements. As policy refinement depends on concrete program entities, we additionally propose a precomputation of policy refinement conditions, enabling an efficient refinement check for concrete programs.

A Human-Centered Perspective on Software Quality: Acceptance Criteria for Work 4.0 - Fischer, Holger Gerhard; Engler, Michael; Sauer, Stefan (Design, User Experience, and Usability: Theory, Methodology, and Management)

Monitoring of Domain-Related Problems in Distributed Data Streams - Bemmann, Pascal; Biermeier, Felix; Bürmann, Jan; Kemper, Arne; Knollmann, Till; Knorr, Steffen; Kothe, Nils; Mäcker, Alexander; Malatyali, Manuel; Meyer auf der Heide, Friedhelm; Riechers, Sören; Schaefer, Johannes Sebastian; et al. (Structural Information and Communication Complexity)

Simulating Storage Policies for an Automated Grid-Based Warehouse System - Beckschäfer, Michaela; Malberg, Simon; Tierney, Kevin; Weskamp, Christoph (Lecture Notes in Computer Science)

Reducing the Verbosity of Imperative Model Refinements by Using General-Purpose Language Facilities - Gerking, Christopher; Schubert, David; Budde, Ingo (Theory and Practice of Model Transformation)

Population Coding: A New Design Paradigm for Embodied Distributed Systems - Hamann, Heiko; Valentini, Gabriele; Dorigo, Marco (10th Int. Conf. on Swarm Intelligence, ANTS 2016)

Collective Perception of Environmental Features in a Robot Swarm - Valentini, Gabriele; Brambilla, Davide; Hamann, Heiko; Dorigo, Marco (10th Int. Conf. on Swarm Intelligence, ANTS 2016)

Implementing Cryptographic Pairings on Accumulator Based Smart Card Architectures - Günther, Peter; Krummel, Volker (Mathematical Aspects of Computer and Information Sciences)

Theoretical Analysis of the k-Means Algorithm – A Survey - Blömer, Johannes; Lammersen, Christiane; Schmidt, Melanie; Sohler, Christian (Algorithm Engineering)

Adaptive Seeding for Gaussian Mixture Models - Blömer, Johannes; Bujna, Kathrin (Advances in Knowledge Discovery and Data Mining)

Cross-Device Integration of Android Apps - Wolters, Dennis; Kirchhoff, Jonas; Gerth, Christian; Engels, Gregor (Service-Oriented Computing)
Integrating apps on mobile devices into applications running on other devices is usually difficult. For instance, using a messenger on a smartphone to share a text written on a desktop computer often ends up in a cumbersome solution to transfer the text, because many applications are not designed for such scenarios. In this paper, we present an approach enabling the integration of apps running on Android devices into applications running on other devices and even other platforms. This is achieved by specifying adapters for Android apps, which map their services to a platform-independent service interface. For this purpose, we have developed a domain-specific language to ease the specification of such mappings. Our approach is applicable without the need to modify the existing Android apps providing the service. We analyzed its feasibility by implementing our approach and by specifying mappings for several popular Android apps, e.g., phone book, camera, and file explorer.
Keywords: Cross-Device; Integration; Android; Adapter; DSL

Human-Centered Software Engineering as a Chance to Ensure Software Quality Within the Digitization of Human Workflows - Fischer, Holger Gerhard; Senft, Björn (Human-Centered and Error-Resilient Systems Development)

Adaptive Seeding for Gaussian Mixture Models - Blömer, Johannes; Bujna, Kathrin (Advances in Knowledge Discovery and Data Mining)

Tightly-Secure Signatures from Chameleon Hash Functions - Blazy, Olivier; Kakvi, Saqib; Kiltz, Eike; Pan, Jiaxin (Lecture Notes in Computer Science)

AdIDoS – Adaptive and Intelligent Fully-Automatic Detection of Denial-of-Service Weaknesses in Web Services - Altmeier, Christian; Mainka, Christian; Somorovsky, Juraj; Schwenk, Jörg (Data Privacy Management, and Security Assurance - 10th International Workshop, DPM 2015, and 4th International Workshop, QASA 2015)

Practical Invalid Curve Attacks on TLS-ECDH - Jager, Tibor; Schwenk, Jörg; Somorovsky, Juraj (Computer Security -- ESORICS 2015)

ECST – Extended Context-Free Straight-Line Tree Grammars - Böttcher, Stefan; Hartel, Rita; Jacobs, Thomas; Jeromin, Markus (Data Science - 30th British International Conference on Databases, BICOD 2015)

Understanding the Patient 2.0 - Geierhos, Michaela; Bäumer, Frederik S.; Schulze, Sabine; Klotz, Caterina (Modeling and Using Context)

Understanding the Patient 2.0 - Geierhos, Michaela; Bäumer, Frederik S.; Schulze, Sabine; Klotz, Caterina (Modeling and Using Context)

Swarm in a Fly Bottle: Feedback-Based Analysis of Self-organizing Temporary Lock-ins - Hamann, Heiko; Valentini, Gabriele (Ninth Int. Conf. on Swarm Intelligence (ANTS 2014))

Generating EAST-ADL Event Chains from Scenario-Based Requirements Specifications - Koch, Thorsten; Holtmann, Jörg; DeAntoni, Julien (Software Architecture)
Real-time software-intensive embedded systems complexity, as in the automotive domain, requires rigorous Requirements Engineering (RE) approaches. Scenario-based RE formalisms like Modal Sequence Diagrams (MSDs) enable an intuitive specication and the simulative validation of functional requirements. However, the dependencies between events occurring in different MSD scenarios are implicit so that it is difficult to find causes of requirements defects, if any. The automotive architecture description language EAST-ADL addresses this problem by relying on event chains, which make dependencies between events explicit. However, EAST-ADL event chains have a low abstraction level, and their relationship to functional requirements has seldom been investigated. Based on the EAST-ADL functional architecture, we propose to use its central notion of event to conciliate both approaches. We conceived an automatic transformation from the high abstraction level requirements specified in MSDs to the low abstraction level event chains.

Use Your Best Device! Enabling Device Changes at Runtime - Bokermann, Dennis; Gerth, Christian; Engels, Gregor (12th International Conference on Business Process Management (BPM 2014))

Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013

Efficient XML Keyword Search Based on DAG-Compression - Böttcher, Stefan; Hartel, Rita; Rabe, Jonathan (Database and Expert Systems Applications - 25th International Conference, DEXA 2014)

Fast Collisionless Pattern Formation by Anonymous, Position-Aware Robots - Lukovszki, Tamás; Meyer auf der Heide, Friedhelm (Lecture Notes in Computer Science)

Continuous Aggregation in Dynamic Ad-Hoc Networks - Abshoff, Sebastian; Meyer auf der Heide, Friedhelm (Structural Information and Communication Complexity)

Aggregation of Network Protocol Data Near Its Source - Fourné, Marcel; Stegemann, Kevin; Petersen, Dominique; Pohlmann, Norbert (Information and Communication Technology)

Improved Side Channel Attacks on Pairing Based Cryptography - Blömer, Johannes; Günther, Peter; Liske, Gennadij (Constructive Side-Channel Analysis and Secure Design)

A Taxonomy-Based Approach towards NUI Interaction Design - Klompmaker, Florian; Paelke, Volker; Fischer, Holger Gerhard (Distributed, Ambient, and Pervasive Interactions)

Towards a Holistic Tool for the Selection and Validation of Usability Method Sets Supporting Human-Centered Design - Fischer, Holger Gerhard; Strenge, Benjamin; Nebe, Karsten (Design, User Experience, and Usability. Design Philosophy, Methods, and Tools)

Separating Regular Languages by Piecewise Testable and Unambiguous Languages - Place, Thomas; van Rooijen, Lorijn; Zeitoun, Marc (Mathematical Foundations of Computer Science 2013 - 38th International Symposium, (MFCS) 2013, Klosterneuburg, Austria, August 26-30, 2013)

Fast Multi-update Operations on Compressed XML Data - Böttcher, Stefan; Hartel, Rita; Jacobs, Thomas (Big Data - 29th British National Conference on Databases, BNCOD 2013,)

Evaluation of Rendering Algorithms Using Position-Dependent Scene Properties - Jähn, Claudius; Eikel, Benjamin; Fischer, Matthias; Petring, Ralf; Meyer auf der Heide, Friedhelm (Advances in Visual Computing)
In order to evaluate the efficiency of algorithms for real-time 3D rendering, different properties like rendering time, occluded triangles, or image quality, need to be investigated. Since these properties depend on the position of the camera, usually some camera path is chosen, along which the measurements are performed. As those measurements cover only a small part of the scene, this approach hardly allows drawing conclusions regarding the algorithm's properties at arbitrary positions in the scene. The presented method allows the systematic and position-independent evaluation of rendering algorithms. It uses an adaptive sampling approach to approximate the distribution of a property (like rendering time) for all positions in the scene. This approximation can be visualized to produce an intuitive impression of the algorithm's behavior or be statistically analyzed for objectively rating and comparing algorithms. We demonstrate our method by evaluating performance aspects of a known occlusion culling algorithm.

Real-Time 3D Rendering of Heterogeneous Scenes - Petring, Ralf; Eikel, Benjamin; Jähn, Claudius; Fischer, Matthias; Meyer auf der Heide, Friedhelm (Advances in Visual Computing)
Many virtual 3D scenes, especially those that are large, are not structured evenly. For such heterogeneous data, there is no single algorithm that is able to render every scene type at each position fast and with the same high image quality. For a small set of scenes, this situation can be improved if different rendering algorithms are manually assigned to particular parts of the scene by an experienced user. We introduce the Multi-Algorithm-Rendering method. It automatically deploys different rendering algorithms simultaneously for a broad range of scene types. The method divides the scene into subregions and measures the behavior of different algorithms for each region in a preprocessing step. During runtime, this data is utilized to compute an estimate for the quality and running time of the available rendering algorithms from the observer's point of view. By solving an optimizing problem, the image quality can be optimized by an assignment of algorithms to regions while keeping the frame rate almost constant.

Towards Swarm Calculus: Universal Properties of Swarm Performance and Collective Decisions - Hamann, Heiko; Engelbrecht, Andreas; Birattari, Mauro; Dorigo, Marco; Blum, Christian; Stuetzle, Thomas; Christensen, Anders Lyhne; Gross, Roderich (Swarm Intelligence: 8th International Conference, ANTS 2012)

Certifying RSA - Kakvi, Saqib; Kiltz, Eike; May, Alexander (Advances in Cryptology – ASIACRYPT 2012)

Optimal Security Proofs for Full Domain Hash, Revisited - Kakvi, Saqib; Kiltz, Eike (Advances in Cryptology – EUROCRYPT 2012)

Continuous Local Strategies for Robotic Formation Problems - Kempkes, Barbara; Meyer auf der Heide, Friedhelm (Experimental Algorithms)

Local, Self-organizing Strategies for Robotic Formation Problems - Kempkes, Barbara; Meyer auf der Heide, Friedhelm (Algorithms for Sensor Systems)

Newton’s Method and Secant Method for Set-Valued Mappings - Baier, Robert; Molo, Mirko Hessel-von (Large-Scale Scientific Computing)

Bleichenbacher’s Attack Strikes again: Breaking PKCS#1 v1.5 in XML Encryption - Jager, Tibor; Schinzel, Sebastian; Somorovsky, Juraj (Computer Security – ESORICS 2012)

Asynchronous Occlusion Culling on Heterogeneous PC Clusters for Distributed 3D Scenes - Suess, Tim; Koch, Clemens; Jähn, Claudius; Fischer, Matthias; Meyer auf der Heide, Friedhelm (Advances in Visual Computing)
We present a parallel rendering system for heterogeneous PC clusters to visualize massive models. One single, powerful visualization node is supported by a group of backend nodes with weak graphics performance. While the visualization node renders the visible objects, the backend nodes asynchronously perform visibility tests and supply the front end with visible scene objects. The visualization node stores only currently visible objects in its memory, while the scene is distributed among the backend nodes’ memory without redundancy. To efficiently compute the occlusion tests in spite of that each backend node stores only a fraction of the original geometry, we complete the scene by adding highly simplified versions of the objects stored on other nodes. We test our system with 15 backend nodes. It is able to render a ≈ 350,M polygons (≈ 8.5,GiB) large aircraft model with 20, to 30,fps and thus allows a walk-through in real-time.

Evolving for Creativity: Maximizing Complexity in a Self-organized Multi-particle System - Hamann, Heiko; Schmickl, Thomas; Crailsheim, Karl (10th European Conference on Artificial Life (ECAL'09))

Modeling Agents and Agent Systems - Lettmann, Theodor; Baumann, Michael; Eberling, Markus; Kemmerich, Thomas (Transactions on Computational Collective Intelligence V)

Collisionless Gathering of Robots with an Extent - Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; auf der Heide, Friedhelm Meyer; Raupach, Christoph; Swierkot, Kamil; et al. (SOFSEM 2011: Theory and Practice of Computer Science)

A New Approach for Analyzing Convergence Algorithms for Mobile Robots - Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; et al. (Automata, Languages and Programming)

Exploiting New Interaction Techniques for Disaster Control Management Using Multitouch-, Tangible- and Pen-Based-Interaction - Nebe, Karsten; Klompmaker, Florian; Jung, Helge; Fischer, Holger Gerhard (Human-Computer Interaction. Interaction Techniques and Environments.)

A Holistic Model for Integrating Usability Engineering and Software Engineering Enriched with Marketing Activities - Fischer, Holger Gerhard; Nebe, Karsten; Klompmaker, Florian (Human Centered Design)

Collisionless Gathering of Robots with an Extent - Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; et al. (37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011))
Gathering n mobile robots in one single point in the Euclidean plane is a widely studied problem from the area of robot formation problems. Classically, the robots are assumed to have no physical extent, and they are able to share a position with other robots. We drop these assumptions and investigate a similar problem for robots with (a spherical) extent: the goal is to gather the robots as close together as possible. More exactly, we want the robots to form a sphere with minimum radius around a predefined point. We propose an algorithm for this problem which synchronously moves the robots towards the center of the sphere unless they block each other. In this case, if possible, the robots spin around the center of the sphere. We analyze this algorithm experimentally in the plane. If R is the distance of the farthest robot to the center of the sphere, the simulations indicate a runtime which is linear in n and R. Additionally, we prove a theoretic upper bound for the runtime of O(nR) for a discrete version of the problem. Simulations also suggest a runtime of O(n + R) for the discrete version.

Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally - Brandes, Philipp; Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm (Structural Information and Communication Complexity)

Mixing Bottom-Up and Top-Down XPath Query Evaluation - Benter, Markus; Böttcher, Stefan; Hartel, Rita (East European Conference on Advances in Databases and Information Systems)

Updates on Grammar-Compressed XML Data - Bätz, Alexander; Böttcher, Stefan; Hartel, Rita (Advances in Databases - 28th British National Conference on Databases, BNCOD 28, Revised Selected Papers)

TraCX: Transformation of Compressed XML - Böttcher, Stefan; Hartel, Rita; Stey, Sebastian (Advances in Databases - 28th British National Conference on Databases, BNCOD 28, Revised Selected Papers)

A New Approach for Analyzing Convergence Algorithms for Mobile Robots - Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; et al. (Automata, Languages and Programming)
Given a set of n mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. Robots can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement, so that the movement is based on outdated information about other robot's positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [Cohen, Peleg: Convergence properties of gravitational algorithms in asynchronous robot systems], the Center of Gravity is considered as target function, convergence was proven, and the number of rounds needed for halving the diameter of the convex hull of the robot's positions was shown to be O(n^2) and Omega(n). We present an easy-to-check property of target functions that guarantee convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axes aligned minimal box containing all robots. This property holds, e.g., for the above-mentioned target function, and improves the above O(n^2) to an asymptotically optimal O(n) upper bound. Our technique also yields a constant time bound for a target function that requires all robots having identical coordinate axes.

Read-Write-Codes: An Erasure Resilient Encoding System for Flexible Reading and Writing in Storage Networks - Mense, Mario; Schindelhauer, Christian (Proceedings of 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems)
We introduce the Read-Write-Coding-System (RWC) a very flexible class of linear block codes that generate efficient and flexible erasure codes for storage networks. In particular, given a message x of k symbols and a codeword y of n symbols, an RW code defines additional parameters k ≤ r,w ≤ n that offer enhanced possibilities to adjust the fault-tolerance capability of the code. More precisely, an RWC provides linear $\left(n,k,d\right)$-codes that have (a) minimum distance d=n-r+1 for any two codewords, and (b) for each codeword there exists a codeword for each other message with distance of at most w. Furthermore, depending on the values r,w and the code alphabet, different block codes such as parity codes (e.g. RAID 4/5) or Reed-Solomon (RS) codes (if r=k and thus, w=n) can be generated. In storage networks in which I/O accesses are very costly and redundancy is crucial, this flexibility has considerable advantages as r and w can optimally be adapted to read or write intensive applications; only w symbols must be updated if the message x changes completely, what is different from other codes which always need to rewrite y completely as x changes. In this paper, we first state a tight lower bound and basic conditions for all RW codes. Furthermore, we introduce special RW codes in which all mentioned parameters are adjustable even online, that is, those RW codes are adaptive to changing demands. At last, we point out some useful properties regarding safety and security of the stored data.

A Model of Symmetry Breaking in Collective Decision-Making - Hamann, Heiko; Meyer, Bernd; Schmickl, Thomas; Crailsheim, Karl (From Animals to Animats 11)

Robust Undetectable Interference Watermarks - Grza̧ślewicz, Ryszard; Kutyłowski, Jarosław; Kutyłowski, Mirosław; Pietkiewicz, Wojciech (ICCSA'05: Proceedings of the 2005 international conference on Computational Science and Its Applications)

Bregman Clustering for Separable Instances - Ackermann, Marcel R.; Blömer, Johannes (SWAT 2010)

Designing Self-healing in Automotive Systems - Seebach, Hella; Nafz, Florian; Holtmann, Jörg; Meyer, Jan; Tichy, Matthias; Reif, Wolfgang; Schäfer, Wilhelm (Lecture Notes in Computer Science)
Self-healing promises to improve the dependability of systems. In particular safety-critical systems like automotive systems are well suited application, since safe operation is required in these systems even in case of failures. Prerequisite for the improved dependability is the correct realization of the self-healing techniques. Consequently, self-healing activities should be rigorously specified and appropriately integrated with the rest of the system. In this paper, we present an approach for designing self-healing mechanisms in automotive systems. The approach contains a construction model which consist of a structural description as well as an extensive set of constraints. The constraints specify a correct system structure and are also used in the self-healing activities. We exemplify the self-healing approach using the adaptive cruise control system of modern cars.

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing - Briest, Patrick; Chalermsook, Parinya; Khanna, Sanjeev; Laekhanukit, Bundit; Nanongkai, Danupon (Workshop on Internet and Network Economics (WINE))

Preprocessed Global Visibility for Real-Time Rendering on Low-End Hardware - Eikel, Benjamin; Jähn, Claudius; Fischer, Matthias (Advances in Visual Computing)
We present an approach for real-time rendering of complex 3D scenes consisting of millions of polygons on limited graphics hardware. In a preprocessing step, powerful hardware is used to gain fine granular global visibility information of a scene using an adaptive sampling algorithm. Additively the visual influence of each object on the eventual rendered image is estimated. This influence is used to select the most important objects to display in our approximative culling algorithm. After the visibility data is compressed to meet the storage capabilities of small devices, we achieve an interactive walkthrough of the Power Plant scene on a standard netbook with an integrated graphics chipset.

Searchable Compression of Office Documents by XML Schema Subtraction - Böttcher, Stefan; Hartel, Rita; Messinger, Christian (Database and XML Technologies - 7th International XML Database Symposium, XSym 2010)

A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots - Degener, Bastian; Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm (Structural Information and Communication Complexity)

Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II.

Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I.

Towards a Systematic Approach for Capturing Knowledge-Intensive Business Processes - Trier, Matthias; Müller, Claudia (Practical Aspects of Knowledge Management)

Complexity and Approximation of a Geometric Local Robot Assignment Problem - Bonorden, Olaf; Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter (Algorithmic Aspects of Wireless Sensor Networks)
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.

Reinforcement Learning for Blackjack - Kakvi, Saqib (Lecture Notes in Computer Science)

Three-Valued Spotlight Abstractions - Schrieb, Jonas; Wehrheim, Heike; Wonisch, Daniel (FM 2009: Formal Methods)

On Stackelberg Pricing with Computationally Bounded Consumers - Briest, Patrick; Hoefer, Martin; Gualà, Luciano; Ventre, Carmine (Lecture Notes in Computer Science)
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.

Creating Butterflies in the Core – A Network Coding Extension for MPLS/RSVP-TE - Biermann, Thorsten; Schwabe, Arne; Karl, Holger (NETWORKING 2009)

Reinforcement Learning for Blackjack - Kakvi, Saqib (Lecture Notes in Computer Science)

Uniform Budgets and the Envy-Free Pricing Problem - Briest, Patrick (Proceedings of the 35th InternationalColloquium on Automata, Languages and Programming (ICALP))

The Kinetic Facility Location Problem - Degener, Bastian; Gehweiler, Joachim; Lammersen, Christiane (Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT))

Aggregating Robots Compute: An Adaptive Heuristic for the Euclidean Steiner Tree Problem - Hamann, Heiko; Wörn, Heinz (The tenth International Conference on Simulation of Adaptive Behavior (SAB'08))

On Faster Integer Calculations Using Non-arithmetic Primitives - Lürwer-Brüggemeier, Katharina; Ziegler, Martin (Unconventional Computing)

The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces - Bienkowski, Marcin; Kutyłowski, Jarosław (Lecture Notes in Computer Science)
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.

Cryptanalysis of Unbalanced RSA with Small CRT-Exponent - May, Alexander (Advances in Cryptology — CRYPTO 2002)

Low Secret Exponent RSA Revisited - Blömer, Johannes; May, Alexander (Lecture Notes in Computer Science)

Key Revocation with Interval Cover Families - Blömer, Johannes; May, Alexander (Selected Areas in Cryptography)

Dimension Reduction Methods for Convolution Modular Lattices - May, Alexander; Silverman, Joseph H. (Lecture Notes in Computer Science)

A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers - Blömer, Johannes (Algorithms — ESA’ 98)

Competitive Maintenance of Minimum Spanning Trees in Dynamic Graphs - Dynia, Miroslaw; Korzeniowski, Miroslaw; Kutyłowski, Jarosław (Proc. of the 33rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'07))

(Short) Survey of Real Hypercomputation - Ziegler, Martin (Lecture Notes in Computer Science)

Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation - Meer, Klaus; Ziegler, Martin (Mathematical Foundations of Computer Science 2007)

Upper Bounds on the Bisection Width of 3- and 4-Regular Graphs - Monien, Burkhard; Preis, Robert (Mathematical Foundations of Computer Science 2001)

Evaluating XPath Queries on XML Data Streams - Böttcher, Stefan; Steinmetz, Rita (Data Management. Data, Data Everywhere, 24th British National Conference on Databases, BNCOD 24)

Data Management for Mobile Ajax Web 2.0 Applications - Böttcher, Stefan; Steinmetz, Rita (Database and Expert Systems Applications, 18th International Conference, DEXA 2007)

Online Multi-path Routing in a Maze - Rührup, Stefan; Schindelhauer, Christian (Proc. of the 17th International Symposium on Algorithms and Computation (ISAAC 2006))

Reliable Broadcasting Without Collision Detection - Kutyłowski, Jarosław; Zagórski, Filip (SOFSEM 2006: Theory and Practice of Computer Science)
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.

Fault Based Collision Attacks on AES - Blömer, Johannes; Krummel, Volker (Lecture Notes in Computer Science)

Wagner’s Attack on a Secure CRT-RSA Algorithm Reconsidered - Blömer, Johannes; Otto, Martin (Lecture Notes in Computer Science)

Sign Change Fault Attacks on Elliptic Curve Cryptosystems - Blömer, Johannes; Otto, Martin; Seifert, Jean-Pierre (Lecture Notes in Computer Science)

Power-Aware Collective Tree Exploration - Dynia, Miroslaw; Korzeniowski, Miroslaw; Schindelhauer, Christian (Architecture of Computing Systems - ARCS)

Uncomputability Below the Real Halting Problem - Meer, Klaus; Ziegler, Martin (Logical Approaches to Computational Barriers)

De Dictionariis Dynamicis Pauco Spatio Utentibus ({lat.} On Dynamic Dictionaries Using Little Space) - Demaine, Erik D.; Meyer auf der Heide, Friedhelm; Pagh, Rasmus; Pǎtraşcu, Mihai (LATIN 2006: Theoretical Informatics)

Smart Robot Teams Exploring Sparse Trees - Dynia, M.; Kutyłowski, J.; Meyer auf der Heide, Friedhelm; Schindelhauer, Christian (Lecture Notes in Computer Science)

DTD-Driven Structure Preserving XML Compression - Böttcher, Stefan; Steinmetz, Rita (Flexible and Efficient Information Handling, 23rd British National Conference on Databases, BNCOD 23)

Information Disclosure by XPath Queries - Böttcher, Stefan; Steinmetz, Rita (Secure Data Management, Third VLDB Workshop, SDM 2006)