2010

Case, John; Kötzing, Timo Solutions to Open Questions for Non-U-Shaped Learning with Memory LimitationsAlgorithmic Learning Theory (ALT) 2010: 285–299
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
A U-shape 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 U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct learning. This paper solves the following two problems regarding non-U-shaped learning posed in the prior literature. First, it is shown that there are classes learnable with three memory states that are not learnable non-U-shapedly with any finite number of memory states. This result is surprising, as for learning with one or two memory states, U-shapes 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 non-U-shapedly 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 U-shapes - in fact, all classes of infinite languages learnable with complete memory are learnable memorylessly with finitely many feedback queries and without U-shapes. 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 U-shapes by any particular bounded number of feedback queries.
@inproceedings{DBLP:conf/alt/CaseK10, abstract = {A U-shape 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 U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct learning. This paper solves the following two problems regarding non-U-shaped learning posed in the prior literature. First, it is shown that there are classes learnable with three memory states that are not learnable non-U-shapedly with any finite number of memory states. This result is surprising, as for learning with one or two memory states, U-shapes 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 non-U-shapedly 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 U-shapes - in fact, all classes of infinite languages learnable with complete memory are learnable memorylessly with finitely many feedback queries and without U-shapes. 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 U-shapes by any particular bounded number of feedback queries.}, author = {Case, John and Kötzing, Timo}, booktitle = {Algorithmic Learning Theory (ALT)}, keywords = {alt imported johncase timokoetzing year2010}, pages = {285-299}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Solutions to Open Questions for Non-U-Shaped Learning with Memory Limitations}, volume = 6331, year = 2010 }

Kötzing, Timo; Neumann, Frank; Röglin, Heiko; Witt, Carsten Theoretical Properties of Two ACO Approaches for the Traveling Salesman ProblemInternational Conference on Swarm Intelligence (ANTS) 2010: 324–335
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@inproceedings{DBLP:conf/antsw/KotzingNRW10, abstract = {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.}, author = {Kötzing, Timo and Neumann, Frank and Röglin, Heiko and Witt, Carsten}, booktitle = {International Conference on Swarm Intelligence (ANTS)}, keywords = {ants carstenwitt frankneumann heikoroeglin imported timokoetzing year2010}, pages = {324-335}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Theoretical Properties of Two ACO Approaches for the Traveling Salesman Problem}, volume = 6234, year = 2010 }

Friedrich, Tobias; Sauerwald, Thomas The Cover Time of Deterministic Random WalksComputing and Combinatorics Conference (COCOON) 2010: 130–139
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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.
@inproceedings{DBLP:conf/cocoon/FriedrichS10, abstract = {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.}, author = {Friedrich, Tobias and Sauerwald, Thomas}, booktitle = {Computing and Combinatorics Conference (COCOON)}, keywords = {cocoon noabstract tobiasfriedrich year2010}, pages = {130-139}, title = {The Cover Time of Deterministic Random Walks}, year = 2010 }

Case, John; Kötzing, Timo Strongly Non-U-Shaped Learning Results by General TechniquesConference On Learning Theory (COLT) 2010: 181–193
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
In learning, a semantic or behavioral U-shape 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 U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct and non-trivial vacillatory learning. Herein we focus more on syntactic U-shapes. This paper introduces two general techniques and applies them especially to syntactic U-shapes 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 so-called self-learning classes of languages which are shown to characterize completely one criterion learning more than another. We apply these techniques to show that, for set-driven and partially set-driven learning, any kind of U-shapes are unnecessary. Furthermore, we show that U-shapes are not unnecessary in a strong way for iterative learning, contrasting an earlier result by Case and Moelius that semantic U-shapes are unnecessary for iterative learning.
@inproceedings{DBLP:conf/colt/CaseK10, abstract = {In learning, a semantic or behavioral U-shape 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 U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct and non-trivial vacillatory learning. Herein we focus more on syntactic U-shapes. This paper introduces two general techniques and applies them especially to syntactic U-shapes 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 so-called self-learning classes of languages which are shown to characterize completely one criterion learning more than another. We apply these techniques to show that, for set-driven and partially set-driven learning, any kind of U-shapes are unnecessary. Furthermore, we show that U-shapes are not unnecessary in a strong way for iterative learning, contrasting an earlier result by Case and Moelius that semantic U-shapes are unnecessary for iterative learning.}, author = {Case, John and Kötzing, Timo}, booktitle = {Conference On Learning Theory (COLT)}, keywords = {colt imported timokoetzing year2010}, pages = {181-193}, publisher = {Omnipress}, title = {Strongly Non-U-Shaped Learning Results by General Techniques}, year = 2010 }

