2013

Case, John; Kötzing, Timo Topological Separations in Inductive InferenceAlgorithmic Learning Theory (ALT) 2013: 128–142
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Re learning in the limit from positive data, a major concern is which classes of languages are learnable with respect to a given learning criterion. We are particularly interested herein in the reasons for a class of languages to be unlearnable. We consider two types of reasons. One type is called topological where it does not help if the learners are allowed to be uncomputable (an example of Gold's is that no class containing an infinite language and all its finite sub-languages is learnable - even by an uncomputable learner). Another reason is called computational (where the learners are required to be algorithmic). In particular, two learning criteria might allow for learning different classes of languages from one another - but with dependence on whether the unlearnability is of type topological or computational. In this paper we formalize the idea of two learning criteria separating topologically in learning power. This allows us to study more closely why two learning criteria separate in learning power. For a variety of learning criteria, concerning vacillatory, monotone, (several kinds of) iterative and feedback learning, we show that certain learning criteria separate topologically, and certain others, which are known to separate, are shown not to separate topologically. Showing that learning criteria do not separate topologically implies that any known separation must necessarily exploit algorithmicity of the learner.
@inproceedings{DBLP:conf/alt/CaseK13, abstract = {Re learning in the limit from positive data, a major concern is which classes of languages are learnable with respect to a given learning criterion. We are particularly interested herein in the reasons for a class of languages to be unlearnable. We consider two types of reasons. One type is called topological where it does not help if the learners are allowed to be uncomputable (an example of Gold's is that no class containing an infinite language and all its finite sub-languages is learnable - even by an uncomputable learner). Another reason is called computational (where the learners are required to be algorithmic). In particular, two learning criteria might allow for learning different classes of languages from one another - but with dependence on whether the unlearnability is of type topological or computational. In this paper we formalize the idea of two learning criteria separating topologically in learning power. This allows us to study more closely why two learning criteria separate in learning power. For a variety of learning criteria, concerning vacillatory, monotone, (several kinds of) iterative and feedback learning, we show that certain learning criteria separate topologically, and certain others, which are known to separate, are shown not to separate topologically. Showing that learning criteria do not separate topologically implies that any known separation must necessarily exploit algorithmicity of the learner.}, author = {Case, John and Kötzing, Timo}, booktitle = {Algorithmic Learning Theory (ALT)}, keywords = {imported timokoetzing year2013}, pages = {128-142}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Topological Separations in Inductive Inference}, volume = 8139, year = 2013 }

Wagner, Markus; Friedrich, Tobias Efficient parent selection for Approximation-Guided Evolutionary multi-objective optimizationCongress on Evolutionary Computation (CEC) 2013: 1846–1853
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The Pareto front of a multi-objective optimization problem is typically very large and can only be approximated. Approximation-Guided Evolution (AGE) is a recently presented evolutionary multi-objective optimization algorithm that aims at minimizing iteratively the approximation factor, which measures how well the current population approximates the Pareto front. It outperforms state-of-the-art algorithms for problems with many objectives. However, AGE's performance is not competitive on problems with very few objectives. We study the reason for this behavior and observe that AGE selects parents uniformly at random, which has a detrimental effect on its performance. We then investigate different algorithm-specific selection strategies for AGE. The main difficulty here is finding a computationally efficient selection scheme which does not harm AGEs linear runtime in the number of objectives. We present several improved selections schemes that are computationally efficient and substantially improve AGE on low-dimensional objective spaces, but have no negative effect in high-dimensional objective spaces.
@inproceedings{DBLP:conf/cec/WagnerF13, abstract = {The Pareto front of a multi-objective optimization problem is typically very large and can only be approximated. Approximation-Guided Evolution (AGE) is a recently presented evolutionary multi-objective optimization algorithm that aims at minimizing iteratively the approximation factor, which measures how well the current population approximates the Pareto front. It outperforms state-of-the-art algorithms for problems with many objectives. However, AGE's performance is not competitive on problems with very few objectives. We study the reason for this behavior and observe that AGE selects parents uniformly at random, which has a detrimental effect on its performance. We then investigate different algorithm-specific selection strategies for AGE. The main difficulty here is finding a computationally efficient selection scheme which does not harm AGEs linear runtime in the number of objectives. We present several improved selections schemes that are computationally efficient and substantially improve AGE on low-dimensional objective spaces, but have no negative effect in high-dimensional objective spaces.}, author = {Wagner, Markus and Friedrich, Tobias}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {imported tobiasfriedrich year2013}, pages = {1846-1853}, title = {Efficient parent selection for Approximation-Guided Evolutionary multi-objective optimization}, year = 2013 }

Nallaperuma, Samadhi; Sutton, Andrew M.; Neumann, Frank Fixed-parameter evolutionary algorithms for the Euclidean Traveling Salesperson problemCongress on Evolutionary Computation (CEC) 2013: 2037–2044
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We exploit structural properties related to the optimization process of evolutionary algorithms for this problem and use them to bound the runtime of evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points \(k\) and shows that simple evolutionary algorithms solve the Euclidean TSP in expected time \(O(n^{4k(2k - 1)!)\). Moreover, we show that, under reasonable geometric constraints, a locally optimal 2-opt tour can be found by randomized local search in expected time \(O(n^{2k}!)\).
@inproceedings{DBLP:conf/cec/NallaperumaSN13, abstract = {We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We exploit structural properties related to the optimization process of evolutionary algorithms for this problem and use them to bound the runtime of evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points \(k\) and shows that simple evolutionary algorithms solve the Euclidean TSP in expected time \(O(n^{4k}(2k - 1)!)\). Moreover, we show that, under reasonable geometric constraints, a locally optimal 2-opt tour can be found by randomized local search in expected time \(O(n^{2k}!)\).}, author = {Nallaperuma, Samadhi and Sutton, Andrew M. and Neumann, Frank}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {andrewmsutton cec frankneumann imported samadhinallaperuma year2013}, pages = {2037-2044}, title = {Fixed-parameter evolutionary algorithms for the Euclidean Traveling Salesperson problem}, year = 2013 }

Nallaperuma, Samadhi; Sutton, Andrew M.; Neumann, Frank Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problemCongress on Evolutionary Computation (CEC) 2013: 2045–2052
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We propose a new construction procedure for ant colony optimization (ACO) algorithms working on the Euclidean traveling salesperson problem (TSP) that preserves the ordering on the convex hull of the points in the instance. The procedure is inspired by theoretical analyses for simple evolutionary algorithms that are provably more efficient on instances where the number of inner points of the instance is not too large. We integrate the construction procedure into the well-known MaxMin Ant System (MMAS) and empirically show that it leads to more efficient optimization on instances where the number of inner points is not too high.
@inproceedings{DBLP:conf/cec/NallaperumaSN13a, abstract = {We propose a new construction procedure for ant colony optimization (ACO) algorithms working on the Euclidean traveling salesperson problem (TSP) that preserves the ordering on the convex hull of the points in the instance. The procedure is inspired by theoretical analyses for simple evolutionary algorithms that are provably more efficient on instances where the number of inner points of the instance is not too large. We integrate the construction procedure into the well-known MaxMin Ant System (MMAS) and empirically show that it leads to more efficient optimization on instances where the number of inner points is not too high.}, author = {Nallaperuma, Samadhi and Sutton, Andrew M. and Neumann, Frank}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {andrewmsutton cec frankneumann imported samadhinallaperuma year2013}, pages = {2045-2052}, title = {Parameterized complexity analysis and more effective construction methods for ACO algorithms and the euclidean traveling salesperson problem}, year = 2013 }

Feldmann, Matthias; Kötzing, Timo Optimizing expected path lengths with ant colony optimization using fitness proportional updateFoundations of Genetic Algorithms (FOGA) 2013: 65–74
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We study the behavior of a Max-Min Ant System (MMAS) on the stochastic single-destination shortest path (SDSP) problem. Two previous papers already analyzed this setting for two slightly different MMAS algorithms, where the pheromone update fitness-independently rewards edges of the best-so-far solution. The first paper showed that, when the best-so-far solution is not reevaluated and the stochastic nature of the edge weights is due to noise, the MMAS will find a tree of edges successfully and efficiently identify a shortest path tree with minimal noise-free weights. The second paper used reevaluation of the best-so-far solution and showed that the MMAS finds paths which beat any other path in direct comparisons, if existent. For both results, for some random variables, this corresponds to a tree with minimal expected weights. In this work we analyze a variant of MMAS that works with fitness-proportional update on stochastic-weight graphs with arbitrary random edge weights from \([0,1]\). For \(\delta\) such that any suboptimal path is worse by at least \(\delta\) than an optimal path, then, with suitable parameters, the graph will be optimized after \(O(n^3 ln n/\delta over \delta^3)\) iterations (in expectation). In order to prove the above result, the multiplicative and the variable drift theorem are adapted to continuous search spaces.
@inproceedings{DBLP:conf/foga/FeldmannK13, abstract = {We study the behavior of a Max-Min Ant System (MMAS) on the stochastic single-destination shortest path (SDSP) problem. Two previous papers already analyzed this setting for two slightly different MMAS algorithms, where the pheromone update fitness-independently rewards edges of the best-so-far solution. The first paper showed that, when the best-so-far solution is not reevaluated and the stochastic nature of the edge weights is due to noise, the MMAS will find a tree of edges successfully and efficiently identify a shortest path tree with minimal noise-free weights. The second paper used reevaluation of the best-so-far solution and showed that the MMAS finds paths which beat any other path in direct comparisons, if existent. For both results, for some random variables, this corresponds to a tree with minimal expected weights. In this work we analyze a variant of MMAS that works with fitness-proportional update on stochastic-weight graphs with arbitrary random edge weights from \([0,1]\). For \(\delta\) such that any suboptimal path is worse by at least \(\delta\) than an optimal path, then, with suitable parameters, the graph will be optimized after \(O(n^3 ln n/\delta over \delta^3)\) iterations (in expectation). In order to prove the above result, the multiplicative and the variable drift theorem are adapted to continuous search spaces.}, author = {Feldmann, Matthias and Kötzing, Timo}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {imported timokoetzing year2013}, pages = {65-74}, title = {Optimizing expected path lengths with ant colony optimization using fitness proportional update}, year = 2013 }

Bläsius, Thomas; Karrer, Annette; Rutter, Ignaz Simultaneous Embedding: Edge Orderings, Relative Positions, CutverticesGraph Drawing (GD) 2013: 220–231
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 \cap G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^{\cup} = G ^1 \cup G^2\) , (2) most separating pairs of \(G^{\cup}\), and (3) connected components of \(G\) that are biconnected but not a cycle. Second, we give an \(O(n^3)\)-time algorithm solving Sefe for instances with the following restriction. Let \(u\) be a pole of a \(P\)-node \(\mu\) in the SPQR-tree of a block of \(G^1\) or \(G^2\) . Then at most three virtual edges of \(\mu\) may contain common edges incident to \(u\). All algorithms extend to the sunflower case, i.e., to the case of more than three graphs pairwise intersecting in the same common graph.
@inproceedings{DBLP:conf/gd/BlasiusKR13, abstract = {A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 \cap G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem Sefe). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given Sefe instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^{\cup} = G ^1 \cup G^2\) , (2) most separating pairs of \(G^{\cup}\), and (3) connected components of \(G\) that are biconnected but not a cycle. Second, we give an \(O(n^3)\)-time algorithm solving Sefe for instances with the following restriction. Let \(u\) be a pole of a \(P\)-node \(\mu\) in the SPQR-tree of a block of \(G^1\) or \(G^2\) . Then at most three virtual edges of \(\mu\) may contain common edges incident to \(u\). All algorithms extend to the sunflower case, i.e., to the case of more than three graphs pairwise intersecting in the same common graph.}, author = {Bläsius, Thomas and Karrer, Annette and Rutter, Ignaz}, booktitle = {Graph Drawing (GD)}, keywords = {GD imported thomas thomasblaesius year2013}, pages = {220-231}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices}, volume = 8242, year = 2013 }

Biedl, Therese C.; Bläsius, Thomas; Niedermann, Benjamin; Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph DrawingsGraph Drawing (GD) 2013: 460–471
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We present a simple and versatile formulation of grid-based graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a grid-based representation vertices and edges correspond to axis-parallel boxes on an underlying integer grid; boxes can be further constrained in their shapes and interactions by additional problem-specific constraints. We describe a general \(d\)-dimensional model for grid representation problems. This model can be used to solve a variety of NP-hard graph problems, including pathwidth, bandwidth, optimum st-orientation, area-minimal (bar-k) visibility representation, boxicity-k graphs and others. We implemented SAT-models for all of the above problems and evaluated them on the Rome graphs collection. The experiments show that our model successfully solves NP-hard problems within few minutes on small to medium-size Rome graphs.
@inproceedings{DBLP:conf/gd/BiedlBNNPR13, abstract = {We present a simple and versatile formulation of grid-based graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a grid-based representation vertices and edges correspond to axis-parallel boxes on an underlying integer grid; boxes can be further constrained in their shapes and interactions by additional problem-specific constraints. We describe a general \(d\)-dimensional model for grid representation problems. This model can be used to solve a variety of NP-hard graph problems, including pathwidth, bandwidth, optimum st-orientation, area-minimal (bar-k) visibility representation, boxicity-k graphs and others. We implemented SAT-models for all of the above problems and evaluated them on the Rome graphs collection. The experiments show that our model successfully solves NP-hard problems within few minutes on small to medium-size Rome graphs.}, author = {Biedl, Therese C. and Bläsius, Thomas and Niedermann, Benjamin and Nöllenburg, Martin and Prutkin, Roman and Rutter, Ignaz}, booktitle = {Graph Drawing (GD)}, keywords = {GD imported thomas thomasblaesius year2013}, pages = {460-471}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings}, volume = 8242, year = 2013 }

Benz, Florian; Kötzing, Timo An effective heuristic for the smallest grammar problemGenetic and Evolutionary Computation Conference (GECCO) 2013: 487–494
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The smallest grammar problem is the problem of finding the smallest context-free grammar that generates exactly one given sequence. Approximating the problem with a ratio of less than 8569/8568 is known to be NP-hard. Most work on this problem has focused on finding decent solutions fast (mostly in linear time), rather than on good heuristic algorithms. Inspired by a new perspective on the problem presented by Carrascosa et al. (2010), we investigate the performance of different heuristics on the problem. The aim is to find a good solution on large instances by allowing more than linear time. We propose a hybrid of a max-min ant system and a genetic algorithm that in combination with a novel local search outperforms the state of the art on all files of the Canterbury corpus, a standard benchmark suite. Furthermore, this hybrid performs well on a standard DNA corpus.
@inproceedings{DBLP:conf/gecco/BenzK13, abstract = {The smallest grammar problem is the problem of finding the smallest context-free grammar that generates exactly one given sequence. Approximating the problem with a ratio of less than 8569/8568 is known to be NP-hard. Most work on this problem has focused on finding decent solutions fast (mostly in linear time), rather than on good heuristic algorithms. Inspired by a new perspective on the problem presented by Carrascosa et al.\ (2010), we investigate the performance of different heuristics on the problem. The aim is to find a good solution on large instances by allowing more than linear time. We propose a hybrid of a max-min ant system and a genetic algorithm that in combination with a novel local search outperforms the state of the art on all files of the Canterbury corpus, a standard benchmark suite. Furthermore, this hybrid performs well on a standard DNA corpus.}, author = {Benz, Florian and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported timokoetzing year2013}, pages = {487-494}, publisher = {{ACM}}, title = {An effective heuristic for the smallest grammar problem}, year = 2013 }

Bringmann, Karl; Friedrich, Tobias Parameterized average-case complexity of the hypervolume indicatorGenetic and Evolutionary Computation Conference (GECCO) 2013: 575–582
Nominated for Best Paper Award (EMO Track)
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The hypervolume indicator (HYP) is a popular measure for the quality of a set of \(n\) solutions in \(\mathbb{R}^d\). We discuss its asymptotic worst-case runtimes and several lower bounds depending on different complexity-theoretic assumptions. Assuming that P \(\neq\) NP, there is no algorithm with runtime \(poly(n,d)\). Assuming the exponential time hypothesis, there is no algorithm with runtime \(n^{o(d)}\). In contrast to these worst-case lower bounds, we study the average-case complexity of HYP for points distributed i.i.d. at random on a \(d\)-dimensional simplex. We present a general framework which translates any algorithm for HYP with worst-case runtime \(n^{f(d)}\) to an algorithm with worst-case runtime \(n^{f(d) +1}\) and fixed-parameter-tractable (FPT) average-case runtime. This can be used to show that HYP can be solved in expected time \(O(d^{d^2/2 n + d n^2)\), which implies that HYP is FPT on average while it is W1-hard in the worst-case. For constant dimension \(d\) this gives an algorithm for HYP with runtime \(O(n^2)\) on average. This is the first result proving that HYP is asymptotically easier in the average case. It gives a theoretical explanation why most HYP algorithms perform much better on average than their theoretical worst-case runtime predicts.
@inproceedings{DBLP:conf/gecco/BringmannF13, abstract = {The hypervolume indicator (HYP) is a popular measure for the quality of a set of \(n\) solutions in \(\mathbb{R}^d\). We discuss its asymptotic worst-case runtimes and several lower bounds depending on different complexity-theoretic assumptions. Assuming that P \(\neq\) NP, there is no algorithm with runtime \(poly(n,d)\). Assuming the exponential time hypothesis, there is no algorithm with runtime \(n^{o(d)}\). In contrast to these worst-case lower bounds, we study the average-case complexity of HYP for points distributed i.i.d. at random on a \(d\)-dimensional simplex. We present a general framework which translates any algorithm for HYP with worst-case runtime \(n^{f(d)}\) to an algorithm with worst-case runtime \(n^{f(d) +1}\) and fixed-parameter-tractable (FPT) average-case runtime. This can be used to show that HYP can be solved in expected time \(O(d^{d^2/2} n + d n^2)\), which implies that HYP is FPT on average while it is W1-hard in the worst-case. For constant dimension \(d\) this gives an algorithm for HYP with runtime \(O(n^2)\) on average. This is the first result proving that HYP is asymptotically easier in the average case. It gives a theoretical explanation why most HYP algorithms perform much better on average than their theoretical worst-case runtime predicts.}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco imported tobiasfriedrich year2013}, note = {Nominated for Best Paper Award (EMO Track)}, pages = {575-582}, title = {Parameterized average-case complexity of the hypervolume indicator}, year = 2013 }

Anand, S.; Bringmann, Karl; Friedrich, Tobias; Garg, Naveen; Kumar, Amit Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated MachinesInternational Colloquium on Automata, Languages and Programming (ICALP) 2013: 13–24
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
In this paper we initiate the study of job scheduling on related and unrelated machines so as to minimize the maximum flow time or the maximum weighted flow time (when each job has an associated weight). Previous work for these metrics considered only the setting of parallel machines, while previous work for scheduling on unrelated machines only considered \(L_p, p < \infty\) norms. Our main results are: (1) we give an \(O(\epsilon^{-3})\)-competitive algorithm to minimize maximum weighted flow time on related machines where we assume that the machines of the online algorithm can process \(1+\epsilon\) units of a job in 1 time-unit (\(\epsilon\) speed augmentation). (2) For the objective of minimizing maximum flow time on unrelated machines we give a simple \(2/\epsilon\)-competitive algorithm when we augment the speed by \(\epsilon\). For \(m\) machines we show a lower bound of \(\Omega(m)\) on the competitive ratio if speed augmentation is not permitted. Our algorithm does not assign jobs to machines as soon as they arrive. To justify this "drawback" we show a lower bound of \(\Omega(\log m)\) on the competitive ratio of immediate dispatch algorithms. In both these lower bound constructions we use jobs whose processing times are in \(\{1,\infty\}\), and hence they apply to the more restrictive subset parallel setting. (3) For the objective of minimizing maximum weighted flow time on unrelated machines we establish a lower bound of \(\Omega(\log m)\)-on the competitive ratio of any online algorithm which is permitted to use \(s = O(1)\) speed machines. In our lower bound construction, job j has a processing time of \(p_j\) on a subset of machines and infinity on others and has a weight \(1/p_j\). Hence this lower bound applies to the subset parallel setting for the special case of minimizing maximum stretch.
@inproceedings{DBLP:conf/icalp/0002BFGK13, abstract = {In this paper we initiate the study of job scheduling on related and unrelated machines so as to minimize the maximum flow time or the maximum weighted flow time (when each job has an associated weight). Previous work for these metrics considered only the setting of parallel machines, while previous work for scheduling on unrelated machines only considered \(L_p, p < \infty\) norms. Our main results are: (1) we give an \(O(\epsilon^{-3})\)-competitive algorithm to minimize maximum weighted flow time on related machines where we assume that the machines of the online algorithm can process \(1+\epsilon\) units of a job in 1 time-unit (\(\epsilon\) speed augmentation). (2) For the objective of minimizing maximum flow time on unrelated machines we give a simple \(2/\epsilon\)-competitive algorithm when we augment the speed by \(\epsilon\). For \(m\) machines we show a lower bound of \(\Omega(m)\) on the competitive ratio if speed augmentation is not permitted. Our algorithm does not assign jobs to machines as soon as they arrive. To justify this "drawback" we show a lower bound of \(\Omega(\log m)\) on the competitive ratio of immediate dispatch algorithms. In both these lower bound constructions we use jobs whose processing times are in \(\{1,\infty\}\), and hence they apply to the more restrictive subset parallel setting. (3) For the objective of minimizing maximum weighted flow time on unrelated machines we establish a lower bound of \(\Omega(\log m)\)-on the competitive ratio of any online algorithm which is permitted to use \(s = O(1)\) speed machines. In our lower bound construction, job j has a processing time of \(p_j\) on a subset of machines and infinity on others and has a weight \(1/p_j\). Hence this lower bound applies to the subset parallel setting for the special case of minimizing maximum stretch.}, author = {Anand, S. and Bringmann, Karl and Friedrich, Tobias and Garg, Naveen and Kumar, Amit}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {imported tobiasfriedrich year2013}, pages = {13-24}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines}, volume = 7965, year = 2013 }

Bläsius, Thomas; Rutter, Ignaz; Wagner, Dorothea Optimal Orthogonal Graph Drawing with Convex Bend CostsInternational Colloquium on Automata, Languages, and Programming (ICALP) 2013: 184–195
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph \(G\) on \(n\) vertices with maximum degree 4 (4-planar graph) and for each edge \(e\) a cost function \(cost_e \colon N_0 \rightarrow R\) defining costs depending on the number of bends \(e\) has, compute a planar orthogonal drawing of \(G\) of minimum cost. In this generality OptimalFlexDraw is NP-hard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time \(O(n, cdot, T_flow(n))\) and \(O(n^2, cdot, T_flow(n))\) for biconnected and connected graphs, respectively, where \(T_{flow(n)\) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.
@inproceedings{DBLP:conf/icalp/BlasiusRW13, abstract = {Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph \(G\) on \(n\) vertices with maximum degree 4 (4-planar graph) and for each edge \(e\) a cost function \(cost_e \colon N_0 \rightarrow R\) defining costs depending on the number of bends \(e\) has, compute a planar orthogonal drawing of \(G\) of minimum cost. In this generality OptimalFlexDraw is NP-hard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time \(O(n, \cdot, T_{flow}(n))\) and \(O(n^2, \cdot, T_{flow}(n))\) for biconnected and connected graphs, respectively, where \(T_{flow}(n)\) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.}, author = {Bläsius, Thomas and Rutter, Ignaz and Wagner, Dorothea}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {imported thomas thomasblaesius year2013}, pages = {184-195}, series = {Lecture Notes in Computer Science}, title = {Optimal Orthogonal Graph Drawing with Convex Bend Costs}, volume = 7965, year = 2013 }

Bringmann, Karl; Friedrich, Tobias Exact and Efficient Generation of Geometric Random Variates and Random GraphsInternational Colloquium on Automata, Languages, and Programming (ICALP) 2013: 267–278
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The standard algorithm for fast generation of ErdHo}s-Rényi random graphs only works in the Real RAM model. The critical point is the generation of geometric random variates \(Geo(p)\), for which there is no algorithm that is both exact and efficient in any bounded precision machine model. For a RAM model with word size \(w=\Omega(\log\log(1/p))\), we show that this is possible and present an exact algorithm for sampling \(Geo(p)\) in optimal expected time \(O(1 + \log(1/p) / w)\). We also give an exact algorithm for sampling \(\min\{n, Geo(p)\}\) in optimal expected time \(O(1 + \log(\min\{1/p,n\})/w)\). This yields a new exact algorithm for sampling ErdHo}s-Rényi and Chung-Lu random graphs of \(n\) vertices and \(m\) (expected) edges in optimal expected runtime \(O(n + m)\) on a RAM with word size \(w=\Theta(\log n)\).
@inproceedings{DBLP:conf/icalp/BringmannF13, abstract = {The standard algorithm for fast generation of Erd\H{o}s-Rényi random graphs only works in the Real RAM model. The critical point is the generation of geometric random variates \(Geo(p)\), for which there is no algorithm that is both exact and efficient in any bounded precision machine model. For a RAM model with word size \(w=\Omega(\log\log(1/p))\), we show that this is possible and present an exact algorithm for sampling \(Geo(p)\) in optimal expected time \(O(1 + \log(1/p) / w)\). We also give an exact algorithm for sampling \(\min\{n, Geo(p)\}\) in optimal expected time \(O(1 + \log(\min\{1/p,n\})/w)\). This yields a new exact algorithm for sampling Erd\H{o}s-Rényi and Chung-Lu random graphs of \(n\) vertices and \(m\) (expected) edges in optimal expected runtime \(O(n + m)\) on a RAM with word size \(w=\Theta(\log n)\).}, author = {Bringmann, Karl and Friedrich, Tobias}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {icalp imported tobiasfriedrich year2013}, pages = {267-278}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Exact and Efficient Generation of Geometric Random Variates and Random Graphs}, volume = 7965, year = 2013 }

