
Albers, Susanne; Lenzner, Pascal On Approximate Nash Equilibria in Network Design. Conference on Web and Internet Economics (WINE) 2010: 1425

Backes, Michael; Ciobotaru, Oana; Krohmer, Anton RatFish: A File Sharing Protocol Provably Secure against Rational Users. European Symposium on Research in Computer Security (ESORICS) 2010: 607625
The proliferation of P2P computing has recently been propelled by popular applications, most notably file sharing protocols such as BitTorrent. These protocols provide remarkable efficiency and scalability, as well as adaptivity to dynamic situations. However, none of them is secure against attacks from rational users, i.e., users that misuse the protocol if doing so increases their benefits (e.g., reduces download time or amount of upload capacity). We propose a rigorous model of rational file sharing for both seeders and leechers, building upon the concept of rational cryptography. We design a novel file sharing protocol called RatFish, and we formally prove that no rational party has an incentive to deviate from RatFish; i.e., RatFish constitutes a Nash equilibrium. Compared to existing file sharing protocols such as BitTorrent, the tracker in RatFish is assigned additional tasks while the communication overhead of a RatFish client is kept to a minimum. We demonstrate by means of a prototype implementation that RatFish is practical and efficient.

Berghammer, Rudolf; Friedrich, Tobias; Neumann, Frank Setbased multiobjective optimization, indicators, and deteriorative cycles. Genetic and Evolutionary Computation Conference (GECCO) 2010: 495502
Evolutionary multiobjective optimization deals with the task of computing a minimal set of search points according to a given set of objective functions. The task has been made explicit in a recent paper by Zitzler et al. [13]. We take an ordertheoretic view on this task and examine how the use of indicator functions can help to direct the search towards Pareto optimal sets. Thereby, we point out that evolutionary algorithms for multiobjective optimization working on the dominance relation of search points have to deal with a cyclic behavior that may lead to worsenings with respect to the Paretodominance relation defined on sets. Later on, we point out in which situations wellknown binary and unary indicators can help to avoid this cyclic behavior.

Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, Dorothea Orthogonal Graph Drawing with Flexibility Constraints. Graph Drawing (GD) 2010: 92104

Bradonjic, Milan; Elsässer, Robert; Friedrich, Tobias; Sauerwald, Thomas; Stauffer, Alexandre Efficient Broadcast on Random Geometric Graphs. Symposium on Discrete Algorithms (SODA) 2010: 14121421
A Random Geometric Graph (RGG) in two dimensions is constructed by distributing \(n\) nodes independently and uniformly at random in \([0, sqrt n]^2\) and creating edges between every pair of nodes having Euclidean distance at most \(r\), for some prescribed \(r\). We analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that with probability \(1  O(n^{1})\) this algorithm informs every node in the largest connected component of an RGG within \(O(sqrt n / r + log n)\) rounds. This holds for any value of \(r\) larger than the critical value for the emergence of a connected component with \(\Omega(n)\) nodes. In order to prove this result, we show that for any two nodes sufficiently distant from each other in \([0, sqrt n]^2\), the length of the shortest path between them in the RGG, when such a path exists, is only a constant factor larger than the optimum. This result has independent interest and, in particular, gives that the diameter of the largest connected component of an RGG is \(\Theta(sqrt n / r\)), which surprisingly has been an open problem so far.

Bringmann, Karl; Friedrich, Tobias Tight Bounds for the Approximation Ratio of the Hypervolume Indicator. Parallel Problem Solving from Nature (PPSN) 2010: 607616
The hypervolume indicator is widely used to guide the search and to evaluate the performance of evolutionary multiobjective optimization algorithms. It measures the volume of the dominated portion of the objective space which is considered to give a good approximation of the Pareto front. There is surprisingly little theoretically known about the quality of this approximation. We examine the multiplicative approximation ratio achieved by twodimensional sets maximizing the hypervolume indicator and prove that it deviates significantly from the optimal approximation ratio. This provable gap is even exponential in the ratio between the largest and the smallest value of the front. We also examine the additive approximation ratio of the hypervolume indicator and prove that it achieves the optimal additive approximation ratio apart from a small factor \(le n/(n  2)\), where \(n\) is the size of the population. Hence the hypervolume indicator can be used to achieve a very good additive but not a good multiplicative approximation of a Pareto front.