Backes, Michael; Ciobotaru, Oana; Krohmer, Anton RatFish: A File Sharing Protocol Provably Secure against Rational UsersEuropean Symposium on Research in Computer Security (ESORICS) 2010: 607–625
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@inproceedings{DBLP:conf/esorics/BackesCK10, abstract = {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.}, author = {Backes, Michael and Ciobotaru, Oana and Krohmer, Anton}, booktitle = {European Symposium on Research in Computer Security (ESORICS)}, keywords = {antonkrohmer filesharing gametheory security year2010}, pages = {607-625}, title = {RatFish: A File Sharing Protocol Provably Secure against Rational Users}, year = 2010 }

Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, Dorothea Orthogonal Graph Drawing with Flexibility ConstraintsGraph Drawing (GD) 2010: 92–104
[ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
@inproceedings{DBLP:conf/gd/BlasiusKRW10, author = {Bläsius, Thomas and Krug, Marcus and Rutter, Ignaz and Wagner, Dorothea}, booktitle = {Graph Drawing (GD)}, keywords = {gd thomasblaesius year2010}, pages = {92-104}, title = {Orthogonal Graph Drawing with Flexibility Constraints}, year = 2010 }

Berghammer, Rudolf; Friedrich, Tobias; Neumann, Frank Set-based multi-objective optimization, indicators, and deteriorative cyclesGenetic and Evolutionary Computation Conference (GECCO) 2010: 495–502
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Evolutionary multi-objective 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 order-theoretic 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 multi-objective 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 Pareto-dominance relation defined on sets. Later on, we point out in which situations well-known binary and unary indicators can help to avoid this cyclic behavior.
@inproceedings{DBLP:conf/gecco/BerghammerFN10, abstract = {Evolutionary multi-objective 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 order-theoretic 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 multi-objective 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 Pareto-dominance relation defined on sets. Later on, we point out in which situations well-known binary and unary indicators can help to avoid this cyclic behavior.}, author = {Berghammer, Rudolf and Friedrich, Tobias and Neumann, Frank}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {frankneumann gecco imported rudolfberghammer tobiasfriedrich year2010}, pages = {495-502}, publisher = {{ACM}}, title = {Set-based multi-objective optimization, indicators, and deteriorative cycles}, year = 2010 }

Bringmann, Karl; Friedrich, Tobias The maximum hypervolume set yields near-optimal approximationGenetic and Evolutionary Computation Conference (GECCO) 2010: 511–518
Best Paper Award (EMO Track)
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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 near-optimal approximation ratio.
@inproceedings{DBLP:conf/gecco/BringmannF10, abstract = {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 near-optimal approximation ratio.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported tobiasfriedrich year2010}, note = {Best Paper Award (EMO Track)}, pages = {511-518}, title = {The maximum hypervolume set yields near-optimal approximation}, year = 2010 }

Kötzing, Timo; Lehre, Per Kristian; Neumann, Frank; Oliveto, Pietro Simone Ant colony optimization and the minimum cut problemGenetic and Evolutionary Computation Conference (GECCO) 2010: 1393–1400
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@inproceedings{DBLP:conf/gecco/KotzingLNO10, abstract = {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.}, author = {Kötzing, Timo and Lehre, Per Kristian and Neumann, Frank and Oliveto, Pietro Simone}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {frankneumann gecco imported perkristianlehre pietrosimoneoliveto timokoetzing year2010}, pages = {1393-1400}, publisher = {{ACM}}, title = {Ant colony optimization and the minimum cut problem}, year = 2010 }

Voß, Thomas; Friedrich, Tobias; Bringmann, Karl; Igel, Christian Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary studyGenetic and Evolutionary Computation Conference (GECCO) 2010: 1975–1978
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
It is known that the performance of multi-objective evolutionary algorithms (MOEAs) in general deteriorates with increasing number of objectives. For few objectives, MOEAs relying on the contributing hypervolume as (second-level) sorting criterion are the methods of choice. However, the computational complexity of calculating the contributing hypervolume prevents the broad application of these powerful MOEAs to objective functions with many objectives. In this study, we employ the approximation within the steady-state MO-CMA-ES and the SMS-EMOA to empirically investigate whether the Monte-Carlo approximation is indeed useful in practice.
@inproceedings{DBLP:conf/gecco/VossFBI10, abstract = {It is known that the performance of multi-objective evolutionary algorithms (MOEAs) in general deteriorates with increasing number of objectives. For few objectives, MOEAs relying on the contributing hypervolume as (second-level) sorting criterion are the methods of choice. However, the computational complexity of calculating the contributing hypervolume prevents the broad application of these powerful MOEAs to objective functions with many objectives. In this study, we employ the approximation within the steady-state MO-CMA-ES and the SMS-EMOA to empirically investigate whether the Monte-Carlo approximation is indeed useful in practice.}, author = {Voß, Thomas and Friedrich, Tobias and Bringmann, Karl and Igel, Christian}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco noabstract tobiasfriedrich year2010}, pages = {1975-1978}, title = {Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary study}, year = 2010 }

