tr-announce

Download

tr-announce@lists.rwth-aachen.de

December 2005

1 participants
2 discussions

2005-23: Decision Making Based on Approximate and Smoothed Pareto Curves
by Peter Schneider-Kamp 14 Dec '05

14 Dec '05

The following technical report is available from http://aib.informatik.rwth-aachen.de: Decision Making Based on Approximate and Smoothed Pareto Curves Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking AIB 2005-23 We consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the Pareto curve and (ii) the so-called decision maker's approach in which both criteria are combined into a single (usually non-linear) objective function. Previous work by Papadimitriou and Yannakakis showed how to efficiently approximate the Pareto curve for problems like Shortest Path, Spanning Tree, and Perfect Matching}. We wish to determine for which classes of combined objective functions the approximate Pareto curve also yields an approximate solution to the decision maker's problem. We show that an FPTAS for the Pareto curve also gives an FPTAS for the decision maker's problem if the combined objective function is growth bounded like a quasi-polynomial function. If these functions, however, show exponential growth then the decision maker's problem is NP-hard to approximate within any factor. In order to bypass these limitations of approximate decision making, we turn our attention to Pareto curves in the probabilistic framework of smoothed analysis. We show that in a smoothed model, we can efficiently generate the (complete and exact) Pareto curve with a small failure probability if there exists an algorithm for generating the Pareto curve whose worst case running time is pseudopolynomial. This way, we can solve the decision maker's problem w.r.t. any non-decreasing objective function for randomly perturbed instances of, e.g., Shortest Path, Spanning Tree, and Perfect Matching.

1 0

2005-22: Optimal Randomized Fair Exchange with Secret Shared Coins
by Peter Schneider-Kamp 07 Dec '05

07 Dec '05

The following technical report is available from http://aib.informatik.rwth-aachen.de: Optimal Randomized Fair Exchange with Secret Shared Coins Felix Freiling, Maurice Herlihy, Lucia Draque Penso AIB 2005-22 In the fair exchange problem, mutually untrusting parties must securely exchange digital goods. A fair exchange protocol must ensure that no combination of cheating or failures will result in some goods being delivered but not others, and that all goods will be delivered in the absence of cheating and failures. This paper proposes two novel randomized protocols for solving fair exchange using simple trusted units. Both protocols have an optimal expected running time, completing in a constant (3) expected number of rounds. They also have optimal resilience. The first one tolerates any number of dishonest parties, as long as one is honest, while the second one, which assumes more aggressive cheating and failures assumptions, tolerates up to a minority of dishonest parties. The key insight is similar to the idea underlying the code-division multiple access (CDMA) communication protocol: outwitting an adversary is much easier if participants share a common, secret pseudo-random number generator. -- Peter Schneider-Kamp mailto:psk@informatik.rwth-aachen.de LuFG Informatik II http://www-i2.informatik.rwth-aachen.de/~nowonder RWTH Aachen phone: ++49 241 80-21211

1 0