2015

Chauhan, Ankit; Rao, B. V. Raghavendra Parameterized Analogues of Probabilistic ComputationConference on Algorithms and Discrete Applied Mathematics (CALDAM) 2015: 181–192
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study structural aspects of randomized parameterized computation. We introduce a new class W[P]-PFPT as a natural parameterized analogue of PP. Our definition uses the machine based characterization of the parameterized complexity class W[P] obtained by Chen et.al [TCS 2005]. We translate most of the structural properties and characterizations of the class PP to the new class W[P]-PFPT. We study a parameterization of the polynomial identity testing problem based on the degree of the polynomial computed by the arithmetic circuit. We obtain a parameterized analogue of the well known Schwartz-Zippel lemma [Schwartz, JACM 80 and Zippel, EUROSAM 79]. Additionally, we introduce a parameterized variant of permanent, and prove its #W[1] completeness.
@inproceedings{DBLP:conf/caldam/ChauhanR15, abstract = {We study structural aspects of randomized parameterized computation. We introduce a new class W[P]-PFPT as a natural parameterized analogue of PP. Our definition uses the machine based characterization of the parameterized complexity class W[P] obtained by Chen et.al [TCS 2005]. We translate most of the structural properties and characterizations of the class PP to the new class W[P]-PFPT. We study a parameterization of the polynomial identity testing problem based on the degree of the polynomial computed by the arithmetic circuit. We obtain a parameterized analogue of the well known Schwartz-Zippel lemma [Schwartz, JACM 80 and Zippel, EUROSAM 79]. Additionally, we introduce a parameterized variant of permanent, and prove its \#W[1] completeness.}, author = {Chauhan, Ankit and Rao, B. V. Raghavendra}, booktitle = {Conference on Algorithms and Discrete Applied Mathematics (CALDAM)}, keywords = {CALDAM ankitchauhan year2015}, pages = {181-192}, title = {Parameterized Analogues of Probabilistic Computation}, year = 2015 }

Bringmann, Karl; Friedrich, Tobias; Klitzke, Patrick Efficient computation of two-dimensional solution sets maximizing the epsilon-indicatorCongress on Evolutionary Computation (CEC) 2015: 970–977
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The majority of empirical comparisons of multi-objective evolutionary algorithms (MOEAs) are performed on synthetic benchmark functions. One of the advantages of synthetic test functions is the a-priori knowledge of the optimal Pareto front. This allows measuring the proximity to the optimal front for the solution sets returned by the different MOEAs. Such a comparison is only meaningful if the cardinality of all solution sets is bounded by some fixed \(k\). In order to compare MOEAs to the theoretical optimum achievable with \(k\) solutions, we determine best possible \(\epsilon\)-indicator values achievable with solution sets of size \(k\), up to an error of \(\delta\). We present a new algorithm with runtime \(O(k cdot \log^2(\delta-1))\), which is an exponential improvement regarding the dependence on the error \(\delta\) compared to all previous work. We show mathematical correctness of our algorithm and determine optimal solution sets for sets of cardinality \(k \in \2, 3, 4, 5, 10, 20, 50, 100, 1000\}\) for the well known test suits DTLZ, ZDT, WFG and LZ09 up to error \(\delta = 10^{-25}\).
@inproceedings{DBLP:conf/cec/BringmannFK15, abstract = {The majority of empirical comparisons of multi-objective evolutionary algorithms (MOEAs) are performed on synthetic benchmark functions. One of the advantages of synthetic test functions is the a-priori knowledge of the optimal Pareto front. This allows measuring the proximity to the optimal front for the solution sets returned by the different MOEAs. Such a comparison is only meaningful if the cardinality of all solution sets is bounded by some fixed \(k\). In order to compare MOEAs to the theoretical optimum achievable with \(k\) solutions, we determine best possible \(\epsilon\)-indicator values achievable with solution sets of size \(k\), up to an error of \(\delta\). We present a new algorithm with runtime \(O(k \cdot \log^2(\delta-1))\), which is an exponential improvement regarding the dependence on the error \(\delta\) compared to all previous work. We show mathematical correctness of our algorithm and determine optimal solution sets for sets of cardinality \(k \in \{2, 3, 4, 5, 10, 20, 50, 100, 1000\}\) for the well known test suits DTLZ, ZDT, WFG and LZ09 up to error \(\delta = 10^{-25}\).}, author = {Bringmann, Karl and Friedrich, Tobias and Klitzke, Patrick}, booktitle = {Congress on Evolutionary Computation (CEC)}, keywords = {cec imported tobiasfriedrich year2015}, pages = {970-977}, title = {Efficient computation of two-dimensional solution sets maximizing the epsilon-indicator}, year = 2015 }

Bläsius, Thomas; Lehmann, Sebastian; Rutter, Ignaz Orthogonal Graph Drawing with Inflexible EdgesInternational Conference on Algorithms and Complexity (CIAC) 2015: 61–73
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge \(e\) a natural number \(flex(e)\), its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge \(e\) has at most \(flex(e)\) bends. It is known that FlexDraw is NP-hard if \(flex(e)=0\) for every edge \(e\) [7]. On the other hand, FlexDraw can be solved efficiently if \(flex(e) \ge1\) [2] and is trivial if \(flex(e) \ge 2\) [1] for every edge \(e\). To close the gap between the NP-hardness for \(flex(e)=0\) and the efficient algorithm for \(flex(e) \ge 1\), we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e., have flexibility 0). We show that for any \(\epsilon > 0\) FlexDraw is NP-complete for instances with \(O(n^\epsilon)\) inflexible edges with pairwise distance \(\Omega(n^{1-\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm with running time \(O(2^k cdot n cdot T_flow(n))\), where \(T_{flow(n)\) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and \(k\) is the number of inflexible edges having at least one endpoint of degree 4.
@inproceedings{DBLP:conf/ciac/BlasiusLR15, abstract = {We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge \(e\) a natural number \(flex(e)\), its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge \(e\) has at most \(flex(e)\) bends. It is known that FlexDraw is NP-hard if \(flex(e)=0\) for every edge \(e\) [7]. On the other hand, FlexDraw can be solved efficiently if \(flex(e) \ge1\) [2] and is trivial if \(flex(e) \ge 2\) [1] for every edge \(e\). To close the gap between the NP-hardness for \(flex(e)=0\) and the efficient algorithm for \(flex(e) \ge 1\), we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e., have flexibility 0). We show that for any \(\epsilon > 0\) FlexDraw is NP-complete for instances with \(O(n^\epsilon)\) inflexible edges with pairwise distance \(\Omega(n^{1-\epsilon})\) (including the case where they induce a matching). On the other hand, we give an FPT-algorithm with running time \(O(2^k \cdot n \cdot T_{flow}(n))\), where \(T_{flow}(n)\) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and \(k\) is the number of inflexible edges having at least one endpoint of degree 4.}, author = {Bläsius, Thomas and Lehmann, Sebastian and Rutter, Ignaz}, booktitle = {International Conference on Algorithms and Complexity (CIAC)}, keywords = {imported thomas thomasblaesius year2015}, pages = {61-73}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Orthogonal Graph Drawing with Inflexible Edges}, volume = 9079, year = 2015 }

Kötzing, Timo; Lissovoi, Andrei; Witt, Carsten (1+1) EA on Generalized Dynamic OneMaxFoundations of Genetic Algorithms (FOGA) 2015: 40–51
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We re-prove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension. Furthermore, we make an anytime analysis as suggested by Jansen and Zarges (2014), analyzing how closely the (1+1) EA can track the dynamically moving optimum over time. We get tight bounds both for the case of bit strings, as well as for the case of more than two values per position. Surprisingly, in the latter setting, the expected quality of the search point maintained by the (1+1) EA does not depend on the number of values per dimension.
@inproceedings{DBLP:conf/foga/KotzingLW15, abstract = {Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We re-prove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension. Furthermore, we make an anytime analysis as suggested by Jansen and Zarges (2014), analyzing how closely the (1+1) EA can track the dynamically moving optimum over time. We get tight bounds both for the case of bit strings, as well as for the case of more than two values per position. Surprisingly, in the latter setting, the expected quality of the search point maintained by the (1+1) EA does not depend on the number of values per dimension.}, author = {Kötzing, Timo and Lissovoi, Andrei and Witt, Carsten}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, keywords = {imported timokoetzing year2015}, pages = {40-51}, publisher = {{ACM}}, title = {(1+1) EA on Generalized Dynamic OneMax}, year = 2015 }

Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, Alexander Pixel and Voxel Representations of GraphsGraph Drawing (GD) 2015: 472–486
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D. Two pixels are adjacent if they share an edge, two voxels if they share a face. We call a connected set of pixels or voxels a blob. Given a graph, we represent its vertices by disjoint blobs such that two blobs contain adjacent pixels or voxels if and only if the corresponding vertices are adjacent. We are interested in the size of a representation, which is the number of pixels or voxels it consists of. We first show that finding minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for \(k\)-outerplanar graphs with \(n\) vertices, \(\Theta(kn)\) pixels are always sufficient and sometimes necessary. In particular, outerplanar graphs can be represented with a linear number of pixels, whereas general planar graphs sometimes need a quadratic number. In 3D, \(\Theta(n^2)\) voxels are always sufficient and sometimes necessary for any \(n\)-vertex graph. We improve this bound to \(\Theta(n \cdot \tau)\) for graphs of treewidth \(\tau\) and to \(O((g+1)^2 n \log^2 n)\) for graphs of genus \(g\). In particular, planar graphs admit representations with \(O(n\log^2 n)\) voxels.
@inproceedings{DBLP:conf/gd/AlamBRUW15, abstract = {We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D. Two pixels are adjacent if they share an edge, two voxels if they share a face. We call a connected set of pixels or voxels a blob. Given a graph, we represent its vertices by disjoint blobs such that two blobs contain adjacent pixels or voxels if and only if the corresponding vertices are adjacent. We are interested in the size of a representation, which is the number of pixels or voxels it consists of. We first show that finding minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for \(k\)-outerplanar graphs with \(n\) vertices, \(\Theta(kn)\) pixels are always sufficient and sometimes necessary. In particular, outerplanar graphs can be represented with a linear number of pixels, whereas general planar graphs sometimes need a quadratic number. In 3D, \(\Theta(n^2)\) voxels are always sufficient and sometimes necessary for any \(n\)-vertex graph. We improve this bound to \(\Theta(n \cdot \tau)\) for graphs of treewidth \(\tau\) and to \(O((g+1)^2 n \log^2 n)\) for graphs of genus \(g\). In particular, planar graphs admit representations with \(O(n\log^2 n)\) voxels.}, author = {Alam, Md. Jawaherul and Bläsius, Thomas and Rutter, Ignaz and Ueckerdt, Torsten and Wolff, Alexander}, booktitle = {Graph Drawing (GD)}, keywords = {GD imported thomas thomasblaesius year2015}, pages = {472-486}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Pixel and Voxel Representations of Graphs}, volume = 9411, year = 2015 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Robustness of Ant Colony Optimization to NoiseGenetic and Evolutionary Computation Conference (GECCO) 2015: 17–24
Best-Paper Award (ACO/SI Track)
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding. We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical \((\mu+1)\)-EA outperforms any ACO algorithm, with smaller \(\mu\) being better; however, with large noise, the \((\mu+1)\)-EA fails, even for high values of \(\mu\) (which are known to help against small noise). In this paper we show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor \(\mu\) is small enough dependent on the parameter \(\delta^2\) of the noise and the dimension \(n\) of the search space \((p = o(1/(n(n + \delta \log n)^2 \log n)))\), optimization will be successful.
@inproceedings{DBLP:conf/gecco/FriedrichKKS15, abstract = {Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding. We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical \((\mu+1)\)-EA outperforms any ACO algorithm, with smaller \(\mu\) being better; however, with large noise, the \((\mu+1)\)-EA fails, even for high values of \(\mu\) (which are known to help against small noise). In this paper we show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor \(\mu\) is small enough dependent on the parameter \(\delta^2\) of the noise and the dimension \(n\) of the search space \((p = o(1/(n(n + \delta \log n)^2 \log n)))\), optimization will be successful.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton bestpaper first gecco imported martinskrejca timokoetzing tobiasfriedrich year2015}, note = {Best-Paper Award (ACO/SI Track)}, pages = {17-24}, title = {Robustness of Ant Colony Optimization to Noise}, year = 2015 }

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Solving Problems with Unknown Solution Length at (Almost) No Extra CostGenetic and Evolutionary Computation Conference (GECCO) 2015: 831–838
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to real-world optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length. We then show that almost the same run times can be achieved even if no a priori information on the solution length is available. Finally, we provide mutation rates suitable for settings in which neither the solution length nor the positions of the relevant bits are known. Again we obtain almost optimal run times for the OneMax and LeadingOnes test functions, thus solving an open problem from Cathabard et al.
@inproceedings{DBLP:conf/gecco/DoerrDK15, abstract = {Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to real-world optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length. We then show that almost the same run times can be achieved even if no a priori information on the solution length is available. Finally, we provide mutation rates suitable for settings in which neither the solution length nor the positions of the relevant bits are known. Again we obtain almost optimal run times for the OneMax and LeadingOnes test functions, thus solving an open problem from Cathabard et al.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr caroladoerr gecco imported timokoetzing year2015}, pages = {831-838}, title = {Solving Problems with Unknown Solution Length at (Almost) No Extra Cost}, year = 2015 }

Doerr, Benjamin; Neumann, Frank; Sutton, Andrew M. Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance CorrelationGenetic and Evolutionary Computation Conference (GECCO) 2015: 1415–1422
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942-951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time \(O(n \log n)\) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.
@inproceedings{DBLP:conf/gecco/DoerrNS15, abstract = {With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942-951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time \(O(n \log n)\) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.}, author = {Doerr, Benjamin and Neumann, Frank and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {andrewmsutton benjamindoerr bestpaper frankneumann gecco imported second year2015}, pages = {1415-1422}, publisher = {{ACM}}, title = {Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation}, year = 2015 }

Cseh, Ágnes; Huang, Chien-Chung; Kavitha, Telikepalli Popular Matchings with Two-Sided Preferences and One-Sided TiesInternational Colloquium on Automata, Languages and Programming (ICALP) 2015: 367–379
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
We are given a bipartite graph \($G=(A \cup B, E)$\) where each vertex has a preference list ranking its neighbors: in particular, every \($a \in A$\) ranks its neighbors in a strict order of preference, whereas the preference lists of \($b \in B$\) may contain ties. A matching \($M$\) is popular if there is no matching \($M'$\) such that the number of vertices that prefer \($M'$\) to \($M$\) exceeds the number that prefer \($M$\) to \($M'$\). We show that the problem of deciding whether \($G$\) admits a popular matching or not is NP-hard. This is the case even when every \($b \in B$\) either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each \($b \in B$\) puts all its neighbors into a single tie. That is, all neighbors of \($b$\) are tied in \($b’s$\) list and and b desires to be matched to any of them. Our main result is an \($\mathcal{O(n^2)$\) algorithm (where \($n=|A \cup B|$\)) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in \($B$\) have no preferences and do not care whether they are matched or not.
@inproceedings{cseh2015popular, abstract = {We are given a bipartite graph $G=(A \cup B, E)$ where each vertex has a preference list ranking its neighbors: in particular, every $a \in A$ ranks its neighbors in a strict order of preference, whereas the preference lists of $b \in B$ may contain ties. A matching $M$ is popular if there is no matching $M'$ such that the number of vertices that prefer $M'$ to $M$ exceeds the number that prefer $M$ to $M'$. We show that the problem of deciding whether $G$ admits a popular matching or not is NP-hard. This is the case even when every $b \in B$ either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each $b \in B$ puts all its neighbors into a single tie. That is, all neighbors of $b$ are tied in $b’s$ list and and b desires to be matched to any of them. Our main result is an $\mathcal{O}(n^2)$ algorithm (where $n=|A \cup B|$) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in $B$ have no preferences and do not care whether they are matched or not.}, author = {Cseh, Ágnes and Huang, Chien-Chung and Kavitha, Telikepalli}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sys:relevantfor:ae agnescseh chien-chunghuang icalp telikepallikavitha year2015}, pages = {367-379}, title = {Popular Matchings with Two-Sided Preferences and One-Sided Ties}, year = 2015 }

Bringmann, Karl; Friedrich, Tobias; Hoefer, Martin; Rothenberger, Ralf; Sauerwald, Thomas Ultra-Fast Load Balancing on Scale-Free NetworksInternational Colloquium on Automata, Languages and Programming (ICALP) 2015: 516–527
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The performance of large distributed systems crucially depends on efficiently balancing their load. This has motivated a large amount of theoretical research how an imbalanced load vector can be smoothed with local algorithms. For technical reasons, the vast majority of previous work focuses on regular (or almost regular) graphs including symmetric topologies such as grids and hypercubes, and ignores the fact that large networks are often highly heterogenous. We model large scale-free networks by Chung-Lu random graphs and analyze a simple local algorithm for iterative load balancing. On n-node graphs our distributed algorithm balances the load within \(O((log~log~n)^2)\) steps. It does not need to know the exponent \(2<\beta<3\) of the power-law degree distribution or the weights \(w_i\) of the graph model. To the best of our knowledge, this is the first result which shows that load-balancing can be done in double-logarithmic time on realistic graph classes.
@inproceedings{DBLP:conf/icalp/BringmannFHRS15, abstract = {The performance of large distributed systems crucially depends on efficiently balancing their load. This has motivated a large amount of theoretical research how an imbalanced load vector can be smoothed with local algorithms. For technical reasons, the vast majority of previous work focuses on regular (or almost regular) graphs including symmetric topologies such as grids and hypercubes, and ignores the fact that large networks are often highly heterogenous. We model large scale-free networks by Chung-Lu random graphs and analyze a simple local algorithm for iterative load balancing. On n-node graphs our distributed algorithm balances the load within \(O((log&nbsp;log&nbsp;n)^2)\) steps. It does not need to know the exponent \(2<\beta<3\) of the power-law degree distribution or the weights \(w_i\) of the graph model. To the best of our knowledge, this is the first result which shows that load-balancing can be done in double-logarithmic time on realistic graph classes.}, author = {Bringmann, Karl and Friedrich, Tobias and Hoefer, Martin and Rothenberger, Ralf and Sauerwald, Thomas}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {icalp imported ralfrothenberger tobiasfriedrich year2015}, pages = {516-527}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Ultra-Fast Load Balancing on Scale-Free Networks}, volume = 9135, year = 2015 }

Friedrich, Tobias; Krohmer, Anton On the Diameter of Hyperbolic Random GraphsInternational Colloquium on Automata, Languages and Programming (ICALP) 2015: 614–625
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing performs close to optimal (Boguna, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power-law degree distribution with controllable exponent \(\beta\) and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573-585, 2012). For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is \(O((\log n)\)\(^{32/((3-\beta)(5-\beta))})\) (Kiwi and Mitsche. ANALCO, pp. 26-39, 2015). We present two much simpler proofs for an improved upper bound of \(O((\log n)\)\(^{2/(3-\beta)})\) and a lower bound of \(\Omega(\log n)\). If the average degree is bounded from above by some constant, we show that the latter bound is tight by proving an upper bound of \(O(\log n)\).
@inproceedings{DBLP:conf/icalp/FriedrichK15, abstract = {Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing performs close to optimal (Boguna, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power-law degree distribution with controllable exponent \(\beta\) and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573-585, 2012). For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is \(O((\log n)\)\(^{32/((3-\beta)(5-\beta))})\) (Kiwi and Mitsche. ANALCO, pp. 26-39, 2015). We present two much simpler proofs for an improved upper bound of \(O((\log n)\)\(^{2/(3-\beta)})\) and a lower bound of \(\Omega(\log n)\). If the average degree is bounded from above by some constant, we show that the latter bound is tight by proving an upper bound of \(O(\log n)\).}, author = {Friedrich, Tobias and Krohmer, Anton}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {antonkrohmer hyperbolic_analysis icalp imported tobiasfriedrich year2015}, pages = {614-625}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {On the Diameter of Hyperbolic Random Graphs}, volume = 9135, year = 2015 }

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Square-Free Graphs, Modulo 2International Colloquium on Automata, Languages, and Programming (ICALP) 2015: 642–653
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem \( \oplus \)HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph \(H\). A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (nonmodular) counting; thus, subtle dichotomy theorems can arise. We show the following dichotomy: for any \(H\) that contains no 4-cycles, \(\oplus\)HomsToH is either in polynomial time or is \(\oplus\)P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example, in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.
@inproceedings{DBLP:conf/icalp/0001GR15, abstract = {We study the problem \( \oplus \)HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph \(H\). A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (nonmodular) counting; thus, subtle dichotomy theorems can arise. We show the following dichotomy: for any \(H\) that contains no 4-cycles, \(\oplus\)HomsToH is either in polynomial time or is \(\oplus\)P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example, in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {andreasgoebel icalp notaccepted year2015}, pages = {642-653}, title = {Counting Homomorphisms to Square-Free Graphs, Modulo 2}, year = 2015 }

Friedrich, Tobias; Krohmer, Anton Cliques in Hyperbolic Random GraphsInternational Conference on Computer Communications (INFOCOM) 2015: 1544–1552
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Most complex real-world networks display scale-free features. This motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Papadopoulos, Krioukov, Boguna, Vahdat (INFOCOM, pp. 2973-2981, 2010) and has shown theoretically and empirically to fulfill all typical properties of real-world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs \(G\) and present new results on the expected number of \(k\)-cliques \(E[K_k]\) and the size of the largest clique \(\omega(G)\). We observe that there is a phase transition at power-law exponent \(\gamma = 3\). More precisely, for \(\gamma\) \(\in\) \((2,3)\) we prove \(E[K_k] = \)\(n^{k(3-\gamma)/2}\)\(\Theta(k)^{-k}\) and \(\omega(G) = \)\(\Theta(\)\(n^{(3-\gamma)/2})\) while for \(\gamma \ge 3\) we prove \(E[K_k] = n \Theta(k)^{-k}\) and \(\omega(G) = \Theta(\log(n)/\log \log n)\). We empirically compare the \(\omega(G)\) value of several scale-free random graph models with real-world networks. Our experiments show that the \(\omega(G)\)-predictions by hyperbolic random graphs are much closer to the data than other scale-free random graph models.
@inproceedings{DBLP:conf/infocom/FriedrichK15, abstract = {Most complex real-world networks display scale-free features. This motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Papadopoulos, Krioukov, Boguna, Vahdat (INFOCOM, pp. 2973-2981, 2010) and has shown theoretically and empirically to fulfill all typical properties of real-world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs \(G\) and present new results on the expected number of \(k\)-cliques \(E[K_k]\) and the size of the largest clique \(\omega(G)\). We observe that there is a phase transition at power-law exponent \(\gamma = 3\). More precisely, for \(\gamma\) \(\in\) \((2,3)\) we prove \(E[K_k] = \)\(n^{k(3-\gamma)/2}\)\(\Theta(k)^{-k}\) and \(\omega(G) = \)\(\Theta(\)\(n^{(3-\gamma)/2})\) while for \(\gamma \ge 3\) we prove \(E[K_k] = n \Theta(k)^{-k}\) and \(\omega(G) = \Theta(\log(n)/\log \log n)\). We empirically compare the \(\omega(G)\) value of several scale-free random graph models with real-world networks. Our experiments show that the \(\omega(G)\)-predictions by hyperbolic random graphs are much closer to the data than other scale-free random graph models.}, author = {Friedrich, Tobias and Krohmer, Anton}, booktitle = {International Conference on Computer Communications (INFOCOM)}, keywords = {antonkrohmer hyperbolic_analysis imported infocom tobiasfriedrich year2015}, pages = {1544-1552}, title = {Cliques in Hyperbolic Random Graphs}, year = 2015 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Benefit of Recombination in Noisy Evolutionary SearchInternational Symposium of Algorithms and Computation (ISAAC) 2015: 140–150
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings meta-heuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper we want to support this claim with mathematical rigor. The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the \((\mu+1)\)-EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm which does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population.
@inproceedings{DBLP:conf/isaac/FriedrichKKS15, abstract = {Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings meta-heuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper we want to support this claim with mathematical rigor. The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the \((\mu+1)\)-EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm which does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population.}, address = {Berlin, Heidelberg}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Sutton, Andrew M.}, booktitle = {International Symposium of Algorithms and Computation (ISAAC)}, editor = {Elbassioni, Khaled and Makino, Kazuhisa}, keywords = {andrewmsutton isaac martinskrejca timokoetzing tobiasfriedrich year2015}, pages = {140-150}, publisher = {Springer Berlin Heidelberg}, title = {The Benefit of Recombination in Noisy Evolutionary Search}, year = 2015 }

Arulselvan, Ashwin; Cseh, Ágnes; Groß, Martin; Manlove, David F.; Matuschke, Jannik Many-to-one Matchings with Lower Quotas: Algorithms and ComplexityInternational Symposium Algorithms and Computation (ISAAC) 2015: 176–187
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph \(G = (A \cup P, E)\) with weights on the edges in \(E\), and with lower and upper quotas on the vertices in \(P\). We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (wmlq), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of wmlq from the viewpoints of classic polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota \($u_max$\) as basis, and we prove that this dependence is necessary unless FPT=W[1]. Finally, we also present an approximation algorithm for the general case with performance guarantee \(u_max + 1\), which is asymptotically best possible unless \(P=NP\).
@inproceedings{arulselvan2015manytoone, abstract = {We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph \(G = (A \cup P, E)\) with weights on the edges in \(E\), and with lower and upper quotas on the vertices in \(P\). We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (wmlq), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of wmlq from the viewpoints of classic polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between NP -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $u_max$ as basis, and we prove that this dependence is necessary unless FPT=W[1]. Finally, we also present an approximation algorithm for the general case with performance guarantee \(u_max + 1\), which is asymptotically best possible unless \(P=NP\).}, author = {Arulselvan, Ashwin and Cseh, Ágnes and Groß, Martin and Manlove, David F. and Matuschke, Jannik}, booktitle = {International Symposium Algorithms and Computation (ISAAC)}, keywords = {sys:relevantfor:ae agnescseh ashwinarulselvan davidfmanlove isaac jannikmatuschke martingroß year2015}, pages = {176-187}, title = {Many-to-one Matchings with Lower Quotas: Algorithms and Complexity}, year = 2015 }

Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Unbounded Discrepancy of Deterministic Random Walks on GridsInternational Symposium on Algorithms and Computation (ISAAC) 2015: 212–222
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs, called rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave remarkably similar: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer (2006) showed that on \(\mathbb{Z}^d\) the single vertex discrepancy is only a constant \(c_d\). Other authors also determined the precise value of \(c_d\) for \(d=1,2\). All these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph \(\mathbb{Z}^d\). We show that this assumption is crucial by proving that otherwise the single vertex discrepancy can become arbitrarily large. For all dimensions \(d \ge 1\) and arbitrary discrepancies \(\ell \ge 0\), we construct configurations that reach a discrepancy of at least \(\ell\).
@inproceedings{DBLP:conf/isaac/FriedrichKK15, abstract = {Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs, called rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave remarkably similar: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer (2006) showed that on \(\mathbb{Z}^d\) the single vertex discrepancy is only a constant \(c_d\). Other authors also determined the precise value of \(c_d\) for \(d=1,2\). All these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph \(\mathbb{Z}^d\). We show that this assumption is crucial by proving that otherwise the single vertex discrepancy can become arbitrarily large. For all dimensions \(d \ge 1\) and arbitrary discrepancies \(\ell \ge 0\), we construct configurations that reach a discrepancy of at least \(\ell\).}, author = {Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, keywords = {antonkrohmer imported isaac maximiliankatzmann tobiasfriedrich year2015}, pages = {212-222}, series = {Lecture Notes in Computer Science}, title = {Unbounded Discrepancy of Deterministic Random Walks on Grids}, volume = 9472, year = 2015 }

Cord-Landwehr, Andreas; Lenzner, Pascal Network Creation Games: Think Global - Act LocalMathematical Foundations of Computer Science (MFCS) 2015: 248–260
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (Fabrikant et al., PODC'03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bilo et al., SPAA'14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus non-local strategy changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a non-constant lower bound on the Price of Anarchy.
@inproceedings{DBLP:conf/mfcs/Cord-LandwehrL15, abstract = {We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (Fabrikant et al., PODC'03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bilo et al., SPAA'14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus non-local strategy changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a non-constant lower bound on the Price of Anarchy.}, author = {Cord-Landwehr, Andreas and Lenzner, Pascal}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, keywords = {imported mfcs pascal pascallenzner year2015}, pages = {248-260}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Network Creation Games: Think Global - Act Local}, volume = 9235, year = 2015 }

Cseh, Ágnes; Manlove, David F. Stable Marriage and Roommates Problems with Restricted Edges: Complexity and ApproximabilitySymposium Algorithmic Game Theory (SAGT) 2015: 15–26
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
In the stable marriage and roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. A matching is a set of disjoint pairs of mutually acceptable agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. We investigate the complexity of finding a solution satisfying additional constraints on restricted pairs of agents. Restricted pairs can be either forced or forbidden. A stable solution must contain all of the forced pairs, while it must contain none of the forbidden pairs. Dias et al. [5] gave a polynomial-time algorithm to decide whether such a solution exists in the presence of restricted edges. If the answer is no, one might look for a solution close to optimal. Since optimality in this context means that the matching is stable and satisfies all constraints on restricted pairs, there are two ways of relaxing the constraints by permitting a solution to: (1) be blocked by as few as possible pairs, or (2) violate as few as possible constraints on restricted pairs. Our main theorems prove that for the (bipartite) stable marriage problem, case (1) leads to NP-hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For non-bipartite stable roommates instances, case (2) yields an NP-hard but (under some cardinality assumptions) 2-approximable problem. In the case of NP-hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.
@inproceedings{cseh2015stable, abstract = {In the stable marriage and roommates problems, a set of agents is given, each of them having a strictly ordered preference list over some or all of the other agents. A matching is a set of disjoint pairs of mutually acceptable agents. If any two agents mutually prefer each other to their partner, then they block the matching, otherwise, the matching is said to be stable. We investigate the complexity of finding a solution satisfying additional constraints on restricted pairs of agents. Restricted pairs can be either forced or forbidden. A stable solution must contain all of the forced pairs, while it must contain none of the forbidden pairs. Dias et al. [5] gave a polynomial-time algorithm to decide whether such a solution exists in the presence of restricted edges. If the answer is no, one might look for a solution close to optimal. Since optimality in this context means that the matching is stable and satisfies all constraints on restricted pairs, there are two ways of relaxing the constraints by permitting a solution to: (1) be blocked by as few as possible pairs, or (2) violate as few as possible constraints on restricted pairs. Our main theorems prove that for the (bipartite) stable marriage problem, case (1) leads to NP-hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For non-bipartite stable roommates instances, case (2) yields an NP-hard but (under some cardinality assumptions) 2-approximable problem. In the case of NP-hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.}, author = {Cseh, Ágnes and Manlove, David F.}, booktitle = {Symposium Algorithmic Game Theory (SAGT)}, keywords = {sys:relevantfor:ae agnescseh davidfmanlove sagt year2015}, pages = {15-26}, title = {Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability}, year = 2015 }

Rothenberger, Ralf; Grau, Sascha; Rossberg, Michael Dominating an s-t-Cut in a NetworkCurrent Trends in Theory and Practice of Computer Science (SOFSEM) 2015: 401–411
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study an optimization problem with applications in design and analysis of resilient communication networks: given two vertices \(s, t\) in a graph \(G = (V,E)\), find a vertex set \(X \subset V\) of minimum cardinality, such that \(X\) and its neighborhood constitute an \(s-t\) vertex separator. Although the problem naturally combines notions of graph connectivity and domination, its computational properties significantly differ from these relatives. In particular, we show that on general graphs the problem cannot be approximated to within a factor of \(2^{\log^{1-\delta}n}\), with \(\delta = 1 / \log\log^cn\) and arbitrary \(c<1/2\) (if P \(\neq\) NP). This inapproximability result even applies if the subgraph induced by a solution set has the additional constraint of being connected. Furthermore, we give a \(2\sqrt{n}\)-approximation algorithm and study the problem on graphs with bounded node degree. With \(\Delta\) being the maximum degree of nodes \(V \setminus \{s,t\}\), we identify a \((\Delta + 1)\) approximation algorithm.
@inproceedings{DBLP:conf/sofsem/RothenbergerGR15, abstract = {We study an optimization problem with applications in design and analysis of resilient communication networks: given two vertices \(s, t\) in a graph \(G = (V,E)\), find a vertex set \(X \subset V\) of minimum cardinality, such that \(X\) and its neighborhood constitute an \(s-t\) vertex separator. Although the problem naturally combines notions of graph connectivity and domination, its computational properties significantly differ from these relatives. In particular, we show that on general graphs the problem cannot be approximated to within a factor of \(2^{\log^{1-\delta}n}\), with \(\delta = 1 / \log\log^cn\) and arbitrary \(c<1/2\) (if P \(\neq\) NP). This inapproximability result even applies if the subgraph induced by a solution set has the additional constraint of being connected. Furthermore, we give a \(2\sqrt{n}\)-approximation algorithm and study the problem on graphs with bounded node degree. With \(\Delta\) being the maximum degree of nodes \(V \setminus \{s,t\}\), we identify a \((\Delta + 1)\) approximation algorithm.}, author = {Rothenberger, Ralf and Grau, Sascha and Rossberg, Michael}, booktitle = {Current Trends in Theory and Practice of Computer Science (SOFSEM)}, keywords = {SOFSEM ralfrothenberger year2015}, pages = {401-411}, title = {Dominating an s-t-Cut in a Network}, year = 2015 }

Teibrich, Alexander; Mueller, Stefanie; Guimbretière, François; Kovacs, Robert; Neubert, Stefan; Baudisch, Patrick Patching Physical ObjectsUser Interface Software and Technology (UIST) 2015: 83–91
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Personal fabrication is currently a one-way process: Once an object has been fabricated with a 3D printer, it cannot be changed anymore; any change requires printing a new version from scratch. The problem is that this approach ignores the nature of design iteration, i.e. that in subsequent iterations large parts of an object stay the same and only small parts change. This makes fabricating from scratch feel unnecessary and wasteful. In this paper, we propose a different approach: instead of re-printing the entire object from scratch, we suggest patching the existing object to reflect the next design iteration. We built a system on top of a 3D printer that accomplishes this: Users mount the existing object into the 3D printer, then load both the original and the modified 3D model into our software, which in turn calculates how to patch the object. After identifying which parts to remove and what to add, our system locates the existing object in the printer using the system's built-in 3D scanner. After calibrating the orientation, a mill first removes the outdated geometry, then a print head prints the new geometry in place. Since only a fraction of the entire object is refabricated, our approach reduces material consumption and plastic waste (for our example objects by 82\% and 93\% respectively).
@inproceedings{Teibrich:2015:PPO:2807442.2807467, abstract = {Personal fabrication is currently a one-way process: Once an object has been fabricated with a 3D printer, it cannot be changed anymore; any change requires printing a new version from scratch. The problem is that this approach ignores the nature of design iteration, i.e. that in subsequent iterations large parts of an object stay the same and only small parts change. This makes fabricating from scratch feel unnecessary and wasteful. In this paper, we propose a different approach: instead of re-printing the entire object from scratch, we suggest patching the existing object to reflect the next design iteration. We built a system on top of a 3D printer that accomplishes this: Users mount the existing object into the 3D printer, then load both the original and the modified 3D model into our software, which in turn calculates how to patch the object. After identifying which parts to remove and what to add, our system locates the existing object in the printer using the system's built-in 3D scanner. After calibrating the orientation, a mill first removes the outdated geometry, then a print head prints the new geometry in place. Since only a fraction of the entire object is refabricated, our approach reduces material consumption and plastic waste (for our example objects by 82\% and 93\% respectively).}, address = {New York, NY, USA}, author = {Teibrich, Alexander and Mueller, Stefanie and Guimbretière, François and Kovacs, Robert and Neubert, Stefan and Baudisch, Patrick}, booktitle = {User Interface Software and Technology (UIST)}, keywords = {stefanneubert uist year2015}, pages = {83-91}, publisher = {ACM}, series = {UIST '15}, title = {Patching Physical Objects}, year = 2015 }

2015

Friedrich, Tobias; Wagner, Markus Seeding the initial population of multi-objective evolutionary algorithms: A computational studyApplied Soft Computing 2015: 223–230
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Most experimental studies initialize the population of evolutionary algorithms with random genotypes. In practice, however, optimizers are typically seeded with good candidate solutions either previously known or created according to some problem-specific method. This seeding has been studied extensively for single-objective problems. For multi-objective problems, however, very little literature is available on the approaches to seeding and their individual benefits and disadvantages. In this article, we are trying to narrow this gap via a comprehensive computational study on common real-valued test functions. We investigate the effect of two seeding techniques for five algorithms on 48 optimization problems with 2, 3, 4, 6, and 8 objectives. We observe that some functions (e.g., DTLZ4 and the LZ family) benefit significantly from seeding, while others (e.g., WFG) profit less. The advantage of seeding also depends on the examined algorithm.
@article{DBLP:journals/asc/Friedrich015, abstract = {Most experimental studies initialize the population of evolutionary algorithms with random genotypes. In practice, however, optimizers are typically seeded with good candidate solutions either previously known or created according to some problem-specific method. This seeding has been studied extensively for single-objective problems. For multi-objective problems, however, very little literature is available on the approaches to seeding and their individual benefits and disadvantages. In this article, we are trying to narrow this gap via a comprehensive computational study on common real-valued test functions. We investigate the effect of two seeding techniques for five algorithms on 48 optimization problems with 2, 3, 4, 6, and 8 objectives. We observe that some functions (e.g., DTLZ4 and the LZ family) benefit significantly from seeding, while others (e.g., WFG) profit less. The advantage of seeding also depends on the examined algorithm.}, author = {Friedrich, Tobias and Wagner, Markus}, journal = {Applied Soft Computing}, keywords = {asc imported tobiasfriedrich year2015}, pages = {223-230}, title = {Seeding the initial population of multi-objective evolutionary algorithms: A computational study}, volume = 33, year = 2015 }

Bläsius, Thomas; Rutter, Ignaz Disconnectivity and relative positions in simultaneous embeddingsComputational Geometry 2015: 459–478
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
For two planar graphs \(G^1 = ( V^1, E^1)\) and \(G^2 = ( V^2, E^2)\) sharing a common subgraph \(G = G^1 \cap G^2\) the problem Simultaneous Embedding with Fixed Edges (SEFE) asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where \(G\) is connected, and hence do not need to handle relative positions of connected components. We consider the problem where \(G\), \(G^1\) and \(G^2\) are not necessarily connected.First, we show that a general instance of SEFE can be reduced in linear time to an equivalent instance where \(V^1 = V^2\) and \(G^1\) and \(G^2\) are connected. Second, for the case where \(G\) consists of disjoint cycles, we introduce the CC-tree which represents all embeddings of \(G\) that extend to planar embeddings of \(G^1\). We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all \(k\) input graphs (possibly \(k > 2\)) pairwise share the same set of disjoint cycles. These results, including the CC-tree, extend to the case where \(G\) consists of arbitrary connected components, each with a fixed planar embedding on the sphere. Then the running time is \(O(n^2)\).
@article{DBLP:journals/comgeo/BlasiusR15, abstract = {For two planar graphs \(G^1 = ( V^1, E^1)\) and \(G^2 = ( V^2, E^2)\) sharing a common subgraph \(G = G^1 \cap G^2\) the problem Simultaneous Embedding with Fixed Edges (SEFE) asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where \(G\) is connected, and hence do not need to handle relative positions of connected components. We consider the problem where \(G\), \(G^1\) and \(G^2\) are not necessarily connected.First, we show that a general instance of SEFE can be reduced in linear time to an equivalent instance where \(V^1 = V^2\) and \(G^1\) and \(G^2\) are connected. Second, for the case where \(G\) consists of disjoint cycles, we introduce the CC-tree which represents all embeddings of \(G\) that extend to planar embeddings of \(G^1\). We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all \(k\) input graphs (possibly \(k > 2\)) pairwise share the same set of disjoint cycles. These results, including the CC-tree, extend to the case where \(G\) consists of arbitrary connected components, each with a fixed planar embedding on the sphere. Then the running time is \(O(n^2)\).}, author = {Bläsius, Thomas and Rutter, Ignaz}, journal = {Computational Geometry}, keywords = {imported thomas thomasblaesius year2015}, number = 6, pages = {459-478}, title = {Disconnectivity and relative positions in simultaneous embeddings}, volume = 48, year = 2015 }

Parsaei Majd, Leila; Rahimi, Ahad On the structure of sequentially Cohen-Macaulay bigraded modulesCzechoslovak Mathematical Journal 2015: 1011–1022
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Let \(K\) be a field and \(S = K[x_1, \dots, x_m, y_1, \dots, y_n ]\) be the standard bigraded polynomial ring over \(K\). In this paper, we explicitly describe the structure of finitely generated bigraded ”sequentially Cohen–Macaulay” \(S\)-modules with respect to \(Q = (y_1, \dots, y_n )\). Next, we give a characterization of sequentially Cohen–Macaulay modules with respect to \(Q\) in terms of local cohomology modules. Cohen–Macaulay modules that are sequentially Cohen–Macaulay with respect to \(Q\) are considered.
@article{parsaeimajd2015structure, abstract = {Let \(K\) be a field and \(S = K[x_1, \dots, x_m, y_1, \dots, y_n ]\) be the standard bigraded polynomial ring over \(K\). In this paper, we explicitly describe the structure of finitely generated bigraded ”sequentially Cohen–Macaulay” \(S\)-modules with respect to \(Q = (y_1, \dots, y_n )\). Next, we give a characterization of sequentially Cohen–Macaulay modules with respect to \(Q\) in terms of local cohomology modules. Cohen–Macaulay modules that are sequentially Cohen–Macaulay with respect to \(Q\) are considered.}, author = {Parsaei Majd, Leila and Rahimi, Ahad}, journal = {Czechoslovak Mathematical Journal}, keywords = {sys:relevantfor:ae ahadrahimi leilaparsaeimajd year2015}, pages = {1011-1022}, title = {On the structure of sequentially Cohen-Macaulay bigraded modules}, year = 2015 }

Friedrich, Tobias; Krohmer, Anton Parameterized clique on inhomogeneous random graphsDiscrete Applied Mathematics 2015: 130–138
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. In typical applications like social networks or biological networks, however, the considered graphs are scale-free, i.e., their degree sequence follows a power law. Their specific structure can be algorithmically exploited and makes it possible to solve clique much more efficiently. We prove that on inhomogeneous random graphs with \(n\) nodes and power law exponent \(\beta\), cliques of size \(k\) can be found in time \(O(n)\) for \(\beta \ge 3\) and in time \(O(ne^{k^4})\) for \(2 < \beta < 3\).
@article{DBLP:journals/dam/FriedrichK15, abstract = {Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. In typical applications like social networks or biological networks, however, the considered graphs are scale-free, i.e., their degree sequence follows a power law. Their specific structure can be algorithmically exploited and makes it possible to solve clique much more efficiently. We prove that on inhomogeneous random graphs with \(n\) nodes and power law exponent \(\beta\), cliques of size \(k\) can be found in time \(O(n)\) for \(\beta \ge 3\) and in time \(O(ne^{k^4})\) for \(2 < \beta < 3\).}, author = {Friedrich, Tobias and Krohmer, Anton}, journal = {Discrete Applied Mathematics}, keywords = {antonkrohmer dam imported tobiasfriedrich year2015}, pages = {130-138}, title = {Parameterized clique on inhomogeneous random graphs}, volume = 184, year = 2015 }

Wagner, Markus; Bringmann, Karl; Friedrich, Tobias; Neumann, Frank Efficient optimization of many objectives by approximation-guided evolutionEuropean Journal of Operational Research 2015: 465–479
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Multi-objective optimization problems arise frequently in applications, but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. We present a framework for evolutionary multi-objective optimization that allows to work with a formal notion of approximation. This approximation-guided evolutionary algorithm (AGE) has a worst-case runtime linear in the number of objectives and works with an archive that is an approximation of the non-dominated objective vectors seen during the run of the algorithm. Our experimental results show that AGE finds competitive or better solutions not only regarding the achieved approximation, but also regarding the total hypervolume. For all considered test problems, even for many (i.e., more than ten) dimensions, AGE discovers a good approximation of the Pareto front. This is not the case for established algorithms such as NSGA-II, SPEA2, and SMS-EMOA. In this paper we compare AGE with two additional algorithms that use very fast hypervolume-approximations to guide their search. This significantly speeds up the runtime of the hypervolume-based algorithms, which now allows a comparison of the underlying selection schemes.
@article{DBLP:journals/eor/0007BFN15, abstract = {Multi-objective optimization problems arise frequently in applications, but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. We present a framework for evolutionary multi-objective optimization that allows to work with a formal notion of approximation. This approximation-guided evolutionary algorithm (AGE) has a worst-case runtime linear in the number of objectives and works with an archive that is an approximation of the non-dominated objective vectors seen during the run of the algorithm. Our experimental results show that AGE finds competitive or better solutions not only regarding the achieved approximation, but also regarding the total hypervolume. For all considered test problems, even for many (i.e., more than ten) dimensions, AGE discovers a good approximation of the Pareto front. This is not the case for established algorithms such as NSGA-II, SPEA2, and SMS-EMOA. In this paper we compare AGE with two additional algorithms that use very fast hypervolume-approximations to guide their search. This significantly speeds up the runtime of the hypervolume-based algorithms, which now allows a comparison of the underlying selection schemes.}, author = {Wagner, Markus and Bringmann, Karl and Friedrich, Tobias and Neumann, Frank}, journal = {European Journal of Operational Research}, keywords = {eor frankneumann imported karlbringmann markuswagner tobiasfriedrich year2015}, number = 2, pages = {465-479}, title = {Efficient optimization of many objectives by approximation-guided evolution}, volume = 243, year = 2015 }

Friedrich, Tobias; Neumann, Frank; Thyssen, Christian Multiplicative Approximations, Optimal Hypervolume Distributions, and the Choice of the Reference PointEvolutionary Computation 2015: 131–159
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Many optimization problems arising in applications have to consider several objective functions at the same time. Evolutionary algorithms seem to be a very natural choice for dealing with multi-objective problems as the population of such an algorithm can be used to represent the trade-offs with respect to the given objective functions. In this paper, we contribute to the theoretical understanding of evolutionary algorithms for multi-objective problems. We consider indicator-based algorithms whose goal is to maximize the hypervolume for a given problem by distributing \(\mu\) points on the Pareto front. To gain new theoretical insights into the behavior of hypervolume-based algorithms we compare their optimization goal to the goal of achieving an optimal multiplicative approximation ratio. Our studies are carried out for different Pareto front shapes of bi-objective problems. For the class of linear fronts and a class of convex fronts, we prove that maximizing the hypervolume gives the best possible approximation ratio when assuming that the extreme points have to be included in both distributions of the points on the Pareto front. Furthermore, we investigate the choice of the reference point on the approximation behavior of hypervolume-based approaches and examine Pareto fronts of different shapes by numerical calculations.
@article{DBLP:journals/ec/FriedrichNT15, abstract = {Many optimization problems arising in applications have to consider several objective functions at the same time. Evolutionary algorithms seem to be a very natural choice for dealing with multi-objective problems as the population of such an algorithm can be used to represent the trade-offs with respect to the given objective functions. In this paper, we contribute to the theoretical understanding of evolutionary algorithms for multi-objective problems. We consider indicator-based algorithms whose goal is to maximize the hypervolume for a given problem by distributing \(\mu\) points on the Pareto front. To gain new theoretical insights into the behavior of hypervolume-based algorithms we compare their optimization goal to the goal of achieving an optimal multiplicative approximation ratio. Our studies are carried out for different Pareto front shapes of bi-objective problems. For the class of linear fronts and a class of convex fronts, we prove that maximizing the hypervolume gives the best possible approximation ratio when assuming that the extreme points have to be included in both distributions of the points on the Pareto front. Furthermore, we investigate the choice of the reference point on the approximation behavior of hypervolume-based approaches and examine Pareto fronts of different shapes by numerical calculations.}, author = {Friedrich, Tobias and Neumann, Frank and Thyssen, Christian}, journal = {Evolutionary Computation}, keywords = {christianthyssen ec frankneumann imported tobiasfriedrich year2015}, number = 1, pages = {131-159}, title = {Multiplicative Approximations, Optimal Hypervolume Distributions, and the Choice of the Reference Point}, volume = 23, year = 2015 }

Chicano, Francisco; Sutton, Andrew M.; Whitley, L. Darrell; Alba, Enrique Fitness Probability Distribution of Bit-Flip MutationEvolutionary Computation 2015: 217–248
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in \(p\), the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem Onemax, and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.
@article{DBLP:journals/ec/ChicanoSWA15, abstract = {Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in \(p\), the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem Onemax, and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.}, author = {Chicano, Francisco and Sutton, Andrew M. and Whitley, L. Darrell and Alba, Enrique}, journal = {Evolutionary Computation}, keywords = {andrewmsutton ec imported year2015}, number = 2, pages = {217-248}, title = {Fitness Probability Distribution of Bit-Flip Mutation}, volume = 23, year = 2015 }

Friedrich, Tobias; Neumann, Frank Maximizing Submodular Functions under Matroid Constraints by Evolutionary AlgorithmsEvolutionary Computation 2015: 543–558
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function \(f\) under a given set of constraints. In this paper, we investigate the runtime of a simple single objective evolutionary algorithm called (1+1) EA and a multi-objective evolutionary algorithm called GSEMO until they have obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints we show that the GSEMO achieves a \((1-1/e)\)-approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of \(k \ge 2\) matroids, we show that the (1+1) EA achieves a \((1 + k/\delta)\)-approximation in expected polynomial time for any constant \(\delta > 0\). Turning to non-monotone symmetric submodular functions with \(k \ge 1\) matroid intersection constraints, we show that the GSEMO achieves a \((1/((k+2)(1+\epsilon)))\)-approximation in expected time \(O(n^{k+6 \log(n)/\epsilon)\).
@article{DBLP:journals/ec/FriedrichN15, abstract = {Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function \(f\) under a given set of constraints. In this paper, we investigate the runtime of a simple single objective evolutionary algorithm called (1+1) EA and a multi-objective evolutionary algorithm called GSEMO until they have obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints we show that the GSEMO achieves a \((1-1/e)\)-approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of \(k \ge 2\) matroids, we show that the (1+1) EA achieves a \((1 + k/\delta)\)-approximation in expected polynomial time for any constant \(\delta > 0\). Turning to non-monotone symmetric submodular functions with \(k \ge 1\) matroid intersection constraints, we show that the GSEMO achieves a \((1/((k+2)(1+\epsilon)))\)-approximation in expected time \(O(n^{k+6} \log(n)/\epsilon)\).}, author = {Friedrich, Tobias and Neumann, Frank}, journal = {Evolutionary Computation}, keywords = {ec frankneumann tobiasfriedrich year2015}, number = 4, pages = {543-558}, publisher = {MIT Press}, title = {Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms}, volume = 23, year = 2015 }

Doerr, Benjamin; Doerr, Carola; Kötzing, Timo Unbiased Black-Box Complexities of Jump FunctionsEvolutionary Computation 2015: 641–670
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We analyze the unbiased black-box complexity of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we show that when the jump size is \((1/2-\epsilon)n\), that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities 3 and higher are of the same order as those for the simple OneMax function. Even for the extreme jump function, in which all but the two fitness values \(n/2\) and \(n\) are blanked out, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a \(\Theta(n^{-1/2})\) fraction) is a plateau of constant fitness. To prove these results, we introduce new tools for the analysis of unbiased black-box complexities, for example, selecting the new parent individual not by comparing the fitnesses of the competing search points, but also by taking into account the (empirical) expected fitnesses of their offspring.
@article{DBLP:journals/ec/DoerrDK15, abstract = {We analyze the unbiased black-box complexity of jump functions with small, medium, and large sizes of the fitness plateau surrounding the optimal solution. Among other results, we show that when the jump size is \((1/2-\epsilon)n\), that is, only a small constant fraction of the fitness values is visible, then the unbiased black-box complexities for arities 3 and higher are of the same order as those for the simple OneMax function. Even for the extreme jump function, in which all but the two fitness values \(n/2\) and \(n\) are blanked out, polynomial-time mutation-based (i.e., unary unbiased) black-box optimization algorithms exist. This is quite surprising given that for the extreme jump function almost the whole search space (all but a \(\Theta(n^{-1/2})\) fraction) is a plateau of constant fitness. To prove these results, we introduce new tools for the analysis of unbiased black-box complexities, for example, selecting the new parent individual not by comparing the fitnesses of the competing search points, but also by taking into account the (empirical) expected fitnesses of their offspring.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, journal = {Evolutionary Computation}, keywords = {benjamindoerr caroladoerr ec imported timokoetzing year2015}, number = 4, pages = {641-670}, title = {Unbiased Black-Box Complexities of Jump Functions}, volume = 23, year = 2015 }

Cohen, Sarel; Fiat, Amos; Hershcovitch, Moshik; Kaplan, Haim Minimal indices for predecessor searchInformation and Computation 2015: 12–30
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We give a new predecessor 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(\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 \(w ^{1/5}\) of a fusion tree node). To construct these indices we device highly efficient bit selectors which, we believe, are of independent interest.
@article{cohen2015minimal, abstract = {We give a new predecessor 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}(\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 \(w ^{1/5}\) of a fusion tree node). To construct these 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}, journal = {Information and Computation}, keywords = {sys:relevantfor:ae amosfiat haimkaplan ic moshikhershcovitch sarelcohen year2015}, pages = {12-30}, title = {Minimal indices for predecessor search}, year = 2015 }

Batra, Sanjit Singh; Kumar, Nikhil; Tripathi, Amitabha On a Linear Diophantine Problem Involving the Fibonacci and Lucas SequencesIntegers 2015: A26
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
For a positive and relatively prime set \(A\), let \(\Gamma(A)\) denote the set of integers that are formed by taking nonnegative integer linear combinations of integers in \(A\). Then there are finitely many positive integers that do not belong to \(\Gamma(A)\). For \(A\), let \(\texttt{g(A)\) and \(\texttt{n(A)\) denote the largest integer and the number of integers that do not belong to \(\Gamma(A)\), respectively. We determine both \(\texttt{g(A)\) and \(\texttt{n(A)\) for two sets that arise naturally from the Fibonacci sequence and the Lucas sequence.
@article{batra2015linear, abstract = {For a positive and relatively prime set \(A\), let \(\Gamma(A)\) denote the set of integers that are formed by taking nonnegative integer linear combinations of integers in \(A\). Then there are finitely many positive integers that do not belong to \(\Gamma(A)\). For \(A\), let \(\texttt{g}(A)\) and \(\texttt{n}(A)\) denote the largest integer and the number of integers that do not belong to \(\Gamma(A)\), respectively. We determine both \(\texttt{g}(A)\) and \(\texttt{n}(A)\) for two sets that arise naturally from the Fibonacci sequence and the Lucas sequence.}, author = {Batra, Sanjit Singh and Kumar, Nikhil and Tripathi, Amitabha}, journal = {Integers}, keywords = {amitabhatripathi integers nikhilkumar sanjitsinghbartra year2015}, pages = {A26}, title = {On a Linear Diophantine Problem Involving the Fibonacci and Lucas Sequences}, volume = 15, year = 2015 }

Berenbrink, Petra; Cooper, Colin; Friedetzky, Tom; Friedrich, Tobias; Sauerwald, Thomas Randomized diffusion for indivisible loadsJournal of Computer and System Sciences 2015: 159–185
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds compared to the algorithm of Rabani, Sinclair, and Wanka. For hypercubes we obtain a polynomial improvement. In contrast to previous papers, our algorithm is vertex-based and not edge-based. This means excess tokens are assigned to vertices instead to edges, and the vertex reallocates all of its excess tokens by itself. This approach avoids nodes having "negative loads", but causes additional dependencies for the analysis.
@article{DBLP:journals/jcss/BerenbrinkCFFS15, abstract = {We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds compared to the algorithm of Rabani, Sinclair, and Wanka. For hypercubes we obtain a polynomial improvement. In contrast to previous papers, our algorithm is vertex-based and not edge-based. This means excess tokens are assigned to vertices instead to edges, and the vertex reallocates all of its excess tokens by itself. This approach avoids nodes having "negative loads", but causes additional dependencies for the analysis.}, author = {Berenbrink, Petra and Cooper, Colin and Friedetzky, Tom and Friedrich, Tobias and Sauerwald, Thomas}, journal = {Journal of Computer and System Sciences}, keywords = {jcss noabstract tobiasfriedrich year2015}, number = 1, pages = {159-185}, title = {Randomized diffusion for indivisible loads}, volume = 81, year = 2015 }

Friedrich, Tobias; Hercher, Christian On the kernel size of clique cover reductions for random intersection graphsJournal of Discrete Algorithms 2015: 128–136
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Covering all edges of a graph by a minimum number of cliques is a well known NP -hard problem. For the parameter \(k\) being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worst-case. We study the average kernel size for random intersection graphs with \(n\) vertices, edge probability \(p\), and clique covers of size \(k\). We consider the well-known set of reduction rules of Gramm, Guo, Hüffner, and Niedermeier (2009) and show that with high probability they reduce the graph completely if \(p\) is bounded away from 1 and \(k < c \log n\) for some constant \(c > 0\) . This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worst-case bounds.
@article{DBLP:journals/jda/FriedrichH15, abstract = {Covering all edges of a graph by a minimum number of cliques is a well known NP -hard problem. For the parameter \(k\) being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worst-case. We study the average kernel size for random intersection graphs with \(n\) vertices, edge probability \(p\), and clique covers of size \(k\). We consider the well-known set of reduction rules of Gramm, Guo, Hüffner, and Niedermeier (2009) and show that with high probability they reduce the graph completely if \(p\) is bounded away from 1 and \(k < c \log n\) for some constant \(c > 0\) . This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worst-case bounds.}, author = {Friedrich, Tobias and Hercher, Christian}, journal = {Journal of Discrete Algorithms}, keywords = {christianhercher imported jda tobiasfriedrich year2015}, pages = {128-136}, title = {On the kernel size of clique cover reductions for random intersection graphs}, volume = 34, year = 2015 }

Paixão, Tiago; Badkobeh, Golnaz; Barton, Nick H.; Çörüş, Doğan; Dang, Duc-Cuong; Friedrich, Tobias; Lehre, Per Kristian; Sudholt, Dirk; Sutton, Andrew; Trubenová, Barbora Toward a unifying framework for evolutionary processesJournal of Theoretical Biology 2015: 28–43
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields.
@article{JTB1, abstract = {The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields.}, author = {Paixão, Tiago and Badkobeh, Golnaz and Barton, Nick H. and Çörüş, Doğan and Dang, Duc-Cuong and Friedrich, Tobias and Lehre, Per Kristian and Sudholt, Dirk and Sutton, Andrew and Trubenová, Barbora}, journal = {Journal of Theoretical Biology}, keywords = {JTB andrewmsutton tobiasfriedrich year2015}, pages = {28-43}, publisher = {Elsevier}, title = {Toward a unifying framework for evolutionary processes}, volume = 383, year = 2015 }

Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting List Matrix Partitions of GraphsSIAM Journal on Computing 2015: 1089–1118
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given a symmetric \(D\times D\) matrix \(M\) over \(0,1,*\), a list \(M\)-partition of a graph \(G\) is a partition of the vertices of \(G\) into \(D\) parts which are associated with the rows of \(M\). The part of each vertex is chosen from a given list in such a way that no edge of \(G\) is mapped to a 0 in \(M\) and no nonedge of \(G\) is mapped to a 1 in \(M\). Many important graph-theoretic structures can be represented as list \(M\)-partitions including graph colorings, split graphs, and homogeneous sets and pairs, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices \(M\) computations involving list \(M\)-partitions are tractable. This paper focuses on the problem of counting list \(M\)-partitions, given a graph \(G\) and given a list for each vertex of \(G\). We identify a certain set of "tractable" matrices \(M\). We give an algorithm that counts list \(M\)-partitions in polynomial time for every (fixed) matrix \(M\) in this set. The algorithm relies on data structures such as sparse-dense partitions and subcube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of \(M\) in which the interactions of 0s and 1s are controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (\({\#CSP}\)s), which we show how to solve using a constraint satisfaction technique known as arc-consistency. For every matrix \(M\) for which our algorithm fails, we show that the problem of counting list \(M\)-partitions is \({\#P}\)-complete. Furthermore, we give an explicit characterization of the dichotomy theorem: counting list \(M\)-partitions is tractable (in \({FP}\)) if the matrix \(M\) has a structure called a derectangularizing sequence. If \(M\) has no derectangularizing sequence, we show that counting list \(M\)-partitions is \({\#P}\)-hard. We show that the metaproblem of determining whether a given matrix has a derectangularizing sequence is \({NP}\)-complete. Finally, we show that list \(M\)-partitions can be used to encode cardinality restrictions in \(M\)-partitions problems, and we use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.
@article{DBLP:journals/siamcomp/0001GMRY15, abstract = {Given a symmetric \(D\times D\) matrix \(M\) over \(0,1,*\), a list \(M\)-partition of a graph \(G\) is a partition of the vertices of \(G\) into \(D\) parts which are associated with the rows of \(M\). The part of each vertex is chosen from a given list in such a way that no edge of \(G\) is mapped to a 0 in \(M\) and no nonedge of \(G\) is mapped to a 1 in \(M\). Many important graph-theoretic structures can be represented as list \(M\)-partitions including graph colorings, split graphs, and homogeneous sets and pairs, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices \(M\) computations involving list \(M\)-partitions are tractable. This paper focuses on the problem of counting list \(M\)-partitions, given a graph \(G\) and given a list for each vertex of \(G\). We identify a certain set of "tractable" matrices \(M\). We give an algorithm that counts list \(M\)-partitions in polynomial time for every (fixed) matrix \(M\) in this set. The algorithm relies on data structures such as sparse-dense partitions and subcube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of \(M\) in which the interactions of 0s and 1s are controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (\({\#CSP}\)s), which we show how to solve using a constraint satisfaction technique known as arc-consistency. For every matrix \(M\) for which our algorithm fails, we show that the problem of counting list \(M\)-partitions is \({\#P}\)-complete. Furthermore, we give an explicit characterization of the dichotomy theorem: counting list \(M\)-partitions is tractable (in \({FP}\)) if the matrix \(M\) has a structure called a derectangularizing sequence. If \(M\) has no derectangularizing sequence, we show that counting list \(M\)-partitions is \({\#P}\)-hard. We show that the metaproblem of determining whether a given matrix has a derectangularizing sequence is \({NP}\)-complete. Finally, we show that list \(M\)-partitions can be used to encode cardinality restrictions in \(M\)-partitions problems, and we use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and McQuillan, Colin and Richerby, David and Yamakami, Tomoyuki}, journal = {SIAM Journal on Computing}, keywords = {andreasgoebel siamcomp year2015}, number = 4, pages = {1089-1118}, title = {Counting List Matrix Partitions of Graphs}, volume = 44, year = 2015 }

Friedrich, Tobias; He, Jun; Jansen, Thomas; Moraglio, Alberto Genetic and Evolutionary ComputationTheoretical Computer Science 2015: 1–2
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Evolutionary computation and other nature-inspired search heuristics are known and applied on a daily basis for 50 years. They remain an important tool in situations where difficult problems need to be solved and no good problem-specific solution is available. Thanks to continuous efforts directed at a theoretical foundation of this broad and complex set of heuristics we have a much improved understanding of their properties, strengths and limitations. This special issue contains a collection of theoretical analyses of quite different nature-inspired heuristics, all presented in preliminary form either at the field’s largest conference, the Genetic and Evolutionary Computation Conference (GECCO 2013), or at a small and specialized workshop on Theory of Randomized Search Heuristics (ThRaSH 2013) that provides an opportunity for theoreticians in the field to meet and discuss their work since 2007. All articles presented here have been reworked and significantly expanded beyond their initial presentation and they all witness that theory is now developed well beyond the understanding of very simple evolutionary algorithms on simple example functions.
@article{DBLP:journals/tcs/FriedrichHJM15, abstract = {Evolutionary computation and other nature-inspired search heuristics are known and applied on a daily basis for 50 years. They remain an important tool in situations where difficult problems need to be solved and no good problem-specific solution is available. Thanks to continuous efforts directed at a theoretical foundation of this broad and complex set of heuristics we have a much improved understanding of their properties, strengths and limitations. This special issue contains a collection of theoretical analyses of quite different nature-inspired heuristics, all presented in preliminary form either at the field’s largest conference, the Genetic and Evolutionary Computation Conference (GECCO 2013), or at a small and specialized workshop on Theory of Randomized Search Heuristics (ThRaSH 2013) that provides an opportunity for theoreticians in the field to meet and discuss their work since 2007. All articles presented here have been reworked and significantly expanded beyond their initial presentation and they all witness that theory is now developed well beyond the understanding of very simple evolutionary algorithms on simple example functions.}, author = {Friedrich, Tobias and He, Jun and Jansen, Thomas and Moraglio, Alberto}, journal = {Theoretical Computer Science}, keywords = {noabstract tcs tobiasfriedrich year2015}, pages = {1-2}, title = {Genetic and Evolutionary Computation}, volume = 561, year = 2015 }

Fountoulakis, Nikolaos; Friedrich, Tobias; Hermelin, Danny On the average-case complexity of parameterized cliqueTheoretical Computer Science 2015: 18–29
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The \(k\)-Clique problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-known NP-complete and W[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the average-case complexity of the \(k\)-Clique problem on the parameter \(k\). To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that \(k\)-Clique admits both analogues for ErdHo}s-Rényi random graphs of arbitrary density. We also show that \(k\)-Clique is unlikely to admit either of these analogs for some specific computable input distribution.
@article{DBLP:journals/tcs/FountoulakisFH15, abstract = {The \(k\)-Clique problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-known NP-complete and W[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the average-case complexity of the \(k\)-Clique problem on the parameter \(k\). To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that \(k\)-Clique admits both analogues for Erd\H{o}s-Rényi random graphs of arbitrary density. We also show that \(k\)-Clique is unlikely to admit either of these analogs for some specific computable input distribution.}, author = {Fountoulakis, Nikolaos and Friedrich, Tobias and Hermelin, Danny}, journal = {Theoretical Computer Science}, keywords = {imported tcs tobiasfriedrich year2015}, pages = {18-29}, title = {On the average-case complexity of parameterized clique}, volume = 576, year = 2015 }

Nguyen, Anh Quang; Sutton, Andrew M.; Neumann, Frank Population size matters: Rigorous runtime results for maximizing the hypervolume indicatorTheoretical Computer Science 2015: 24–36
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Using the hypervolume indicator to guide the search of evolutionary multi-objective algorithms has become very popular in recent years. We contribute to the theoretical understanding of these algorithms by carrying out rigorous runtime analyses. We consider multi-objective variants of the problems OneMax and LeadingOnes called OMM and LOTZ, respectively, and investigate hypervolume-based algorithms with population sizes that do not allow coverage of the entire Pareto front. Our results show that LOTZ is easier to optimize than OMM for hypervolume-based evolutionary multi-objective algorithms which is contrary to the results on their single-objective variants and the well-studied (1+1)-EA.
@article{DBLP:journals/tcs/NguyenSN15, abstract = {Using the hypervolume indicator to guide the search of evolutionary multi-objective algorithms has become very popular in recent years. We contribute to the theoretical understanding of these algorithms by carrying out rigorous runtime analyses. We consider multi-objective variants of the problems OneMax and LeadingOnes called OMM and LOTZ, respectively, and investigate hypervolume-based algorithms with population sizes that do not allow coverage of the entire Pareto front. Our results show that LOTZ is easier to optimize than OMM for hypervolume-based evolutionary multi-objective algorithms which is contrary to the results on their single-objective variants and the well-studied (1+1)-EA.}, author = {Nguyen, Anh Quang and Sutton, Andrew M. and Neumann, Frank}, journal = {Theoretical Computer Science}, keywords = {andrewmsutton anhquangnguyen frankneumann imported tcs year2015}, pages = {24-36}, title = {Population size matters: Rigorous runtime results for maximizing the hypervolume indicator}, volume = 561, year = 2015 }

Freydenberger, Dominik D.; Kötzing, Timo Fast Learning of Restricted Regular Expressions and DTDsTheory of Computing Systems 2015: 1114–1158
[ 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.
@article{DBLP:journals/mst/FreydenbergerK15, 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}, journal = {Theory of Computing Systems}, keywords = {imported timokoetzing year2015}, number = 4, pages = {1114-1158}, title = {Fast Learning of Restricted Regular Expressions and DTDs}, volume = 57, year = 2015 }