Freydenberger, Dominik D.; Kötzing, Timo Fast learning of restricted regular expressions and DTDsInternational Conference on Database Theory (ICDT) 2013: 45–56
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We study the problem of generalizing from a finite sample to a language taken from a predefined language class. The two language classes we consider are subsets of the regular languages and have significance in the specification of XML documents (the classes corresponding to so called chain regular expressions, Chares, and to single occurrence regular expressions, Sores). The previous literature gave a number of algorithms for generalizing to Sores providing a trade off between quality of the solution and speed. Furthermore, a fast but non-optimal algorithm for generalizing to Chares is known. For each of the two language classes we give an efficient algorithm returning a minimal generalization from the given finite sample to an element of the fixed language class; such generalizations are called descriptive. In this sense, both our algorithms are optimal.
@inproceedings{DBLP:conf/icdt/FreydenbergerK13, abstract = {We study the problem of generalizing from a finite sample to a language taken from a predefined language class. The two language classes we consider are subsets of the regular languages and have significance in the specification of XML documents (the classes corresponding to so called chain regular expressions, Chares, and to single occurrence regular expressions, Sores). The previous literature gave a number of algorithms for generalizing to Sores providing a trade off between quality of the solution and speed. Furthermore, a fast but non-optimal algorithm for generalizing to Chares is known. For each of the two language classes we give an efficient algorithm returning a minimal generalization from the given finite sample to an element of the fixed language class; such generalizations are called descriptive. In this sense, both our algorithms are optimal.}, author = {Freydenberger, Dominik D. and Kötzing, Timo}, booktitle = {International Conference on Database Theory (ICDT)}, keywords = {imported timokoetzing year2013}, pages = {45-56}, title = {Fast learning of restricted regular expressions and DTDs}, year = 2013 }