Bringmann, Karl; Friedrich, Tobias The maximum hypervolume set yields nearoptimal approximation. Genetic and Evolutionary Computation Conference (GECCO) 2010: 511518
Best Paper Award (EMO Track)
In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multiobjective optimizers use indicator functions to guide the search and to evaluate the performance of search algorithms. The most widely used indicator is the hypervolume indicator. It measures the volume of the dominated portion of the objective space. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator is indeed equivalent to the overall objective of finding a good approximation of the Pareto front. To address this question, we compare the optimal approximation factor with the approximation factor achieved by sets maximizing the hypervolume indicator. We bound the optimal approximation factor of \(n\) points by \(1+\Theta(1/n)\) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation ratio is achieved by sets of \(n\) points that maximize the hypervolume indicator. This shows that the speed of convergence of the approximation ratio achieved by maximizing the hypervolume indicator is asymptotically optimal. This implies that for large values of \(n\), sets maximizing the hypervolume indicator quickly approach the optimal approximation ratio. Moreover, our bounds show that also for relatively small values of \(n\), sets maximizing the hypervolume indicator achieve a nearoptimal approximation ratio.

Case, John; Kötzing, Timo Solutions to Open Questions for NonUShaped Learning with Memory Limitations. Algorithmic Learning Theory (ALT) 2010: 285299
A Ushape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Within the framework of Inductive Inference, previous results have shown, for example, that Ushapes are unnecessary for explanatory learning, but are necessary for behaviorally correct learning. This paper solves the following two problems regarding nonUshaped learning posed in the prior literature. First, it is shown that there are classes learnable with three memory states that are not learnable nonUshapedly with any finite number of memory states. This result is surprising, as for learning with one or two memory states, Ushapes are known to be unnecessary. Secondly, it is shown that there is a class learnable memorylessly with a single feedback query such that this class is not learnable nonUshapedly memorylessly with any finite number of feedback queries. This result is complemented by the result that any class of infinite languages learnable memorylessly with finitely many feedback queries is so learnable without Ushapes  in fact, all classes of infinite languages learnable with complete memory are learnable memorylessly with finitely many feedback queries and without Ushapes. On the other hand, we show that there is a class of infinite languages learnable memorylessly with a single feedback query, which is not learnable without Ushapes by any particular bounded number of feedback queries.

Case, John; Kötzing, Timo Strongly NonUShaped Learning Results by General Techniques. Conference On Learning Theory (COLT) 2010: 181193
In learning, a semantic or behavioral Ushape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept (on the way to success). Within the framework of Inductive Inference, previous results have shown, for example, that such Ushapes are unnecessary for explanatory learning, but are necessary for behaviorally correct and nontrivial vacillatory learning. Herein we focus more on syntactic Ushapes. This paper introduces two general techniques and applies them especially to syntactic Ushapes in learning: one technique to show when they are necessary and one to show when they are unnecessary. The technique for the former is very general and applicable to a much wider range of learning criteria. It employs socalled selflearning classes of languages which are shown to characterize completely one criterion learning more than another. We apply these techniques to show that, for setdriven and partially setdriven learning, any kind of Ushapes are unnecessary. Furthermore, we show that Ushapes are not unnecessary in a strong way for iterative learning, contrasting an earlier result by Case and Moelius that semantic Ushapes are unnecessary for iterative learning.

Doerr, Benjamin; Johannsen, Daniel; Kötzing, Timo; Neumann, Frank; Theile, Madeleine More Effective Crossover Operators for the AllPairs Shortest Path Problem. Parallel Problem Solving from Nature (PPSN) 2010: 184193
The allpairs shortest path problem is the first nonartificial problem for which it was shown that adding crossover can significantly speed up a mutationonly evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time (w.r.t. the number of fitness evaluations) of \(\Theta(n^3.25(log n)^{0.25})\). In contrast to this simple algorithm, evolutionary algorithms used in practice usually employ refined recombination strategies in order to avoid the creation of infeasible offspring. We study extensions of the basic algorithm by two such concepts which are central in recombination, namely \(emphrepair mechanisms}\) and \(emphparent selection}\). We show that repairing infeasible offspring leads to an improved expected optimization time of \(O(n^3.2(log n)^{0.2})\). As a second part of our study we prove that choosing parents that guarantee feasible offspring results in an even better optimization time of \(O(n^3 log n)\). Both results show that already simple adjustments of the recombination operator can asymptotically improve the runtime of evolutionary algorithms.

