@phdthesis{18976, abstract = {{Web computing is a variant of parallel computing where the idle times of PCs donated by worldwide distributed users are employed to execute parallel programs. In this thesis we consider a web computing variant with two important properties: First, we support the execution of coupled, massively parallel algorithms (rather than distributed data processing). And second, we organize the system in peer-to-peer fashion. We present the Paderborn University BSP-based Web Computing (PUB-Web) library, which supports the execution of parallel programs in the bulk-synchronous style (BSP) in such a web computing setting. In this thesis, we focus on important technical and algorithmic aspects, in particular: In order to schedule processes with respect to the currently available computing power, which continually changes in an unpredictable fashion, we need intelligent load balancing algorithms and -- as a basic precondition -- the technical ability to migrate threads at runtime. To achieve the latter in a way suitable for production use, compatible with recent Java versions, available for all important platforms, and easy-to-use for developers, we develop the PadMig thread migration and checkpointing library. In order to tackle the distributed load balancing problem, we present an algorithm based on Distributed Heterogeneous Hash-Tables. In order to judge the quality of the schedules produced, we perform extensive experiments to compare several variants of the DHHT-based load balancer with the well- established Work Stealing algorithm, using realistic input data obtained by profiling the utilization of several hundred PCs for a period of several months. Beside the available computing power, we finally also consider the network bandwidth as a secondary criterion for load balancing. For this purpose, we cluster the PUB-Web network according to bandwidth, employing a novel, fault-tolerant, adaptive, and scaling distributed clustering algorithm called DiDiC. In order to judge the quality of the clusterings produces by DiDiC, we experimentally compare it to the well-established MCL algorithm using a simulator.}}, author = {{Gehweiler, Joachim}}, isbn = {{978-3-942647-17-5}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Peer-to-Peer Based Parallel Web Computing}}}, volume = {{298}}, year = {{2011}}, } @inproceedings{19026, author = {{Briest, Patrick and Raupach, Christoph}}, booktitle = {{Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11}}, isbn = {{9781450307437}}, title = {{{The car sharing problem}}}, doi = {{10.1145/1989493.1989518}}, year = {{2011}}, } @phdthesis{19040, author = {{Effert, Sascha}}, title = {{{Verfahren zur redundanten Datenplatzierung in skalierbaren Speichersystemen}}}, year = {{2011}}, } @article{23739, abstract = {{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. }}, author = {{Briest, Patrick and Krysta, Piotr and Vöcking, Berthold}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{1587--1622}}, title = {{{Approximation Techniques for Utilitarian Mechanism Design}}}, doi = {{10.1137/090772988}}, year = {{2011}}, } @article{23740, abstract = {{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^{\varepsilon}|\mathcal{C}|)$ for some constant $\varepsilon>0$, unless $\mathrm{NP}\subseteq\mathrm{DTIME}(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^{\varepsilon})$, $\ell$ being an upper bound on the number of nonzero values per customer, and $\mathcal{O}(|\mathcal{P}|^{\varepsilon})$ 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}|^{\varepsilon})$ assuming $\mathrm{NP}\nsubseteq\bigcap_{\delta>0}\mathrm{BPTIME}(2^{\mathcal{O}(n^{\delta})})$. 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. }}, author = {{Briest, Patrick and Krysta, Piotr}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{1554--1586}}, title = {{{Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems}}}, doi = {{10.1137/090752353}}, year = {{2011}}, } @inbook{20709, author = {{Cord-Landwehr, Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes, Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus and auf der Heide, Friedhelm Meyer and Raupach, Christoph and Swierkot, Kamil and Warner, Daniel and Weddemann, Christoph and Wonisch, Daniel}}, booktitle = {{SOFSEM 2011: Theory and Practice of Computer Science}}, isbn = {{9783642183805}}, issn = {{0302-9743}}, title = {{{Collisionless Gathering of Robots with an Extent}}}, doi = {{10.1007/978-3-642-18381-2_15}}, year = {{2011}}, } @inbook{20710, author = {{Cord-Landwehr, Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes, Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus and Meyer auf der Heide, Friedhelm and Raupach, Christoph and Swierkot, Kamil and Warner, Daniel and Weddemann, Christoph and Wonisch, Daniel}}, booktitle = {{Automata, Languages and Programming}}, isbn = {{9783642220111}}, issn = {{0302-9743}}, title = {{{A New Approach for Analyzing Convergence Algorithms for Mobile Robots}}}, doi = {{10.1007/978-3-642-22012-8_52}}, year = {{2011}}, } @inproceedings{18193, author = {{Renken, Hendrik and Laroque, Christoph and Fischer, Matthias}}, booktitle = {{Proceedings of The 25th European Simulation and Modelling Conference - ESM2011}}, title = {{{An Easy Extendable Modeling Framework for Discrete Event Simulation Models and their Visualization}}}, year = {{2011}}, } @unpublished{18194, abstract = {{We present a parallel rendering system for PC-Clusters to visualize large 3D scenes. One single visualization node, equipped with a high-end graphics adapter, is supported by a group of backend nodes with weak graphics performance. The objects of the scene are distributed among these backend nodes, they serve two purposes: First, they provide an out-of-core memory system for the visualization node. Second, they assist the visualization node's rendering by performing visibility calculations and only sending visible objects to the visualization node. In order to obtain fast rendering with our system, we have to distribute the objects among the backend nodes in a way that does not only guarantee an even distribution of the objects, but also an even distribution of the visibility calculations and the amount of data send to the visualization node. We identify necessary properties of the distribution and argue that a random distribution is a good candidate. Further, in order to reduce the number of objects sent to the visualization node per frame, we employ an approximate hierarchical occlusion culling in each backend node. For this, they are equipped, in addition to the objects assigned to them, with simplified versions of the other objects of the 3D scene. The visualization node is equipped with 512 MiB video memory and supported by 15 backend nodes. This system is able to render a approx. 350 million polygons (approx. 8.5 GiB) large aircraft model between 20 - 30 fps and thus allows a walkthrough in real-time.}}, author = {{Suess, Tim and Koch, Clemens and Jähn, Claudius and Fischer, Matthias and Meyer auf der Heide, Friedhelm}}, title = {{{Parallel Out-of-Core Occlusion Culling}}}, year = {{2011}}, } @inproceedings{18568, author = {{Vöcking, Berthold and Hoefer, Martin and Skopalik, Alexander and Penn, Michal and Polukarov, Maria}}, booktitle = {{{IJCAI} 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence,}}, pages = {{234----239}}, title = {{{Considerate Equilibrium}}}, year = {{2011}}, } @inproceedings{657, abstract = {{We present two distributed, constant factor approximation algorithms for the metric facility location problem. Both algorithms have been designed with a strong emphasis on applicability in the area of wireless sensor networks: in order to execute them, each sensor node only requires limited local knowledge and simple computations. Also, the algorithms can cope with measurement errors and take into account that communication costs between sensor nodes do not necessarily increase linearly with the distance, but can be represented by a polynomial. Since it cannot always be expected that sensor nodes execute algorithms in a synchronized way, our algorithms are executed in an asynchronous model (but they are still able to break symmetry that might occur when two neighboring nodes act at exactly the same time). Furthermore, they can deal with dynamic scenarios: if a node moves, the solution is updated and the update affects only nodes in the local neighborhood. Finally, the algorithms are robust in the sense that incorrect behavior of some nodes during some round will, in the end, still result in a good approximation. The first algorithm runs in expected O(log_{1+\epsilon} n) communication rounds and yields a \my^4(1+4\my^2(1+\epsilon)^{1/p})^p approximation, while the second has a running time of expected O(log^2_{1+\epsilon} n) communication rounds and an approximation factor of \my^4(1 + 2(1 + \epsilon)^{1/p})^p. Here, \epsilon > 0 is an arbitrarily small constant, p the exponent of the polynomial representing the communication costs, and \my the relative measurement error.}}, author = {{Abshoff, Sebastan and Cord-Landwehr, Andreas and Degener, Bastian and Kempkes, Barbara and Pietrzyk, Peter}}, booktitle = {{Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)}}, pages = {{13--27}}, title = {{{Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks}}}, doi = {{10.1007/978-3-642-28209-6_3}}, year = {{2011}}, } @misc{663, author = {{Swierkot, Kamil}}, publisher = {{Universität Paderborn}}, title = {{{Complexity Classes for Local Computation}}}, year = {{2011}}, } @inproceedings{664, abstract = {{Web Computing is a variant of parallel computing where the idle times of PCs donated by worldwide distributed users are employed to execute parallel programs. The PUB-Web library developed by us supports this kind of usage of computing resources. A major problem for the efficient execution of such parallel programs is load balancing. In the Web Computing context, this problem becomes more difficult because of the dynamic behavior of the underlying "parallel computer": the set of available processors (donated PCs) as well as their availability (idle times) change over time in an unpredictable fashion.In this paper, we experimentally evaluate and compare load balancing algorithms in this scenario, namely a variant of the well-established Work Stealing algorithm and strategies based on a heterogeneous version of distributed hash-tables (DHHTs) introduced recently. In order to run a meaningful experimental evaluation, we employ, in addition to our Web Computing library PUB-Web, realistic data sets for the job input streams and for the dynamics of the availability of the resources.Our experimental evaluations suggest that Work Stealing is the better strategy if the number of processes ready to run matches the number of available processors. But a suitable variant of DHHTs outperforms Work Stealing if there are significantly more processes ready to run than available processors.}}, author = {{Gehweiler, Joachim and Kling, Peter and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM)}}, pages = {{31----40}}, title = {{{An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment}}}, doi = {{10.1007/978-3-642-31500-8_4}}, year = {{2011}}, } @proceedings{667, editor = {{Meyer auf der Heide, Friedhelm and Rajaraman, Rajmohan }}, title = {{{23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures}}}, doi = {{10.1145/1989493}}, year = {{2011}}, } @inproceedings{16410, abstract = {{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.}}, author = {{Cord-Landwehr, Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes, Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus and Meyer auf der Heide, Friedhelm and Raupach, Christoph and Swierkot, Kamil and Warner, Daniel and Weddemann, Christoph and Wonisch, Daniel}}, booktitle = {{37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011)}}, isbn = {{9783642183805}}, issn = {{0302-9743}}, number = {{6543}}, pages = {{178--189}}, publisher = {{Springer}}, title = {{{Collisionless Gathering of Robots with an Extent}}}, doi = {{10.1007/978-3-642-18381-2_15}}, year = {{2011}}, } @inbook{16412, author = {{Gehweiler, Joachim and Meyer auf der Heide, Friedhelm}}, booktitle = {{Algorithms Unplugged}}, isbn = {{9783642153273}}, pages = {{367--374}}, title = {{{Bin Packing - How Do I Get My Stuff into the Boxes}}}, doi = {{10.1007/978-3-642-15328-0_38}}, year = {{2011}}, } @inproceedings{16428, author = {{Rajaraman, Rajmohan and Meyer auf der Heide, Friedhelm}}, isbn = {{9781450307437}}, title = {{{Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11}}}, doi = {{10.1145/1989493}}, year = {{2011}}, } @article{16447, author = {{Degener, Bastian and Fekete, Sándor P. and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, issn = {{1574-0137}}, journal = {{Computer Science Review}}, pages = {{57--68}}, title = {{{A survey on relay placement with runtime and approximation guarantees}}}, doi = {{10.1016/j.cosrev.2010.09.005}}, year = {{2011}}, } @inproceedings{16451, author = {{Brandes, Philipp and Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}}, booktitle = {{SIROCCO '11: Proc. of the 18th International Colloquium on Structural Information and Communication Complexity}}, pages = {{138--149}}, title = {{{Energy-efficient strategies for building short chains of mobile robots locally}}}, doi = {{10.1016/j.tcs.2012.10.056}}, year = {{2011}}, } @inproceedings{16453, author = {{Degener, Bastian and Kempkes, Barbara and Langner, Tobias and Meyer auf der Heide, Friedhelm and Pietrzyk, Peter and Wattenhofer, Roger}}, booktitle = {{Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11}}, isbn = {{9781450307437}}, title = {{{A tight runtime bound for synchronous gathering of autonomous robots with limited visibility}}}, doi = {{10.1145/1989493.1989515}}, year = {{2011}}, }