Angelini, Patrizio; Bläsius, Thomas; Rutter, Ignaz Testing Mutual Duality of Planar GraphsInternational Symposium on Algorithms and Computation (ISAAC) 2013: 350–360
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We introduce and study the problem Mutual Planar Duality, which asks for planar graphs \(G_1\) and \(G_2\) whether \(G_1\) can be embedded such that its dual is isomorphic to \(G_2\). We show NP-completeness for general graphs and give a linear-time algorithm for biconnected graphs. We consider the common dual relation \(\sim\), where \(G_1 \sim G_2\) if and only they admit embeddings that result in the same dual graph. We show that ~ is an equivalence relation on the set of biconnected graphs and devise a succinct, SPQR-tree-like representation of its equivalence classes. To solve Mutual Planar Duality for biconnected graphs, we show how to do isomorphism testing for two such representations in linear time. A special case of Mutual Planar Duality is testing whether a graph is self-dual. Our algorithm can handle the case of biconnected graphs in linear time and our NP-hardness proof extends to self-duality and also to map self-duality testing (which additionally requires to preserve the embedding).
@inproceedings{DBLP:conf/isaac/AngeliniBR13, abstract = {We introduce and study the problem Mutual Planar Duality, which asks for planar graphs \(G_1\) and \(G_2\) whether \(G_1\) can be embedded such that its dual is isomorphic to \(G_2\). We show NP-completeness for general graphs and give a linear-time algorithm for biconnected graphs. We consider the common dual relation \(\sim\), where \(G_1 \sim G_2\) if and only they admit embeddings that result in the same dual graph. We show that &nbsp; is an equivalence relation on the set of biconnected graphs and devise a succinct, SPQR-tree-like representation of its equivalence classes. To solve Mutual Planar Duality for biconnected graphs, we show how to do isomorphism testing for two such representations in linear time. A special case of Mutual Planar Duality is testing whether a graph is self-dual. Our algorithm can handle the case of biconnected graphs in linear time and our NP-hardness proof extends to self-duality and also to map self-duality testing (which additionally requires to preserve the embedding).}, author = {Angelini, Patrizio and Bläsius, Thomas and Rutter, Ignaz}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {imported thomas thomasblaesius year2013}, pages = {350-360}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Testing Mutual Duality of Planar Graphs}, volume = 8283, year = 2013 }