Friedrich, Tobias; Gairing, Martin; Sauerwald, Thomas Quasirandom Load Balancing. Symposium on Discrete Algorithms (SODA) 2010: 16201629
We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On \(d\)dimensional torus graphs with \(n\) nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121130] can deviate up to \(\Omega(polylog(n))\), and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694705] has a deviation of \(\Omega(n^{1/d})\). This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that firstpassage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.

Friedrich, Tobias; Sauerwald, Thomas The Cover Time of Deterministic Random Walks. Computing and Combinatorics Conference (COCOON) 2010: 130139
The rotor router model is a popular deterministic analogue of a random walk on a graph. Instead of moving to a random neighbor, the neighbors are served in a fixed order. We examine how fast this "deterministic random walk" covers all vertices (or all edges). We present general techniques to derive upper bounds for the vertex and edge cover time and derive matching lower bounds for several important graph classes. Depending on the topology, the deterministic random walk can be asymptotically faster, slower or equally fast compared to the classical random walk.

Kasprzik, Anna; Kötzing, Timo String Extension Learning Using Lattices. Language and Automata Theory and Applications (LATA) 2010: 380391
The class of regular languages is not identifiable from positive data in Gold's language learning model. Many attempts have been made to define interesting classes that are learnable in this model, preferably with the associated learner having certain advantageous properties. Heinz '09 presents a set of language classes called String Extension (Learning) Classes, and shows it to have several desirable properties. In the present paper, we extend the notion of String Extension Classes by basing it on lattices and formally establish further useful properties resulting from this extension. Using lattices enables us to cover a larger range of language classes including the pattern languages, as well as to give various ways of characterizing String Extension Classes and its learners. We believe this paper to show that String Extension Classes are learnable in a very natural way, and thus worthy of further study.

Kötzing, Timo; Lehre, Per Kristian; Neumann, Frank; Oliveto, Pietro Simone Ant colony optimization and the minimum cut problem. Genetic and Evolutionary Computation Conference (GECCO) 2010: 13931400
Ant Colony Optimization (ACO) is a powerful metaheuristic for solving combinatorial optimization problems. With this paper we contribute to the theoretical understanding of this kind of algorithm by investigating the classical minimum cut problem. An ACO algorithm similar to the one that was proved successful for the minimum spanning tree problem is studied. Using rigorous runtime analyses we show how the ACO algorithm behaves similarly to Karger and Stein's algorithm for the minimum cut problem as long as the use of pheromone values is limited. Hence optimal solutions are obtained in expected polynomial time. On the other hand, we show that high use of pheromones has a negative effect, and the ACO algorithm may get trapped in local optima resulting in an exponential runtime to obtain an optimal solution. This result indicates that ACO algorithms may be inappropriate for finding minimum cuts.

Kötzing, Timo; Neumann, Frank; Röglin, Heiko; Witt, Carsten Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem. International Conference on Swarm Intelligence (ANTS) 2010: 324335
Ant colony optimization (ACO) has been widely used for different combinatorial optimization problems. In this paper, we investigate ACO algorithms with respect to their runtime behavior for the traveling salesperson (TSP) problem. We present a new construction graph and show that it has a stronger local property than the given input graph which is often used for constructing solutions. Later on, we investigate ACO algorithms for both construction graphs on random instances and show that they achieve a good approximation in expected polynomial time.

Sutton, Andrew M.; Howe, Adele E.; Whitley, L. Darrell Directed Plateau Search for MAXkSAT. Symposium on Combinatorial Search (SOCS) 2010
Local search algorithms for MAX\(k\)SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau "gradient" function using a Walsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space. This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks. We show that embedding the gradient computation into a hillclimbing local search for MAX\(k\)SAT improves its convergence profile.

Voß, Thomas; Friedrich, Tobias; Bringmann, Karl; Igel, Christian Scaling up indicatorbased MOEAs by approximating the least hypervolume contributor: a preliminary study. Genetic and Evolutionary Computation Conference (GECCO) 2010: 19751978