Kasprzik, Anna; Kötzing, Timo String Extension Learning Using LatticesLanguage and Automata Theory and Applications (LATA) 2010: 380–391
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@inproceedings{DBLP:conf/lata/KasprzikK10, abstract = {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.}, author = {Kasprzik, Anna and Kötzing, Timo}, booktitle = {Language and Automata Theory and Applications (LATA)}, keywords = {imported timokoetzing year2010}, pages = {380-391}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {String Extension Learning Using Lattices}, volume = 6031, year = 2010 }

Doerr, Benjamin; Johannsen, Daniel; Kötzing, Timo; Neumann, Frank; Theile, Madeleine More Effective Crossover Operators for the All-Pairs Shortest Path ProblemParallel Problem Solving from Nature (PPSN) 2010: 184–193
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The all-pairs shortest path problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only 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 \(\emph{repair mechanisms}\) and \(\emph{parent 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.
@inproceedings{DBLP:conf/ppsn/DoerrJKNT10, abstract = {The all-pairs shortest path problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only 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 \(\emph{repair mechanisms}\) and \(\emph{parent 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.}, author = {Doerr, Benjamin and Johannsen, Daniel and Kötzing, Timo and Neumann, Frank and Theile, Madeleine}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {benjamindoerr danieljohannsen frankneumann imported madeleinetheile ppsn timokoetzing year2010}, pages = {184-193}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {More Effective Crossover Operators for the All-Pairs Shortest Path Problem}, volume = 6238, year = 2010 }

Bringmann, Karl; Friedrich, Tobias Tight Bounds for the Approximation Ratio of the Hypervolume IndicatorParallel Problem Solving from Nature (PPSN) 2010: 607–616
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The hypervolume indicator is widely used to guide the search and to evaluate the performance of evolutionary multi-objective 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 two-dimensional 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.
@inproceedings{DBLP:conf/ppsn/BringmannF10, abstract = {The hypervolume indicator is widely used to guide the search and to evaluate the performance of evolutionary multi-objective 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 two-dimensional 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.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {PPSN imported tobiasfriedrich year2010}, pages = {607-616}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Tight Bounds for the Approximation Ratio of the Hypervolume Indicator}, volume = 6238, year = 2010 }

Sutton, Andrew M.; Howe, Adele E.; Whitley, L. Darrell Directed Plateau Search for MAX-k-SATSymposium on Combinatorial Search (SOCS) 2010
[ Abstract ] [ BibTeX ] [ Download ]
 
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 hill-climbing local search for MAX-\(k\)-SAT improves its convergence profile.
@inproceedings{DBLP:conf/socs/SuttonHW10, abstract = {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 hill-climbing local search for MAX-\(k\)-SAT improves its convergence profile.}, author = {Sutton, Andrew M. and Howe, Adele E. and Whitley, L. Darrell}, booktitle = {Symposium on Combinatorial Search (SOCS)}, keywords = {andrewmsutton imported socs year2013}, publisher = {{AAAI} Press}, title = {Directed Plateau Search for MAX-k-SAT}, year = 2010 }

Bradonjic, Milan; Elsässer, Robert; Friedrich, Tobias; Sauerwald, Thomas; Stauffer, Alexandre Efficient Broadcast on Random Geometric GraphsSymposium on Discrete Algorithms (SODA) 2010: 1412–1421
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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.
@inproceedings{DBLP:conf/soda/BradonjicEFSS10, abstract = {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.}, author = {Bradonjic, Milan and Elsässer, Robert and Friedrich, Tobias and Sauerwald, Thomas and Stauffer, Alexandre}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {imported soda tobiasfriedrich year2010}, pages = {1412-1421}, title = {Efficient Broadcast on Random Geometric Graphs}, year = 2010 }

Friedrich, Tobias; Gairing, Martin; Sauerwald, Thomas Quasirandom Load BalancingSymposium on Discrete Algorithms (SODA) 2010: 1620–1629
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
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. 121-130] can deviate up to \(\Omega(\text{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. 694-705] 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 first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.
@inproceedings{DBLP:conf/soda/FriedrichGS10, abstract = {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. 121-130] can deviate up to \(\Omega(\text{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. 694-705] 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 first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.}, author = {Friedrich, Tobias and Gairing, Martin and Sauerwald, Thomas}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {imported soda tobiasfriedrich year2010}, pages = {1620-1629}, title = {Quasirandom Load Balancing}, year = 2010 }

Albers, Susanne; Lenzner, Pascal On Approximate Nash Equilibria in Network DesignWeb and Internet Economics (WINE) 2010: 14–25
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study a basic network design game where \($n$\) self-interested agents, each having individual connectivity requirements, wish to build a network by purchasing links from a given set of edges. A fundamental cost sharing mechanism is Shapley cost sharing that splits the cost of an edge in a fair manner among the agents using the edge. In this paper we investigate if an optimal minimum-cost network represents an attractive, relatively stable state that agents might want to purchase. We resort to the concept of \($\alpha$\)-approximate Nash equilibria. We prove that for single source games in undirected graphs, any optimal network represents an \($H(n)$\)-approximate Nash equilibrium, where \($H(n)$\) is the \($n$\)-th Harmonic number. We show that this bound is tight. We extend the results to cooperative games, where agents may form coalitions, and to weighted games. In both cases we give tight or nearly tight lower and upper bounds on the stability of optimal solutions. Finally we show that in general source-sink games and in directed graphs, minimum-cost networks do not represent good states.
@inproceedings{Albers2010, abstract = {We study a basic network design game where $n$ self-interested agents, each having individual connectivity requirements, wish to build a network by purchasing links from a given set of edges. A fundamental cost sharing mechanism is Shapley cost sharing that splits the cost of an edge in a fair manner among the agents using the edge. In this paper we investigate if an optimal minimum-cost network represents an attractive, relatively stable state that agents might want to purchase. We resort to the concept of $\alpha$-approximate Nash equilibria. We prove that for single source games in undirected graphs, any optimal network represents an $H(n)$-approximate Nash equilibrium, where $H(n)$ is the $n$-th Harmonic number. We show that this bound is tight. We extend the results to cooperative games, where agents may form coalitions, and to weighted games. In both cases we give tight or nearly tight lower and upper bounds on the stability of optimal solutions. Finally we show that in general source-sink games and in directed graphs, minimum-cost networks do not represent good states.}, address = {Berlin, Heidelberg}, author = {Albers, Susanne and Lenzner, Pascal}, booktitle = {Web and Internet Economics (WINE)}, editor = {Saberi, Amin}, keywords = {pascallenzner wine year2010}, pages = {14-25}, publisher = {Springer Berlin Heidelberg}, title = {On Approximate Nash Equilibria in Network Design}, type = {Publication}, year = 2010 }

2010

Bringmann, Karl; Friedrich, Tobias Approximating the volume of unions and intersections of high-dimensional geometric objectsComputational Geometry 2010: 601–610
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is #P-hard already for very simple bodies (i.e., axis-parallel boxes), we give a fast FPRAS for all objects where one can: (1) test whether a given point lies inside the object, (2) sample a point uniformly, (3) calculate the volume of the object in polynomial time. All three oracles can be weak, that is, just approximate. This implies that Klee's measure problem and the hypervolume indicator can be approximated efficiently even though they are #P-hard and hence cannot be solved exactly in time polynomial in the number of dimensions unless P=NP. Our algorithm also allows to approximate efficiently the volume of the union of convex bodies given by weak membership oracles. For the analogous problem of the intersection of high-dimensional geometric objects we prove #P-hardness for boxes and show that there is no multiplicative polynomial-time \(2^{d^{1-\epsilon}}\)-approximation for certain boxes unless NP=BPP, but give a simple additive polynomial-time \(\epsilon\)-approximation.
@article{DBLP:journals/comgeo/BringmannF10, abstract = {We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is \#P-hard already for very simple bodies (i.e., axis-parallel boxes), we give a fast FPRAS for all objects where one can: (1) test whether a given point lies inside the object, (2) sample a point uniformly, (3) calculate the volume of the object in polynomial time. All three oracles can be weak, that is, just approximate. This implies that Klee's measure problem and the hypervolume indicator can be approximated efficiently even though they are \#P-hard and hence cannot be solved exactly in time polynomial in the number of dimensions unless P=NP. Our algorithm also allows to approximate efficiently the volume of the union of convex bodies given by weak membership oracles. For the analogous problem of the intersection of high-dimensional geometric objects we prove \#P-hardness for boxes and show that there is no multiplicative polynomial-time \(2^{d^{1-\epsilon}}\)-approximation for certain boxes unless NP=BPP, but give a simple additive polynomial-time \(\epsilon\)-approximation.}, author = {Bringmann, Karl and Friedrich, Tobias}, journal = {Computational Geometry}, keywords = {comgeo imported tobiasfriedrich year2010}, number = {6-7}, pages = {601-610}, title = {Approximating the volume of unions and intersections of high-dimensional geometric objects}, volume = 43, year = 2010 }

Ajwani, Deepak; Friedrich, Tobias Average-case analysis of incremental topological orderingDiscrete Applied Mathematics 2010: 240–250
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of incremental topological ordering algorithms. We prove an expected runtime of \(O(n^2 \operatornamepolylog(n))\) under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (1990) [4], Katriel and Bodlaender (2006) [18], and Pearce and Kelly (2006) [23].
@article{DBLP:journals/dam/AjwaniF10, abstract = {Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of incremental topological ordering algorithms. We prove an expected runtime of \(O(n^2 \operatorname{polylog}(n))\) under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (1990) [4], Katriel and Bodlaender (2006) [18], and Pearce and Kelly (2006) [23].}, author = {Ajwani, Deepak and Friedrich, Tobias}, journal = {Discrete Applied Mathematics}, keywords = {dam imported tobiasfriedrich year2010}, number = 4, pages = {240-250}, title = {Average-case analysis of incremental topological ordering}, volume = 158, year = 2010 }

Friedrich, Tobias; Sauerwald, Thomas The Cover Time of Deterministic Random WalksElectronic Journal of Combinatorics 2010
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
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.
@article{DBLP:journals/combinatorics/FriedrichS10, abstract = {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.}, author = {Friedrich, Tobias and Sauerwald, Thomas}, journal = {Electronic Journal of Combinatorics}, keywords = {ejc imported tobiasfriedrich year2010}, number = 1, title = {The Cover Time of Deterministic Random Walks}, volume = 17, year = 2010 }

Bringmann, Karl; Friedrich, Tobias An Efficient Algorithm for Computing Hypervolume ContributionsEvolutionary Computation 2010: 383–402
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The hypervolume indicator serves as a sorting criterion in many recent multi-objective evolutionary algorithms (MOEAs). Typical algorithms remove the solution with the smallest loss with respect to the dominated hypervolume from the population. We present a new algorithm which determines for a population of size \(n\) with \(d\) objectives, a solution with minimal hypervolume contribution in time \(O(n^{d/2 \log n)\) for \(d > 2\). This improves all previously published algorithms by a factor of \(n\) for all \(d > 3\) and by a factor of \(\sqrt{n}\) for \(d = 3\). We also analyze hypervolume indicator based optimization algorithms which remove \(\lambda > 1\) solutions from a population of size \(n = \mu + \lambda\). We show that there are populations such that the hypervolume contribution of iteratively chosen \(\lambda\) solutions is much larger than the hypervolume contribution of an optimal set of \(\lambda\) solutions. Selecting the optimal set of \(\lambda\) solutions implies calculating \(\binom{n}{\mu}\) conventional hypervolume contributions, which is considered to be computationally too expensive. We present the first hypervolume algorithm which directly calculates the contribution of every set of \(\lambda\) solutions. This gives an additive term of \(\binom{n}{\mu}\) in the runtime of the calculation instead of a multiplicative factor of \(\binom{n}{\mu}\). More precisely, for a population of size \(n\) with \(d\) objectives, our algorithm can calculate a set of \(\lambda\) solutions with minimal hypervolume contribution in time \(O(n^{d/2 \log n + n^\lambda)\) for \(d > 2\). This improves all previously published algorithms by a factor of \(n^{min\{\lambda,d/2\}}\) for \(d > 3\) and by a factor of \(n\) for \(d = 3\).
@article{DBLP:journals/ec/BringmannF10, abstract = {The hypervolume indicator serves as a sorting criterion in many recent multi-objective evolutionary algorithms (MOEAs). Typical algorithms remove the solution with the smallest loss with respect to the dominated hypervolume from the population. We present a new algorithm which determines for a population of size \(n\) with \(d\) objectives, a solution with minimal hypervolume contribution in time \(O(n^{d/2} \log n)\) for \(d > 2\). This improves all previously published algorithms by a factor of \(n\) for all \(d > 3\) and by a factor of \(\sqrt{n}\) for \(d = 3\). We also analyze hypervolume indicator based optimization algorithms which remove \(\lambda > 1\) solutions from a population of size \(n = \mu + \lambda\). We show that there are populations such that the hypervolume contribution of iteratively chosen \(\lambda\) solutions is much larger than the hypervolume contribution of an optimal set of \(\lambda\) solutions. Selecting the optimal set of \(\lambda\) solutions implies calculating \(\binom{n}{\mu}\) conventional hypervolume contributions, which is considered to be computationally too expensive. We present the first hypervolume algorithm which directly calculates the contribution of every set of \(\lambda\) solutions. This gives an additive term of \(\binom{n}{\mu}\) in the runtime of the calculation instead of a multiplicative factor of \(\binom{n}{\mu}\). More precisely, for a population of size \(n\) with \(d\) objectives, our algorithm can calculate a set of \(\lambda\) solutions with minimal hypervolume contribution in time \(O(n^{d/2} \log n + n^\lambda)\) for \(d > 2\). This improves all previously published algorithms by a factor of \(n^{min\{\lambda,d/2\}}\) for \(d > 3\) and by a factor of \(n\) for \(d = 3\).}, author = {Bringmann, Karl and Friedrich, Tobias}, journal = {Evolutionary Computation}, keywords = {EC imported tobiasfriedrich year2010}, number = 3, pages = {383-402}, title = {An Efficient Algorithm for Computing Hypervolume Contributions}, volume = 18, year = 2010 }

Friedrich, Tobias; He, Jun; Hebbinghaus, Nils; Neumann, Frank; Witt, Carsten Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective ModelsEvolutionary Computation 2010: 617–633
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical explorations on this subject. We consider the approximation ability of randomized search heuristics for the class of covering problems and compare single-objective and multi-objective models for such problems. For the VertexCover problem, we point out situations where the multi-objective model leads to a fast construction of optimal solutions while in the single-objective case, no good approximation can be achieved within the expected polynomial time. Examining the more general SetCover problem, we show that optimal solutions can be approximated within a logarithmic factor of the size of the ground set, using the multi-objective approach, while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.
@article{DBLP:journals/ec/FriedrichHHNW10, abstract = {The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical explorations on this subject. We consider the approximation ability of randomized search heuristics for the class of covering problems and compare single-objective and multi-objective models for such problems. For the VertexCover problem, we point out situations where the multi-objective model leads to a fast construction of optimal solutions while in the single-objective case, no good approximation can be achieved within the expected polynomial time. Examining the more general SetCover problem, we show that optimal solutions can be approximated within a logarithmic factor of the size of the ground set, using the multi-objective approach, while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.}, author = {Friedrich, Tobias and He, Jun and Hebbinghaus, Nils and Neumann, Frank and Witt, Carsten}, journal = {Evolutionary Computation}, keywords = {carstenwitt ec frankneumann imported junhe nilshebbinghaus tobiasfriedrich year2010}, number = 4, pages = {617-633}, title = {Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models}, volume = 18, year = 2010 }

Friedrich, Tobias; Neumann, Frank When to use bit-wise neutralityNatural Computing 2010: 283–294
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Representation techniques are important issues when designing successful evolutionary algorithms. Within this field the use of neutrality plays an important role. We examine the use of bit-wise neutrality introduced by Poli and Lopez (2007) from a theoretical point of view and show that this mechanism only enhances mutation-based evolutionary algorithms if not the same number of genotypic bits for each phenotypic bit is used. Using different numbers of genotypic bits for the bits in the phenome we point out by rigorous runtime analyses that it may reduce the optimization time significantly.
@article{DBLP:journals/nc/FriedrichN10, abstract = {Representation techniques are important issues when designing successful evolutionary algorithms. Within this field the use of neutrality plays an important role. We examine the use of bit-wise neutrality introduced by Poli and Lopez (2007) from a theoretical point of view and show that this mechanism only enhances mutation-based evolutionary algorithms if not the same number of genotypic bits for each phenotypic bit is used. Using different numbers of genotypic bits for the bits in the phenome we point out by rigorous runtime analyses that it may reduce the optimization time significantly.}, author = {Friedrich, Tobias and Neumann, Frank}, journal = {Natural Computing}, keywords = {frankneumann nc noabstract tobiasfriedrich year2010}, number = 1, pages = {283-294}, title = {When to use bit-wise neutrality}, volume = 9, year = 2010 }

Cooper, Joshua N.; Doerr, Benjamin; Friedrich, Tobias; Spencer, Joel Deterministic random walks on regular treesRandom Structures and Algorithms 2010: 353–366
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb. Probab. Comput. (2006)) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid \(Z^d\) and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips deviates from the expected number the random walk would have gotten there, by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite \(k\)-ary tree \((k \ge 3)\), we show that for any deviation \(D\) there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least \(D\) more chips than expected in the random walk model. However, to achieve a deviation of \(D\) it is necessary that at least \(k \Theta^{(D)}\) vertices contribute by being occupied by a number of chips not divisible by \(k\) in a certain time interval.
@article{DBLP:journals/rsa/CooperDFS10, abstract = {Jim Propp's rotor router model is a deterministic analogue of a random walk on a graph. Instead of distributing chips randomly, each vertex serves its neighbors in a fixed order. Cooper and Spencer (Comb. Probab. Comput. (2006)) show a remarkable similarity of both models. If an (almost) arbitrary population of chips is placed on the vertices of a grid \(Z^d\) and does a simultaneous walk in the Propp model, then at all times and on each vertex, the number of chips deviates from the expected number the random walk would have gotten there, by at most a constant. This constant is independent of the starting configuration and the order in which each vertex serves its neighbors. This result raises the question if all graphs do have this property. With quite some effort, we are now able to answer this question negatively. For the graph being an infinite \(k\)-ary tree \((k \ge 3)\), we show that for any deviation \(D\) there is an initial configuration of chips such that after running the Propp model for a certain time there is a vertex with at least \(D\) more chips than expected in the random walk model. However, to achieve a deviation of \(D\) it is necessary that at least \(k \Theta^{(D)}\) vertices contribute by being occupied by a number of chips not divisible by \(k\) in a certain time interval.}, author = {Cooper, Joshua N. and Doerr, Benjamin and Friedrich, Tobias and Spencer, Joel}, journal = {Random Structures and Algorithms}, keywords = {imported rsa tobiasfriedrich year2010}, number = 3, pages = {353-366}, title = {Deterministic random walks on regular trees}, volume = 37, year = 2010 }

Friedrich, Tobias; Hebbinghaus, Nils; Neumann, Frank Plateaus can be harder in Multi-Objective OptimizationTheoretical Computer Science 2010: 854–864
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SetCover problem.
@article{DBLP:journals/tcs/FriedrichHN10, abstract = {In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SetCover problem.}, author = {Friedrich, Tobias and Hebbinghaus, Nils and Neumann, Frank}, journal = {Theoretical Computer Science}, keywords = {frankneumann imported nilshebbinghaus tcs tobiasfriedrich year2010}, number = 6, pages = {854-864}, title = {Plateaus can be harder in Multi-Objective Optimization}, volume = 411, year = 2010 }