The car sharing problem - Briest, Patrick; Raupach, Christoph (Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11)

Verfahren zur redundanten Datenplatzierung in skalierbaren Speichersystemen - Effert, Sascha

Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing - Kolman, Petr; Scheideler, Christian (28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany)

Approximation Techniques for Utilitarian Mechanism Design - Briest, Patrick; Krysta, Piotr; Vöcking, Berthold (SIAM Journal on Computing)
This paper deals with the design of efficiently computable incentive-compatible mechanisms for combinatorial optimization problems with single-minded agents each possibly having multiple private parameters. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques. Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone fully polynomial time approximation scheme (FPTAS). This can be applied to various problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multiunit auctions. The best previous result for such auctions was a 2-appro-xi-ma-tion. In addition, we present a monotone PTAS for the generalized assignment problem with any constant number of private parameters per agent. The most efficient way to solve packing integer programs (PIPs) is linear programming–based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs), unsplittable flow routing, and multicast routing. Our primal-dual approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle.

Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems - Briest, Patrick; Krysta, Piotr (SIAM Journal on Computing)
We investigate nonparametric multiproduct pricing problems, in which we want to find revenue maximizing prices for products $\mathcal{P}$ based on a set of customer samples $\mathcal{C}$. We mostly focus on the unit-demand case, in which products constitute strict substitutes and each customer aims to purchase a single product. In this setting a customer sample consists of a number of nonzero values for different products and possibly an additional product ranking. Once prices are fixed, each customer chooses to buy one of the products she can afford based on some predefined selection rule. We distinguish between the min-buying, max-buying, and rank-buying models. Some of our results also extend to single-minded pricing, in which case products are strict complements and every customer seeks to buy a single set of products, which she purchases if the sum of prices is below her valuation for that set. For the min-buying model we show that the revenue maximization problem is not approximable within factor $\mathcal{O}(\log^{ε}|\mathcal{C}|)$ for some constant $ε>0$, unless $NP\subseteqDTIME(n^{\mathcal{O}(\log\log n)})$, thereby almost closing the gap between the known algorithmic results and previous lower bounds. We also prove inapproximability within $\mathcal{O}(\ell^{ε})$, $\ell$ being an upper bound on the number of nonzero values per customer, and $\mathcal{O}(|\mathcal{P}|^{ε})$ under slightly stronger assumptions and provide matching upper bounds. Surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined order on the prices of all products, is given. Without the price ladder constraint we obtain similar hardness results for the special case of uniform valuations, i.e., the case that every customer has identical values for all the products she is interested in, assuming specific hardness of the balanced bipartite independent set problem in constant degree graphs or hardness of refuting random 3CNF formulas. Introducing a slightly more general problem definition in which customers are given as an explicit probability distribution, we obtain inapproximability within $\mathcal{O}(|\mathcal{P}|^{ε})$ assuming $NP\nsubseteq\bigcap_{δ>0}BPTIME(2^{\mathcal{O}(n^{δ})})$. These results apply to single-minded pricing as well. For the max-buying model a polynomial-time approximation scheme exists if a price ladder is given. We give a matching lower bound by proving strong NP-hardness. Assuming limited product supply, we analyze a generic local search algorithm and prove that it is 2-approximate. Finally, we discuss implications for the rank-buying model.

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)

Formalisierung von Anforderungen und Betriebssystemeigenschaften zur fruehzeitigen Simulation von eingebetteten, automobilen Systemen - Meyer, Jan; Holtmann, Jörg; Meyer, Matthias (8. Paderborner Workshop Entwurf mechatronischer Systeme)
Durch die immer kuerzer werdenden Entwicklungszyklen und den groeßer werdenden Druck bzgl. Time-to-Market fuer eingebettete Systeme im Automobilsektor steigt der Bedarf, die Systeme bereits zu fruehen Entwicklungszeitpunkten gegenueber den Qualitaetsanforderungen (z. B. Zeitanforderungen und Ressourcenauslastung) zu verifizieren. Wir stellen einen Ansatz vor, der eine formale Spezifikation von Zeitanforderungen und Wirkketten sowie deren fruehzeitige Analyse durch Simulation erlaubt. Verletzungen von Zeitanforderungen werden in den Simulationsergebnissen automatisch erkannt.

A Seamless Model-Based Development Process for Automotive Systems - Holtmann, Jörg; Meyer, Jan; Meyer, Matthias (Software Engineering 2011 – Workshopband (inkl. Doktorandensymposium))
Safety critical functions for embedded systems are increasingly realized with software. Current and future standards and maturity models impose high accuracy and quality for the development process of such software-intensive, embedded systems. But nowadays, there are process and tooling gaps between different modeling aspects for the system under development (SUD). Furthermore, the SUD is usually verified and validated not until it is completely implemented, which leads to expensive corrections. In this paper we present a seamless, model-based development process, which is intended for the automotive supplier domain and conforms to the process reference model of Automotive SPICE. The development process addresses the issues mentioned above by using systematic transitions between different modeling aspects and simulations in early development stages.

Lokale Online-Strategien zur linearen Anordnung von Teilnehmern in einem Peer-to-Peer Netzwerk - Setzer, Alexander