Cohen, Sarel; Fiat, Amos; Hershcovitch, Moshik; Kaplan, Haim Minimal Indices for Successor Search - (Extended Abstract).Mathematical Foundations of Computer Science (MFCS) 2013: 278–289
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from \( \mathcal{O(n w^4/5 \) bits to \( \mathcal{O(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O(n \log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \( w / \log w \) (compared to the \( w^1/5 \) out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.
@inproceedings{cohen2013minimal, abstract = {We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from \( \mathcal{O}(n w^{4/5} \) bits to \( \mathcal{O}(n \log w) \) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra \( \mathcal{O}(n \log w) \) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of \( \mathcal{O}(n \log w) \) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree \( w / \log w \) (compared to the \( w^{1/5} \) out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.}, author = {Cohen, Sarel and Fiat, Amos and Hershcovitch, Moshik and Kaplan, Haim}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, keywords = {sys:relevantfor:ae amosfiat haimkaplan mfcs moshikhershcovitch sarelcohen year2013}, pages = {278-289}, title = {Minimal Indices for Successor Search - (Extended Abstract).}, year = 2013 }

Bläsius, Thomas; Rutter, Ignaz Simultaneous PQ-Ordering with Applications to Constrained Embedding ProblemsSymposium on Discrete Algorithms (SODA) 2013: 1030–1043
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.
@inproceedings{DBLP:conf/soda/BlasiusR13, abstract = {In this article, we define and study the new problem of SIMULTANEOUS PQ-ORDERING. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. SIMULTANEOUS PQ-ORDERING asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that SIMULTANEOUS PQ-ORDERING is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of SIMULTANEOUS PQ-ORDERING. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for PARTIALLY PQ-CONSTRAINED PLANARITY for biconnected graphs, which asks for a planar embedding in the presence of 16 PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for SIMULTANEOUS EMBEDDING WITH FIXED EDGES for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.}, author = {Bläsius, Thomas and Rutter, Ignaz}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {soda thomasblaesius year2013}, pages = {1030-1043}, title = {Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems}, year = 2013 }

Kawald, Bernd; Lenzner, Pascal On dynamics in selfish network creationSymposium on Parallelism in Algorithms and Architectures (SPAA) 2013: 83–92
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We consider the dynamic behavior of several variants of the Network Creation Game, introduced by Fabrikant et al. [PODC'03]. Equilibrium networks in these models have desirable properties like low social cost and small diameter, which makes them attractive for the decentralized creation of overlay-networks. Unfortunately, due to the non-constructiveness of the Nash equilibrium, no distributed algorithm for finding such networks is known. We treat these games as sequential-move games and analyze if (uncoordinated) selfish play eventually converges to an equilibrium. Thus, we shed light on one of the most natural algorithms for this problem: distributed local search, where in each step some agent performs a myopic selfish improving move. We show that fast convergence is guaranteed for all versions of Swap Games, introduced by Alon et al. [SPAA'10], if the initial network is a tree. Furthermore, we prove that this process can be sped up to an almost optimal number of moves by employing a very natural move policy. Unfortunately, these positive results are no longer true if the initial network has cycles and we show the surprising result that even one non-tree edge suffices to destroy the convergence guarantee. This answers an open problem from Ehsani et al. [SPAA'11] in the negative. Moreover, we show that on non-tree networks no move policy can enforce convergence. We extend our negative results to the well-studied original version, where agents are allowed to buy and delete edges as well. For this model we prove that there is no convergence guarantee - even if all agents play optimally. Even worse, if played on a non-complete host-graph, then there are instances where no sequence of improving moves leads to a stable network. Furthermore, we analyze whether cost-sharing has positive impact on the convergence behavior. For this we consider a version by Corbo and Parkes [PODC'05] where bilateral consent is needed for the creation of an edge and where edge-costs are shared among the involved agents. We show that employing such a cost-sharing rule yields even worse dynamic behavior..
@inproceedings{DBLP:conf/spaa/KawaldL13, abstract = {We consider the dynamic behavior of several variants of the Network Creation Game, introduced by Fabrikant et al. [PODC'03]. Equilibrium networks in these models have desirable properties like low social cost and small diameter, which makes them attractive for the decentralized creation of overlay-networks. Unfortunately, due to the non-constructiveness of the Nash equilibrium, no distributed algorithm for finding such networks is known. We treat these games as sequential-move games and analyze if (uncoordinated) selfish play eventually converges to an equilibrium. Thus, we shed light on one of the most natural algorithms for this problem: distributed local search, where in each step some agent performs a myopic selfish improving move. We show that fast convergence is guaranteed for all versions of Swap Games, introduced by Alon et al. [SPAA'10], if the initial network is a tree. Furthermore, we prove that this process can be sped up to an almost optimal number of moves by employing a very natural move policy. Unfortunately, these positive results are no longer true if the initial network has cycles and we show the surprising result that even one non-tree edge suffices to destroy the convergence guarantee. This answers an open problem from Ehsani et al. [SPAA'11] in the negative. Moreover, we show that on non-tree networks no move policy can enforce convergence. We extend our negative results to the well-studied original version, where agents are allowed to buy and delete edges as well. For this model we prove that there is no convergence guarantee - even if all agents play optimally. Even worse, if played on a non-complete host-graph, then there are instances where no sequence of improving moves leads to a stable network. Furthermore, we analyze whether cost-sharing has positive impact on the convergence behavior. For this we consider a version by Corbo and Parkes [PODC'05] where bilateral consent is needed for the creation of an edge and where edge-costs are shared among the involved agents. We show that employing such a cost-sharing rule yields even worse dynamic behavior..}, author = {Kawald, Bernd and Lenzner, Pascal}, booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, keywords = {imported pascallenzner spaa year2013}, pages = {83-92}, title = {On dynamics in selfish network creation}, year = 2013 }

Croitoru, Cosmina; Kötzing, Timo A Normal Form for Argumentation FrameworksTheorie and Applications of Formal Argumentation (TAFA) 2013: 32–45
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We study formal argumentation frameworks as introduced by Dung (1995). We show that any such argumentation framework can be syntactically augmented into a normal form (having a simplified attack relation), preserving the semantic properties of original arguments. An argumentation framework is in normal form if no argument attacks a conflicting pair of arguments. An augmentation of an argumentation framework is obtained by adding new arguments and changing the attack relation such that the acceptability status of original arguments is maintained in the new framework. Furthermore, we define join-normal semantics leading to augmentations of the joined argumentation frameworks. Also, a rewriting technique which transforms in cubic time a given argumentation framework into a normal form is devised.
@inproceedings{DBLP:conf/tafa/CroitoruK13, abstract = {We study formal argumentation frameworks as introduced by Dung (1995). We show that any such argumentation framework can be syntactically augmented into a normal form (having a simplified attack relation), preserving the semantic properties of original arguments. An argumentation framework is in normal form if no argument attacks a conflicting pair of arguments. An augmentation of an argumentation framework is obtained by adding new arguments and changing the attack relation such that the acceptability status of original arguments is maintained in the new framework. Furthermore, we define join-normal semantics leading to augmentations of the joined argumentation frameworks. Also, a rewriting technique which transforms in cubic time a given argumentation framework into a normal form is devised.}, author = {Croitoru, Cosmina and Kötzing, Timo}, booktitle = {Theorie and Applications of Formal Argumentation (TAFA)}, keywords = {imported tafa timokoetzing year2013}, pages = {32-45}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {A Normal Form for Argumentation Frameworks}, volume = 8306, year = 2013 }

Bailly, Gilles; Oulasvirta, Antti; Kötzing, Timo; Hoppe, Sabrina MenuOptimizer: interactive optimization of menu systemsUser Interface Software and Technology (UIST) 2013: 331–342
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Menu systems are challenging to design because design spaces are immense, and several human factors affect user behavior. This paper contributes to the design of menus with the goal of interactively assisting designers with an optimizer in the loop. To reach this goal, 1) we extend a predictive model of user performance to account for expectations as to item groupings; 2) we adapt an ant colony optimizer that has been proven efficient for this class of problems; and 3) we present MenuOptimizer, a set of inter-actions integrated into a real interface design tool (QtDesigner). MenuOptimizer supports designers' abilities to cope with uncertainty and recognize good solutions. It allows designers to delegate combinatorial problems to the optimizer, which should solve them quickly enough without disrupting the design process. We show evidence that satisfactory menu designs can be produced for complex problems in minutes.
@inproceedings{DBLP:conf/uist/BaillyOKH13, abstract = {Menu systems are challenging to design because design spaces are immense, and several human factors affect user behavior. This paper contributes to the design of menus with the goal of interactively assisting designers with an optimizer in the loop. To reach this goal, 1) we extend a predictive model of user performance to account for expectations as to item groupings; 2) we adapt an ant colony optimizer that has been proven efficient for this class of problems; and 3) we present MenuOptimizer, a set of inter-actions integrated into a real interface design tool (QtDesigner). MenuOptimizer supports designers' abilities to cope with uncertainty and recognize good solutions. It allows designers to delegate combinatorial problems to the optimizer, which should solve them quickly enough without disrupting the design process. We show evidence that satisfactory menu designs can be produced for complex problems in minutes.}, author = {Bailly, Gilles and Oulasvirta, Antti and Kötzing, Timo and Hoppe, Sabrina}, booktitle = {User Interface Software and Technology (UIST)}, keywords = {imported timokoetzing uist year2013}, pages = {331-342}, title = {MenuOptimizer: interactive optimization of menu systems}, year = 2013 }

2013

Friedrich, Tobias; Sauerwald, Thomas; Stauffer, Alexandre Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary DimensionsAlgorithmica 2013: 65–88
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A random geometric graph (RGG) is defined by placing \(n\) points uniformly at random in \([0,n^{1/d}]^d\), and joining two points by an edge whenever their Euclidean distance is at most some fixed \(r\). We assume that \(r\) is larger than the critical value for the emergence of a connected component with \(\Omega(n)\) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of \(\omega(\log n / r^{d-1})\), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is \(\Theta(n^{1/d}/r)\) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also 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 w.h.p. this algorithm informs every node in the largest connected component of an RGG within \(\Theta(n^1/d/r+\log n)\) rounds.
@article{DBLP:journals/algorithmica/FriedrichSS13, abstract = {A random geometric graph (RGG) is defined by placing \(n\) points uniformly at random in \([0,n^{1/d}]^d\), and joining two points by an edge whenever their Euclidean distance is at most some fixed \(r\). We assume that \(r\) is larger than the critical value for the emergence of a connected component with \(\Omega(n)\) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a Euclidean distance of \(\omega(\log n / r^{d-1})\), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is \(\Theta(n^{1/d}/r)\) w.h.p. We also prove that the condition on the Euclidean distance above is essentially tight. We also 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 w.h.p. this algorithm informs every node in the largest connected component of an RGG within \(\Theta(n^{1/d}/r+\log n)\) rounds.}, author = {Friedrich, Tobias and Sauerwald, Thomas and Stauffer, Alexandre}, journal = {Algorithmica}, keywords = {algorithmica noabstract tobiasfriedrich year2013}, number = 1, pages = {65-88}, title = {Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions}, volume = 67, year = 2013 }

Cseh, Ágnes; Matuschke, Jannik; Skutella, Martin Stable Flows over TimeAlgorithms 2013: 532–545
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this paper, the notion of stability is extended to network flows over time. As a useful device in our proofs, we present an elegant preflow-push variant of the Gale-Shapley algorithm that operates directly on the given network and computes stable flows in pseudo-polynomial time, both in the static flow and the flow over time case. We show periodical properties of stable flows over time on networks with an infinite time horizon. Finally, we discuss the influence of storage at vertices, with different results depending on the priority of the corresponding holdover edges.
@article{cseh2013stable, abstract = {In this paper, the notion of stability is extended to network flows over time. As a useful device in our proofs, we present an elegant preflow-push variant of the Gale-Shapley algorithm that operates directly on the given network and computes stable flows in pseudo-polynomial time, both in the static flow and the flow over time case. We show periodical properties of stable flows over time on networks with an infinite time horizon. Finally, we discuss the influence of storage at vertices, with different results depending on the priority of the corresponding holdover edges.}, author = {Cseh, Ágnes and Matuschke, Jannik and Skutella, Martin}, journal = {Algorithms}, keywords = {sys:relevantfor:ae agnescseh algorithms jannikmatuschke martinskutella year2013}, pages = {532-545}, title = {Stable Flows over Time}, year = 2013 }

Bringmann, Karl; Friedrich, Tobias; Igel, Christian; Voß, Thomas Speeding up many-objective optimization by Monte Carlo approximationsArtificial Intelligence 2013: 22–29
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Many state-of-the-art evolutionary vector optimization algorithms compute the contributing hypervolume for ranking candidate solutions. However, with an increasing number of objectives, calculating the volumes becomes intractable. Therefore, although hypervolume-based algorithms are often the method of choice for bi-criteria optimization, they are regarded as not suitable for many-objective optimization. Recently, Monte Carlo methods have been derived and analyzed for approximating the contributing hypervolume. Turning theory into practice, we employ these results in the ranking procedure of the multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES) as an example of a state-of-the-art method for vector optimization. It is empirically shown that the approximation does not impair the quality of the obtained solutions given a budget of objective function evaluations, while considerably reducing the computation time in the case of multiple objectives. These results are obtained on common benchmark functions as well as on two design optimization tasks. Thus, employing Monte Carlo approximations makes hypervolume-based algorithms applicable to many-objective optimization.
@article{DBLP:journals/ai/BringmannFIV13, abstract = {Many state-of-the-art evolutionary vector optimization algorithms compute the contributing hypervolume for ranking candidate solutions. However, with an increasing number of objectives, calculating the volumes becomes intractable. Therefore, although hypervolume-based algorithms are often the method of choice for bi-criteria optimization, they are regarded as not suitable for many-objective optimization. Recently, Monte Carlo methods have been derived and analyzed for approximating the contributing hypervolume. Turning theory into practice, we employ these results in the ranking procedure of the multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES) as an example of a state-of-the-art method for vector optimization. It is empirically shown that the approximation does not impair the quality of the obtained solutions given a budget of objective function evaluations, while considerably reducing the computation time in the case of multiple objectives. These results are obtained on common benchmark functions as well as on two design optimization tasks. Thus, employing Monte Carlo approximations makes hypervolume-based algorithms applicable to many-objective optimization.}, author = {Bringmann, Karl and Friedrich, Tobias and Igel, Christian and Voß, Thomas}, journal = {Artificial Intelligence}, keywords = {imported tobiasfriedrich year2013}, pages = {22-29}, title = {Speeding up many-objective optimization by Monte Carlo approximations}, volume = 204, year = 2013 }

Bringmann, Karl; Friedrich, Tobias Approximation quality of the hypervolume indicatorArtificial Intelligence 2013: 265–290
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multi-objective 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 bounded from below by a reference point. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator of sets of bounded size 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 ratio with the approximation ratio achieved by two-dimensional sets maximizing the hypervolume indicator. We bound the optimal multiplicative approximation ratio 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. However, there is a provable gap between the two approximation ratios which 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 in two dimensions and prove that it achieves the optimal additive approximation ratio apart from a small ratio.
@article{DBLP:journals/ai/BringmannF13, abstract = {In order to allow a comparison of (otherwise incomparable) sets, many evolutionary multi-objective 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 bounded from below by a reference point. Though the hypervolume indicator is very popular, it has not been shown that maximizing the hypervolume indicator of sets of bounded size 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 ratio with the approximation ratio achieved by two-dimensional sets maximizing the hypervolume indicator. We bound the optimal multiplicative approximation ratio 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. However, there is a provable gap between the two approximation ratios which 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 in two dimensions and prove that it achieves the optimal additive approximation ratio apart from a small ratio.}, author = {Bringmann, Karl and Friedrich, Tobias}, journal = {Artificial Intelligence}, keywords = {ai imported tobiasfriedrich year2013}, pages = {265-290}, title = {Approximation quality of the hypervolume indicator}, volume = 195, year = 2013 }

Sutton, Andrew M.; Chicano, Francisco; Whitley, L. Darrell Fitness Function Distributions over Generalized Search Neighborhoods in the q-ary HypercubeEvolutionary Computation 2013: 561–590
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The frequency distribution of a fitness function over regions of its domain is an important quantity for understanding the behavior of algorithms that employ randomized sampling to search the function. In general, exactly characterizing this distribution is at least as hard as the search problem, since the solutions typically live in the tails of the distribution. However, in some cases it is possible to efficiently retrieve a collection of quantities called moments that describe the distribution. In this paper, we consider functions of bounded epistasis that are defined over length-\(n\) strings from a finite alphabet of cardinality \(q\). Many problems in combinatorial optimization can be specified as search problems over functions of this type. Employing Fourier analysis of functions over finite groups, we derive an efficient method for computing the exact moments of the frequency distribution of fitness functions over Hamming regions of the \(q\)-ary hypercube. We then use this approach to derive equations that describe the expected fitness of the offspring of any point undergoing uniform mutation. The results we present provide insight into the statistical structure of the fitness function for a number of combinatorial problems. For the graph coloring problem, we apply our results to efficiently compute the average number of constraint violations that lie within a certain number of steps of any coloring. We derive an expression for the mutation rate that maximizes the expected fitness of an offspring at each fitness level. We also apply the results to the slightly more complex frequency assignment problem, a relevant application in the domain of the telecommunications industry. As with the graph coloring problem, we provide formulas for the average value of the fitness function in Hamming regions around a solution and the expectation-optimal mutation rate.
@article{DBLP:journals/ec/SuttonCW13, abstract = {The frequency distribution of a fitness function over regions of its domain is an important quantity for understanding the behavior of algorithms that employ randomized sampling to search the function. In general, exactly characterizing this distribution is at least as hard as the search problem, since the solutions typically live in the tails of the distribution. However, in some cases it is possible to efficiently retrieve a collection of quantities called moments that describe the distribution. In this paper, we consider functions of bounded epistasis that are defined over length-\(n\) strings from a finite alphabet of cardinality \(q\). Many problems in combinatorial optimization can be specified as search problems over functions of this type. Employing Fourier analysis of functions over finite groups, we derive an efficient method for computing the exact moments of the frequency distribution of fitness functions over Hamming regions of the \(q\)-ary hypercube. We then use this approach to derive equations that describe the expected fitness of the offspring of any point undergoing uniform mutation. The results we present provide insight into the statistical structure of the fitness function for a number of combinatorial problems. For the graph coloring problem, we apply our results to efficiently compute the average number of constraint violations that lie within a certain number of steps of any coloring. We derive an expression for the mutation rate that maximizes the expected fitness of an offspring at each fitness level. We also apply the results to the slightly more complex frequency assignment problem, a relevant application in the domain of the telecommunications industry. As with the graph coloring problem, we provide formulas for the average value of the fitness function in Hamming regions around a solution and the expectation-optimal mutation rate.}, author = {Sutton, Andrew M. and Chicano, Francisco and Whitley, L. Darrell}, journal = {Evolutionary Computation}, keywords = {andrewmsutton ec imported year2013}, number = 4, pages = {561-590}, title = {Fitness Function Distributions over Generalized Search Neighborhoods in the q-ary Hypercube}, volume = 21, year = 2013 }

Albers, Susanne; Lenzner, Pascal On Approximate Nash Equilibria in Network DesignInternet Mathematics 2013: 384–405
[ Abstract ] [ BibTeX ] [ 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.
@article{DBLP:journals/im/AlbersL13, 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.}, author = {Albers, Susanne and Lenzner, Pascal}, journal = {Internet Mathematics}, keywords = {imported pascal pascallenzner year2013}, number = 4, pages = {384-405}, title = {On Approximate Nash Equilibria in Network Design}, volume = 9, year = 2013 }

Friedrich, Tobias; Kroeger, Trent; Neumann, Frank Weighted preferences in evolutionary multi-objective optimizationMachine Learning and Cybernetics 2013: 139–148
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Evolutionary algorithms have been widely used to tackle multi-objective optimization problems. Incorporating preference information into the search of evolutionary algorithms for multi-objective optimization is of great importance as it allows one to focus on interesting regions in the objective space. Zitzler et al. have shown how to use a weight distribution function on the objective space to incorporate preference information into hypervolume-based algorithms. We show that this weighted information can easily be used in other popular EMO algorithms as well. Our results for NSGA-II and SPEA2 show that this yields similar results to the hypervolume approach and requires less computational effort.
@article{DBLP:journals/mlc/FriedrichKN13, abstract = {Evolutionary algorithms have been widely used to tackle multi-objective optimization problems. Incorporating preference information into the search of evolutionary algorithms for multi-objective optimization is of great importance as it allows one to focus on interesting regions in the objective space. Zitzler et al. have shown how to use a weight distribution function on the objective space to incorporate preference information into hypervolume-based algorithms. We show that this weighted information can easily be used in other popular EMO algorithms as well. Our results for NSGA-II and SPEA2 show that this yields similar results to the hypervolume approach and requires less computational effort.}, author = {Friedrich, Tobias and Kroeger, Trent and Neumann, Frank}, journal = {Machine Learning and Cybernetics}, keywords = {frankneumann imported mlc tobiasfriedrich trentkroeger year2013}, number = 2, pages = {139-148}, title = {Weighted preferences in evolutionary multi-objective optimization}, volume = 4, year = 2013 }

Friedrich, Tobias; Levine, Lionel Fast simulation of large-scale growth modelsRandom Structures and Algorithms 2013: 185–213
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We give an algorithm that computes the final state of certain growth models without computing all intermediate states. Our technique is based on a "least action principle" which characterizes the odometer function of the growth process. Starting from an approximation for the odometer, we successively correct under- and overestimates and provably arrive at the correct final state. The degree of speedup depends on the accuracy of the initial guess. Determining the size of the boundary fluctuations in growth models like internal diffusion-limited aggregation (IDLA) is a long-standing open problem in statistical physics. As an application of our method, we calculate the size of fluctuations over two orders of magnitude beyond previous simulations.
@article{DBLP:journals/rsa/FriedrichL13, abstract = {We give an algorithm that computes the final state of certain growth models without computing all intermediate states. Our technique is based on a "least action principle" which characterizes the odometer function of the growth process. Starting from an approximation for the odometer, we successively correct under- and overestimates and provably arrive at the correct final state. The degree of speedup depends on the accuracy of the initial guess. Determining the size of the boundary fluctuations in growth models like internal diffusion-limited aggregation (IDLA) is a long-standing open problem in statistical physics. As an application of our method, we calculate the size of fluctuations over two orders of magnitude beyond previous simulations.}, author = {Friedrich, Tobias and Levine, Lionel}, journal = {Random Structures and Algorithms}, keywords = {noabstract rsa tobiasfriedrich year2013}, number = 2, pages = {185-213}, title = {Fast simulation of large-scale growth models}, volume = 42, year = 2013 }

Vladislavleva, Ekaterina; Friedrich, Tobias; Neumann, Frank; Wagner, Markus Predicting the Energy Output of Wind Farms Based on Weather Data: Important Variables and their CorrelationRenewable Energy 2013: 236–243
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Wind energy plays an increasing role in the supply of energy world wide. The energy output of a wind farm is highly dependent on the weather conditions present at its site. If the output can be predicted more accurately, energy suppliers can coordinate the collaborative production of different energy sources more efficiently to avoid costly overproduction. In this paper, we take a computer science perspective on energy prediction based on weather data and analyze the important parameters as well as their correlation on the energy output. To deal with the interaction of the different parameters, we use symbolic regression based on the genetic programming tool DataModeler. Our studies are carried out on publicly available weather and energy data for a wind farm in Australia. We report on the correlation of the different variables for the energy output. The model obtained for energy prediction gives a very reliable prediction of the energy output for newly supplied weather data.
@article{RE1, abstract = {Wind energy plays an increasing role in the supply of energy world wide. The energy output of a wind farm is highly dependent on the weather conditions present at its site. If the output can be predicted more accurately, energy suppliers can coordinate the collaborative production of different energy sources more efficiently to avoid costly overproduction. In this paper, we take a computer science perspective on energy prediction based on weather data and analyze the important parameters as well as their correlation on the energy output. To deal with the interaction of the different parameters, we use symbolic regression based on the genetic programming tool DataModeler. Our studies are carried out on publicly available weather and energy data for a wind farm in Australia. We report on the correlation of the different variables for the energy output. The model obtained for energy prediction gives a very reliable prediction of the energy output for newly supplied weather data.}, author = {Vladislavleva, Ekaterina and Friedrich, Tobias and Neumann, Frank and Wagner, Markus}, journal = {Renewable Energy}, keywords = {RE ekatarinavladislavleva frankneumann markuswagner tobiasfriedrich year2013}, pages = {236-243}, publisher = {Elsevier}, title = {Predicting the Energy Output of Wind Farms Based on Weather Data: Important Variables and their Correlation}, volume = 50, year = 2013 }

Koepke, Peter; Räsch, Karen; Schlicht, Philipp A minimal Prikry-type forcing for singularizing a measurable cardinalThe Journal of Symbolic Logic 2013: 85–100
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Recently, Gitik, Kanovei and the first author proved that for a classical Prikry forcing extension the family of the intermediate models can be parametrized by \(P(\omega)/finite\). By modifying the standard Prikry tree forcing we define a Prikry-type forcing which also singularizes a measurable cardinal but which is minimal, i.e. there are \emph{no} intermediate models properly between the ground model and the generic extension. The proof relies on combining the rigidity of the tree structure with indiscernibility arguments resulting from the normality of the associated measures.
@article{DBLP:journals/jsyml/KoepkeRS13, abstract = {Recently, Gitik, Kanovei and the first author proved that for a classical Prikry forcing extension the family of the intermediate models can be parametrized by \(P(\omega)/finite\). By modifying the standard Prikry tree forcing we define a Prikry-type forcing which also singularizes a measurable cardinal but which is minimal, i.e. there are \emph{no} intermediate models properly between the ground model and the generic extension. The proof relies on combining the rigidity of the tree structure with indiscernibility arguments resulting from the normality of the associated measures.}, author = {Koepke, Peter and Räsch, Karen and Schlicht, Philipp}, journal = {The Journal of Symbolic Logic}, keywords = {jsl karenseidel year2013}, number = {01}, pages = {85-100}, publisher = {Cambridge Univ Press}, title = {A minimal Prikry-type forcing for singularizing a measurable cardinal}, volume = 78, year = 2013 }

Doerr, Benjamin; Johannsen, Daniel; Kötzing, Timo; Neumann, Frank; Theile, Madeleine More effective crossover operators for the all-pairs shortest path problemTheoretical Computer Science 2013: 12–26
[ 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.
@article{DBLP:journals/tcs/DoerrJKNT13, 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}, journal = {Theoretical Computer Science}, keywords = {benjamindoerr danieljohannsen frankneumann imported madeleinetheile tcs timokoetzing year2013}, pages = {12-26}, title = {More effective crossover operators for the all-pairs shortest path problem}, volume = 471, year = 2013 }

Fellows, Michael R.; Friedrich, Tobias; Hermelin, Danny; Narodytska, Nina; Rosamond, Frances A. Constraint satisfaction problems: Convexity makes AllDifferent constraints tractableTheoretical Computer Science 2013: 81–89
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.
@article{DBLP:journals/tcs/FellowsFHNR13, abstract = {We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.}, author = {Fellows, Michael R. and Friedrich, Tobias and Hermelin, Danny and Narodytska, Nina and Rosamond, Frances A.}, journal = {Theoretical Computer Science}, keywords = {imported tcs tobiasfriedrich year2013}, pages = {81-89}, title = {Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable}, volume = 472, year = 2013 }

Doerr, Benjamin; Kötzing, Timo; Lengler, Johannes; Winzen, Carola Black-box complexities of combinatorial problemsTheoretical Computer Science 2013: 84–106
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Black-box complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithms and other randomized search heuristics. Most previous work on black-box complexity is on artificial test functions. In this paper, we move a step forward and give a detailed analysis for the two combinatorial problems minimum spanning tree and single-source shortest paths. Besides giving interesting bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem is non-trivial here. This in particular comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on.
@article{DBLP:journals/tcs/DoerrKLW13, abstract = {Black-box complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithms and other randomized search heuristics. Most previous work on black-box complexity is on artificial test functions. In this paper, we move a step forward and give a detailed analysis for the two combinatorial problems minimum spanning tree and single-source shortest paths. Besides giving interesting bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem is non-trivial here. This in particular comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on.}, author = {Doerr, Benjamin and Kötzing, Timo and Lengler, Johannes and Winzen, Carola}, journal = {Theoretical Computer Science}, keywords = {benjamindoerr caroladoerr imported johanneslengler tcs timokoetzing year2013}, pages = {84-106}, title = {Black-box complexities of combinatorial problems}, volume = 471, year = 2013 }

Case, John; Kötzing, Timo Memory-limited non-U-shaped learning with solved open problemsTheoretical Computer Science 2013: 100–123
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
In empirical cognitive science, for human learning, a semantic or behavioral U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Within the formal framework of Inductive Inference, for learning from positive data, 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 also distinguish between semantic and syntactic U-shapes. We answer a number of open questions in the prior literature as well as provide new results regarding syntactic U-shapes. Importantly for cognitive science, we see more of a previously noticed pattern that, for parameterized learning criteria, beyond very few initial parameter values, U-shapes are necessary for full learning power. We analyze the necessity of U-shapes in two memory-limited settings. The first setting is Bounded Memory State (BMS) learning, where a learner has an explicitly-bounded state memory, and otherwise only knows its current datum. We show that there are classes learnable with three (or more) memory states that are not learnable non-U-shapedly with any finite number of memory states. This result is surprising, since, for learning with one or two memory states, U-shapes are known to be unnecessary. This solves an open question from the literature. The second setting is that of Memoryless Feedback (MLF) learning, where a learner may ask a bounded number of questions about what data has been seen so far, and otherwise only knows its current datum. We show 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. We employ self-learning classes together with the Operator Recursion Theorem for many of our results, but we also introduce two new techniques for obtaining results. The first is for transferring inclusion results from one setting to another. The main part of the second is the Hybrid Operator Recursion Theorem, which enables us to separate some learning criteria featuring complexity-bounded learners, employing self-learning classes. Both techniques are not specific to U-shaped learning, but applicable for a wide range of settings.
@article{DBLP:journals/tcs/CaseK13, abstract = {In empirical cognitive science, for human learning, a semantic or behavioral U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Within the formal framework of Inductive Inference, for learning from positive data, 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 also distinguish between semantic and syntactic U-shapes. We answer a number of open questions in the prior literature as well as provide new results regarding syntactic U-shapes. Importantly for cognitive science, we see more of a previously noticed pattern that, for parameterized learning criteria, beyond very few initial parameter values, U-shapes are necessary for full learning power. We analyze the necessity of U-shapes in two memory-limited settings. The first setting is Bounded Memory State (BMS) learning, where a learner has an explicitly-bounded state memory, and otherwise only knows its current datum. We show that there are classes learnable with three (or more) memory states that are not learnable non-U-shapedly with any finite number of memory states. This result is surprising, since, for learning with one or two memory states, U-shapes are known to be unnecessary. This solves an open question from the literature. The second setting is that of Memoryless Feedback (MLF) learning, where a learner may ask a bounded number of questions about what data has been seen so far, and otherwise only knows its current datum. We show 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. We employ self-learning classes together with the Operator Recursion Theorem for many of our results, but we also introduce two new techniques for obtaining results. The first is for transferring inclusion results from one setting to another. The main part of the second is the Hybrid Operator Recursion Theorem, which enables us to separate some learning criteria featuring complexity-bounded learners, employing self-learning classes. Both techniques are not specific to U-shaped learning, but applicable for a wide range of settings.}, author = {Case, John and Kötzing, Timo}, journal = {Theoretical Computer Science}, keywords = {imported timokoetzing year2013}, pages = {100-123}, title = {Memory-limited non-U-shaped learning with solved open problems}, volume = 473, year = 2013 }