2018

• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy Routing. Algorithm Engineering and Experiments (ALENEX) 2018: 199-208
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.
  @inproceedings{btkk2018hyperbolic, abstract = {Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, booktitle = {Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex antonkrohmer hyperbolic_embedding maximiliankatzmann thomasblaesius tobiasfriedrich year2018}, pages = {199-208}, title = {Hyperbolic Embeddings for Near-Optimal Greedy Routing}, year = 2018 }
• 
  Cseh, Ágnes; Kavitha, TelikepalliPopular Matchings in Complete Graphs. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2018: 17:1-17:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
   
  Our input is a complete graph G = (V,E) on n vertices where each vertex has a strict ranking of all other vertices in G. The goal is to construct a matching in G that is "globally stable" or popular. A matching M is popular if M does not lose a head-to-head election against any matching M': here each vertex casts a vote for the matching in M,M' where it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we show here.
  @inproceedings{cseh2018popular, abstract = {Our input is a complete graph G = (V,E) on n vertices where each vertex has a strict ranking of all other vertices in G. The goal is to construct a matching in G that is "globally stable" or popular. A matching M is popular if M does not lose a head-to-head election against any matching M': here each vertex casts a vote for the matching in {M,M'} where it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we show here.}, author = {Cseh, Ágnes and Kavitha, Telikepalli}, booktitle = {Foundations of Software Technology and Theoretical Computer Science (FSTTCS)}, keywords = {sys:relevantfor:ae agnescseh fsttcs telikepallikavitha year2018}, pages = {17:1-17:14}, title = {Popular Matchings in Complete Graphs}, year = 2018 }
• 
  Friedrich, Tobias; Quinzan, Francesco; Wagner, MarkusEscaping Large Deceptive Basins of Attraction with Heavy Mutation Operators. Genetic and Evolutionary Computation Conference (GECCO) 2018: 293-300
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In many Evolutionary Algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one. In a recent theoretical study, it was proposed to sample the number of mutated variables from a power-law distribution. This results into a significantly higher probability on larger numbers of mutations, so that escaping local optima becomes more probable. In this paper, we propose another class of non-uniform mutation rates. We study the benefits of this operator in terms of average-case black-box complexity analysis and experimental comparison. We consider both pseudo-Boolean artificial landscapes and combinatorial problems (the Minimum Vertex Cover and the Maximum Cut). We observe that our non-uniform mutation rates significantly outperform the standard choices, when dealing with landscapes that exhibit large deceptive basins of attraction.
  @inproceedings{friedrich2018escaping, abstract = {In many Evolutionary Algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one. In a recent theoretical study, it was proposed to sample the number of mutated variables from a power-law distribution. This results into a significantly higher probability on larger numbers of mutations, so that escaping local optima becomes more probable. In this paper, we propose another class of non-uniform mutation rates. We study the benefits of this operator in terms of average-case black-box complexity analysis and experimental comparison. We consider both pseudo-Boolean artificial landscapes and combinatorial problems (the Minimum Vertex Cover and the Maximum Cut). We observe that our non-uniform mutation rates significantly outperform the standard choices, when dealing with landscapes that exhibit large deceptive basins of attraction.}, author = {Friedrich, Tobias and Quinzan, Francesco and Wagner, Markus}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {GECCO francescoquinzan markuswagner tobiasfriedrich year2018}, pages = {293-300}, title = {Escaping Large Deceptive Basins of Attraction with Heavy Mutation Operators}, year = 2018 }
• 
  Friedrich, Tobias; Kötzing, Timo; Quinzan, Francesco; Sutton, Andrew M.Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences. Genetic and Evolutionary Computation Conference (GECCO) 2018: 301-308
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  In the context of black box optimization, the most common way to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple \((1+1)\) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the \((1+1)~EA_{\mathcal{U}}\), a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the \((1+1)~EA\) exhibits exponential run time. We prove that the \((1+1)~EA_{\mathcal{U}}\) has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the \((1+1)~EA\) yields exponential run time on those instances, and the \((1+1)~EA_{\mathcal{U}}\) finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the \((1+1)~EA\) does not find a \((4/3-\epsilon)\)-approximation in polynomial time, and we show that the \((1+1)~EA_{\mathcal{U}}\) reaches a \((4/3-\epsilon)\)-approximation in polynomial time. We then prove that the \((1+1)~EA_{\mathcal{U}}\) serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a \((1+\epsilon)\)-approximation with \(\epsilon > 4/n\).
  @inproceedings{friedrich2018improving, abstract = {In the context of black box optimization, the most common way to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple \((1+1)\) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the \((1+1)~EA_{\mathcal{U}}\), a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the \((1+1)~EA\) exhibits exponential run time. We prove that the \((1+1)~EA_{\mathcal{U}}\) has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the \((1+1)~EA\) yields exponential run time on those instances, and the \((1+1)~EA_{\mathcal{U}}\) finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the \((1+1)~EA\) does not find a \((4/3-\epsilon)\)-approximation in polynomial time, and we show that the \((1+1)~EA_{\mathcal{U}}\) reaches a \((4/3-\epsilon)\)-approximation in polynomial time. We then prove that the \((1+1)~EA_{\mathcal{U}}\) serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a \((1+\epsilon)\)-approximation with \(\epsilon > 4/n\).}, author = {Friedrich, Tobias and Kötzing, Timo and Quinzan, Francesco and Sutton, Andrew M.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {GECCO andrewmsutton francescoquinzan timokoetzing tobiasfriedrich year2018}, pages = {301-308}, title = {Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences}, year = 2018 }
• 
  Gao, Wanru; Friedrich, Tobias; Neumann, Frank; Hercher, ChristianRandomized Greedy Algorithms for Covering Problems. Genetic and Evolutionary Computation Conference (GECCO) 2018: 309-315
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Greedy algorithms provide a fast and often also effective solution to many combinatorial optimization problems. However, it is well known that they sometimes lead to low quality solutions on certain instances. In this paper, we explore the use of randomness in greedy algorithms for the minimum vertex cover and dominating set problem and compare the resulting performance against their deterministic counterpart. Our algorithms are based on a parameter \(\gamma\) which allows to explore the spectrum between uniform and deterministic greedy selection in the steps of the algorithm and our theoretical and experimental investigations point out the benefits of incorporating randomness into greedy algorithms for the two considered combinatorial optimization problems.
  @inproceedings{gao2018randomized, abstract = {Greedy algorithms provide a fast and often also effective solution to many combinatorial optimization problems. However, it is well known that they sometimes lead to low quality solutions on certain instances. In this paper, we explore the use of randomness in greedy algorithms for the minimum vertex cover and dominating set problem and compare the resulting performance against their deterministic counterpart. Our algorithms are based on a parameter \(\gamma\) which allows to explore the spectrum between uniform and deterministic greedy selection in the steps of the algorithm and our theoretical and experimental investigations point out the benefits of incorporating randomness into greedy algorithms for the two considered combinatorial optimization problems.}, author = {Gao, Wanru and Friedrich, Tobias and Neumann, Frank and Hercher, Christian}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {GECCO christianhercher frankneumann tobiasfriedrich wanrugao year2018}, pages = {309-315}, title = {Randomized Greedy Algorithms for Covering Problems}, year = 2018 }
• 
  Doerr, Benjamin; Krejca, Martin S.Significance-based Estimation-of-Distribution Algorithms. Genetic and Evolutionary Computation Conference (GECCO) 2018: 1483-1490
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that maintain a stochastic model of the solution space. This model is updated from iteration to iteration based on the quality of the solutions sampled according to the model. As previous works show, this short-term perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. This can lead to significant performance losses. In order to overcome this problem, we propose a new EDA that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the common benchmark functions OneMax and LeadingOnes both in \(O(n\log n)\) time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA – an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model – we prove that it optimizes OneMax only in a time exponential in the hypothetical population size \(1/\rho\).
  @inproceedings{doerr2018significancebased, abstract = {Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that maintain a stochastic model of the solution space. This model is updated from iteration to iteration based on the quality of the solutions sampled according to the model. As previous works show, this short-term perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. This can lead to significant performance losses. In order to overcome this problem, we propose a new EDA that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the common benchmark functions OneMax and LeadingOnes both in \(O(n\log n)\) time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA – an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model – we prove that it optimizes OneMax only in a time exponential in the hypothetical population size \(1/\rho\).}, author = {Doerr, Benjamin and Krejca, Martin S.}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {GECCO benjamindoerr martinskrejca year2018}, pages = {1483-1490}, title = {Significance-based Estimation-of-Distribution Algorithms}, year = 2018 }
• 
  Issac, Davis; Chandran, L. Sunil; Cheung, Yuen KuengSpanning tree congestion and computation of gyori lovasz partition. International Colloquium on Automata, Languages, and Programming (ICALP) 2018
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, it seeks a spanning tree with no tree-edge routing too many of the original edges. For any general connected graph with n vertices and m edges, we show that its STC is at most \( \mathcal{O(\sqrt{mn}) \), which is asymptotically optimal since we also demonstrate graphs with STC at least \( \Omega(\sqrt{mn}) \). We present a polynomial-time algorithm which computes a spanning tree with congestion \( \mathcal{O(\sqrt{mn}) \log n \) \( \mathcal{O(\sqrt{mn} \log n ) \). We also present another algorithm for computing a spanning tree with congestion \( \mathcal{O(\sqrt{mn}) \); this algorithm runs in sub-exponential time when \(m = \omega(n \log^2 n ) \). For achieving the above results, an important intermediate theorem is generalized Györi-Lovász theorem. Chen et al. [Jiangzhuo Chen et al., 2007] gave a non-constructive proof. We give the first elementary and constructive proof with a local search algorithm of running time \( \mathcal{O^*( 4^n ) \). We discuss some consequences of the theorem concerning graph partitioning, which might be of independent interest. We also show that for any graph which satisfies certain expanding properties, its STC is at most \( \mathcal{O^*(n) \), and a corresponding spanning tree can be computed in polynomial time. We then use this to show that a random graph has STC \( \Theta(n) \) with high probability.
  @inproceedings{icc-stccglp-2018, abstract = {We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, it seeks a spanning tree with no tree-edge routing too many of the original edges. For any general connected graph with n vertices and m edges, we show that its STC is at most \( \mathcal{O}(\sqrt{mn}) \), which is asymptotically optimal since we also demonstrate graphs with STC at least \( \Omega(\sqrt{mn}) \). We present a polynomial-time algorithm which computes a spanning tree with congestion \( \mathcal{O}(\sqrt{mn}) \log n \) \( \mathcal{O}(\sqrt{mn} \log n ) \). We also present another algorithm for computing a spanning tree with congestion \( \mathcal{O}(\sqrt{mn}) \); this algorithm runs in sub-exponential time when \(m = \omega(n \log^2 n ) \). For achieving the above results, an important intermediate theorem is generalized Györi-Lovász theorem. Chen et al. [Jiangzhuo Chen et al., 2007] gave a non-constructive proof. We give the first elementary and constructive proof with a local search algorithm of running time \( \mathcal{O}^*( 4^n ) \). We discuss some consequences of the theorem concerning graph partitioning, which might be of independent interest. We also show that for any graph which satisfies certain expanding properties, its STC is at most \( \mathcal{O}^*(n) \), and a corresponding spanning tree can be computed in polynomial time. We then use this to show that a random graph has STC \( \Theta(n) \) with high probability.}, author = {Issac, Davis and Chandran, L. Sunil and Cheung, Yuen Kueng}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {davisissac icalp lsunilchandran year2018 yuenkuencheung}, title = {Spanning tree congestion and computation of gyori lovasz partition}, year = 2018 }
• 
  Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, MarianneEfficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. International Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1-20:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
  @inproceedings{blasius2018efficient, abstract = {A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.}, author = {Bläsius, Thomas and Freiberger, Cedric and Friedrich, Tobias and Katzmann, Maximilian and Montenegro-Retana, Felix and Thieffry, Marianne}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {cedricfreiberger felixmontenegroretana hyperbolic_analysis icalp mariannethieffry maximiliankatzmann thomasblaesius tobiasfriedrich year2018}, pages = {20:1-20:14}, title = {Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry}, volume = 107, year = 2018 }
• 
  Casel, KatrinResolving Conflicts for Lower-Bounded Clustering. International Symposium on Parameterized and Exact Computation (IPEC) 2018: 23:1-23:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  This paper considers the effect of non-metric distances for lower-bounded clustering, i.e., the problem of computing a partition for a given set of objects with pairwise distance, such that each set has a certain minimum cardinality (as required for anonymisation or balanced facility location problems). We discuss lower-bounded clustering with the objective to minimise the maximum radius or diameter of the clusters. For these problems there exists a 2-approximation but only if the pairwise distance on the objects satisfies the triangle inequality, without this property no polynomial-time constant factor approximation is possible. We try to resolve or at least soften this effect of non-metric distances by devising particular strategies to deal with violations of the triangle inequality ("conflicts"). With parameterised algorithmics, we find that if the number of such conflicts is not too large, constant factor approximations can still be computed efficiently. In particular, we introduce parameterised approximations with respect to not just the number of conflicts but also for the vertex cover number of the "conflict graph" (graph induced by conflicts). Interestingly, we salvage the approximation ratio of 2 for diameter while for radius it is only possible to show a ratio of 3. For the parameter vertex cover number of the conflict graph this worsening in ratio is shown to be unavoidable, unless FPT=W[2]. We further discuss improvements for diameter by choosing the (induced) \(P_3\)-cover number of the conflict graph as parameter and complement these by showing that, unless FPT=W[1], there exists no constant factor parameterised approximation with respect to the parameter split vertex deletion set.
  @inproceedings{casel2018resolving, abstract = {This paper considers the effect of non-metric distances for lower-bounded clustering, i.e., the problem of computing a partition for a given set of objects with pairwise distance, such that each set has a certain minimum cardinality (as required for anonymisation or balanced facility location problems). We discuss lower-bounded clustering with the objective to minimise the maximum radius or diameter of the clusters. For these problems there exists a 2-approximation but only if the pairwise distance on the objects satisfies the triangle inequality, without this property no polynomial-time constant factor approximation is possible. We try to resolve or at least soften this effect of non-metric distances by devising particular strategies to deal with violations of the triangle inequality ("conflicts"). With parameterised algorithmics, we find that if the number of such conflicts is not too large, constant factor approximations can still be computed efficiently. In particular, we introduce parameterised approximations with respect to not just the number of conflicts but also for the vertex cover number of the "conflict graph" (graph induced by conflicts). Interestingly, we salvage the approximation ratio of 2 for diameter while for radius it is only possible to show a ratio of 3. For the parameter vertex cover number of the conflict graph this worsening in ratio is shown to be unavoidable, unless FPT=W[2]. We further discuss improvements for diameter by choosing the (induced) \(P_3\)-cover number of the conflict graph as parameter and complement these by showing that, unless FPT=W[1], there exists no constant factor parameterised approximation with respect to the parameter split vertex deletion set.}, author = {Casel, Katrin}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, keywords = {ipec katrincasel year2018}, pages = {23:1-23:14}, title = {Resolving Conflicts for Lower-Bounded Clustering}, year = 2018 }
• 
  Cucina, Domenico; Rizzo, Manuel; Ursu, EugenIdentification of Multiregime Periodic Autoregressive Models by Genetic Algorithms. International Conference on Time Series and Forecasting (ITISE) 2018: 396-407
  [ Abstract ] [ BibTeX ] [ Download ]
   
  This paper develops a procedure for identifying multiregime Periodic AutoRegressive (PAR) models. In each regime a possibly dif- ferent PAR model is built, for which changes can be due to the seasonal means, the autocorrelation structure or the variances. Number and lo- cations of changepoints which subdivide the time span are detected by means of Genetic Algorithms (GAs), that optimize an identification cri- terion. The method is evaluated by means of simulation studies, and is then employed to analyze shrimp fishery data.
  @inproceedings{cucina2018identification, abstract = {This paper develops a procedure for identifying multiregime Periodic AutoRegressive (PAR) models. In each regime a possibly dif- ferent PAR model is built, for which changes can be due to the seasonal means, the autocorrelation structure or the variances. Number and lo- cations of changepoints which subdivide the time span are detected by means of Genetic Algorithms (GAs), that optimize an identification cri- terion. The method is evaluated by means of simulation studies, and is then employed to analyze shrimp fishery data.}, author = {Cucina, Domenico and Rizzo, Manuel and Ursu, Eugen}, booktitle = {International Conference on Time Series and Forecasting (ITISE)}, keywords = {domenicocucina eugenursu itise manuelrizzo year2018}, pages = {396-407}, title = {Identification of Multiregime Periodic Autoregressive Models by Genetic Algorithms}, volume = 1, year = 2018 }
• 
  Scheibel, Willy; Weyand, Christopher; Döllner, JürgenEvoCells – A Treemap Layout Algorithm for Evolving Tree Data. 9th International Conference on Information Visualization Theory and Applications (IVAPP) 2018: 273-280
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  We propose the rectangular treemap layout algorithm EvoCells that maps changes in tree-structured data onto an initial treemap layout. Changes in topology and node weights are mapped to insertion, removal, growth, and shrinkage of the layout rectangles. Thereby, rectangles displace their neighbors and stretch their enclosing rectangles with a run-time complexity of O(nlogn). An evaluation using layout stability metrics on the opensource ElasticSearch software system suggests EvoCells as a valid alternative for stable treemap layouting.
  @inproceedings{STD2018, abstract = {We propose the rectangular treemap layout algorithm EvoCells that maps changes in tree-structured data onto an initial treemap layout. Changes in topology and node weights are mapped to insertion, removal, growth, and shrinkage of the layout rectangles. Thereby, rectangles displace their neighbors and stretch their enclosing rectangles with a run-time complexity of O(nlogn). An evaluation using layout stability metrics on the opensource ElasticSearch software system suggests EvoCells as a valid alternative for stable treemap layouting.}, author = {Scheibel, Willy and Weyand, Christopher and Döllner, Jürgen}, booktitle = {9th International Conference on Information Visualization Theory and Applications (IVAPP)}, keywords = {christopherweyand}, organization = {INSTICC}, pages = {273-280}, publisher = {SciTePress}, title = {EvoCells – A Treemap Layout Algorithm for Evolving Tree Data}, volume = 3, year = 2018 }
• 
  Issac, Davis; van Leeuwen, Erik Jan; Das, Anita; Chandran, L. SunilAlgorithms and bounds for very strong rainbow coloring. Latin American Symposium on Theoretical Informatics Conference (LATIN) 2018
  [ Abstract ] [ BibTeX ] [ Download ]
   
  A well-studied coloring problem is to assign colors to the edges of a graph G so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number (\(\mathbf{src(G) \)) of the graph. When proving upper bounds on \(\mathbf{src(G) \), it is natural to prove that a coloring exists where, for every shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call very strong rainbow connection number (\(\mathbf{vsrc(G) \)). In this paper, we give upper bounds on \(\mathbf{vsrc(G) \) for several graph classes, some of which are tight. These immediately imply new upper bounds on \(\mathbf{src(G) \) for these classes, showing that the study of \(\mathbf{vsrc(G) \) enables meaningful progress on bounding \(\mathbf{src(G) \). Then we study the complexity of the problem to compute \(\mathbf{vsrc(G) \), particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that \(\mathbf{vsrc(G) \) can be computed in polynomial time on cactus graphs; in contrast, this question is still open for \(\mathbf{src(G) \). We also observe that deciding whether \(\mathbf{vsrc(G) = k \) is fixed-parameter tractable in k and the treewidth of G. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether \(\mathbf{vsrc(G) \leq 3 \) nor to approximate \(\mathbf{vsrc(G) \) within a factor \( n^1-\varepsilon \), unless P = NP.
  @inproceedings{ildc-abvsrc-2018, abstract = {A well-studied coloring problem is to assign colors to the edges of a graph G so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number (\(\mathbf{src}(G) \)) of the graph. When proving upper bounds on \(\mathbf{src}(G) \), it is natural to prove that a coloring exists where, for every shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call very strong rainbow connection number (\(\mathbf{vsrc}(G) \)). In this paper, we give upper bounds on \(\mathbf{vsrc}(G) \) for several graph classes, some of which are tight. These immediately imply new upper bounds on \(\mathbf{src}(G) \) for these classes, showing that the study of \(\mathbf{vsrc}(G) \) enables meaningful progress on bounding \(\mathbf{src}(G) \). Then we study the complexity of the problem to compute \(\mathbf{vsrc}(G) \), particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that \(\mathbf{vsrc}(G) \) can be computed in polynomial time on cactus graphs; in contrast, this question is still open for \(\mathbf{src}(G) \). We also observe that deciding whether \(\mathbf{vsrc}(G) = k \) is fixed-parameter tractable in k and the treewidth of G. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether \(\mathbf{vsrc}(G) \leq 3 \) nor to approximate \(\mathbf{vsrc}(G) \) within a factor \( n^{1-\varepsilon} \), unless P = NP.}, author = {Issac, Davis and van Leeuwen, Erik Jan and Das, Anita and Chandran, L. Sunil}, booktitle = {Latin American Symposium on Theoretical Informatics Conference (LATIN)}, keywords = {anitadas davisissac erikjanvanleeuwen latin lsunilchandran year2018}, title = {Algorithms and bounds for very strong rainbow coloring}, year = 2018 }
• 
  Issac, Davis; van Leeuwen, Erik Jan; Lauri, Juho; Lima, Paloma; Heggernes, PinarRainbow Vertex Coloring Bipartite Graphs and Chordal Graphs. Mathematical Foundations of Computer Science (MFCS) 2018
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.
  @inproceedings{illlh-rvcbgcg-2018, abstract = {Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.}, author = {Issac, Davis and van Leeuwen, Erik Jan and Lauri, Juho and Lima, Paloma and Heggernes, Pinar}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, keywords = {davisissac erikjanvanleeuwen juholauri mfcs palomalima pinarheggernes year2018}, title = {Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs}, year = 2018 }
• 
  Göbel, Andreas; Lagodzinski, J. A. Gregor; Seidel, KarenCounting Homomorphisms to Trees Modulo a Prime. Mathematical Foundations of Computer Science (MFCS) 2018: 49:1-49:13
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article we study the complexity of~\($\#_p\textsc{HomsTo}H$\), the problem of counting graph homomorphisms from an input graph to a graph \($H$\) modulo a prime number~\($p$\). Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo~\($2$\), however, the influence of the structure of~\($H$\) on the tractability was shown to persist, which yields similar dichotomies. Our main result states that for every tree~\($H$\) and every prime~\($p$\) the problem \($\#_p\textsc{HomsTo}H$\) is either polynomial time computable or \($\#_p\mathsf{P}$\)-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph \($H$\) when counting modulo~2. In contrast to previous results on modular counting, the tractable cases of \($\#_p\textsc{HomsTo}H$\) are essentially the same for all values of the modulo when \($H$\) is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime~\($p$\). These results are the first suggesting that such dichotomies hold not only for the one-bit functions of the modulo~2 case but also for the modular counting functions of all primes~\($p$\).
  @inproceedings{gobel2018counting, abstract = {Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article we study the complexity of~$\#_p\textsc{HomsTo}H$, the problem of counting graph homomorphisms from an input graph to a graph $H$ modulo a prime number~$p$. Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo~$2$, however, the influence of the structure of~$H$ on the tractability was shown to persist, which yields similar dichotomies. Our main result states that for every tree~$H$ and every prime~$p$ the problem $\#_p\textsc{HomsTo}H$ is either polynomial time computable or $\#_p\mathsf{P}$-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph $H$ when counting modulo~2. In contrast to previous results on modular counting, the tractable cases of $\#_p\textsc{HomsTo}H$ are essentially the same for all values of the modulo when $H$ is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime~$p$. These results are the first suggesting that such dichotomies hold not only for the one-bit functions of the modulo~2 case but also for the modular counting functions of all primes~$p$.}, author = {Göbel, Andreas and Lagodzinski, J. A. Gregor and Seidel, Karen}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, keywords = {andreasgoebel gregorlagodzinski karenseidel mfcs year2018}, pages = {49:1-49:13}, publisher = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Counting Homomorphisms to Trees Modulo a Prime}, volume = 117, year = 2018 }
• 
  Kötzing, Timo; Lagodzinski, J. A. Gregor; Lengler, Johannes; Melnichenko, AnnaDestructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming. Parallel Problem Solving From Nature (PPSN) 2018: 42-54
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had a surprisingly little share in this work. We analyze a simple crossover operator in combination with local search,where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); the resulting algorithm is denoted ConcatenationCrossover GP. For this purpose three variants of the well-studied Majority test function with large plateaus are considered. We show that the Concatenation Crossover GP can efficiently optimize these test functions,while local search cannot be efficient for all three variants independent of employing bloat control.
  @inproceedings{kotzing2018destructiveness, abstract = {For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant parts). Second, the role and realization of crossover, which is particularly central in GP due to the tree-based representation. Whereas some theoretical work on GP has studied the effects of bloat, crossover had a surprisingly little share in this work. We analyze a simple crossover operator in combination with local search,where a preference for small solutions minimizes bloat (lexicographic parsimony pressure); the resulting algorithm is denoted ConcatenationCrossover GP. For this purpose three variants of the well-studied Majority test function with large plateaus are considered. We show that the Concatenation Crossover GP can efficiently optimize these test functions,while local search cannot be efficient for all three variants independent of employing bloat control.}, author = {Kötzing, Timo and Lagodzinski, J. A. Gregor and Lengler, Johannes and Melnichenko, Anna}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {annamelnichenko gregorlagodzinski johanneslengler ppsn timokoetzing year2018}, pages = {42-54}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming}, volume = 11102, year = 2018 }
• 
  Kötzing, Timo; Krejca, Martin S.First-Hitting Times for Finite State Spaces. Parallel Problem Solving From Nature (PPSN) 2018: 79-91
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  One of the most important aspects of a randomized algorithm is bounding its expected run time on various problems. Formally speaking, this means bounding the expected first-hitting time of a random process. The two arguably most popular tools to do so are the fitness level method and drift theory. The fitness level method considers arbitrary transition probabilities but only allows the process to move toward the goal. On the other hand, drift theory allows the process to move into any direction as long as it moves closer to the goal in expectation; however, this tendency has to be monotone and, thus, the transition probabilities cannot be arbitrary. We provide a result that combines the benefit of these two approaches: our result gives a lower and an upper bound for the expected first-hitting time of a random process over \(\{0, \ldots ,n\}\) that is allowed to move forward and backward by 1 and can use arbitrary transition probabilities. In case that the transition probabilities are known, our bounds coincide and yield the exact value of the expected first-hitting time. Further, we also state the stationary distribution as well as the mixing time of a special case of our scenario.
  @inproceedings{kotzing2018firsthitting, abstract = {One of the most important aspects of a randomized algorithm is bounding its expected run time on various problems. Formally speaking, this means bounding the expected first-hitting time of a random process. The two arguably most popular tools to do so are the fitness level method and drift theory. The fitness level method considers arbitrary transition probabilities but only allows the process to move toward the goal. On the other hand, drift theory allows the process to move into any direction as long as it moves closer to the goal in expectation; however, this tendency has to be monotone and, thus, the transition probabilities cannot be arbitrary. We provide a result that combines the benefit of these two approaches: our result gives a lower and an upper bound for the expected first-hitting time of a random process over \(\{0, \ldots ,n\}\) that is allowed to move forward and backward by 1 and can use arbitrary transition probabilities. In case that the transition probabilities are known, our bounds coincide and yield the exact value of the expected first-hitting time. Further, we also state the stationary distribution as well as the mixing time of a special case of our scenario.}, author = {Kötzing, Timo and Krejca, Martin S.}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {martinskrejca ppsn timokoetzing year2018}, pages = {79-91}, title = {First-Hitting Times for Finite State Spaces}, year = 2018 }
• 
  Kötzing, Timo; Krejca, Martin S.First-Hitting Times Under Additive Drift. Parallel Problem Solving From Nature (PPSN) 2018: 92-104
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process – the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be nonnegative, that is, we remove unnecessary restrictions like a finite, discrete, or bounded search space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift
  @inproceedings{kotzingyear2018firsthitting, abstract = {For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process – the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be nonnegative, that is, we remove unnecessary restrictions like a finite, discrete, or bounded search space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift}, author = {Kötzing, Timo and Krejca, Martin S.}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {martinskrejca ppsn timokoetzing year2018}, pages = {92-104}, title = {First-Hitting Times Under Additive Drift}, year = 2018 }
• 
  Frahnow, Clemens; Kötzing, TimoRing Migration Topology Helps Bypassing Local Optima. Parallel Problem Solving From Nature (PPSN) 2018: 129-140
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Running several evolutionary algorithms in parallel and occasionally exchanging good solutions is referred to as island models. The idea is that the independence of the different islands leads to diversity, thus possibly exploring the search space better. Many theoretical analyses so far have found a complete (or sufficiently quickly expanding) topology as underlying migration graph most efficient for optimization, even though a quick dissemination of individuals leads to a loss of diversity. We suggest a simple fitness function Fork with two local optima parametrized by \(r \geq 2\) and a scheme for composite fitness functions. We show that, while the (1+1) EA gets stuck in a bad local optimum and incurs a run time of \(\Theta(n^{2r})\) fitness evaluations on Fork, island models with a complete topology can achieve a run time of \(\Theta(n^{1.5r})\) by making use of rare migrations in order to explore the search space more effectively. Finally, the ring topology, making use of rare migrations and a large diameter, can achieve a run time of \(\tilde{\Theta}(n^r)\), the black box complexity of Fork. This shows that the ring topology can be preferable over the complete topology in order to maintain diversity.
  @inproceedings{frahnow2018migration, abstract = {Running several evolutionary algorithms in parallel and occasionally exchanging good solutions is referred to as island models. The idea is that the independence of the different islands leads to diversity, thus possibly exploring the search space better. Many theoretical analyses so far have found a complete (or sufficiently quickly expanding) topology as underlying migration graph most efficient for optimization, even though a quick dissemination of individuals leads to a loss of diversity. We suggest a simple fitness function Fork with two local optima parametrized by \(r \geq 2\) and a scheme for composite fitness functions. We show that, while the (1+1) EA gets stuck in a bad local optimum and incurs a run time of \(\Theta(n^{2r})\) fitness evaluations on Fork, island models with a complete topology can achieve a run time of \(\Theta(n^{1.5r})\) by making use of rare migrations in order to explore the search space more effectively. Finally, the ring topology, making use of rare migrations and a large diameter, can achieve a run time of \(\tilde{\Theta}(n^r)\), the black box complexity of Fork. This shows that the ring topology can be preferable over the complete topology in order to maintain diversity.}, author = {Frahnow, Clemens and Kötzing, Timo}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {clemensfrahnow islands ppsn timokoetzing year2018}, pages = {129-140}, series = {Lecture Notes in Computer Science}, title = {Ring Migration Topology Helps Bypassing Local Optima}, volume = 11102, year = 2018 }
• 
  Friedrich, Tobias; Göbel, Andreas; Quinzan, Francesco; Wagner, MarkusHeavy-tailed Mutation Operators in Single-Objective Combinatorial Optimization. Parallel Problem Solving From Nature (PPSN) 2018: 134-145
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A core feature of evolutionary algorithms is their mutation operator. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this line of work, we propose a new mutation operator and analyze its performance on the (1+1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1+1)EA on classes of problems for which results on the other mutation operators are available. We present a jump function for which the performance of the (1+1)EA using any static uniform mutation and any restart strategy can be worse than the performance of the (1+1)EA using our mutation operator with no restarts. We show that the (1+1)EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve this problem. Finally, we evaluate experimentally the performance of the (1+1)EA using our operator, on real-world graphs of different origins with up to \(\sim\)37,000 vertices and \(\sim\)1.6 million edges. In comparison with uniform mutation and a recently proposed dynamic scheme our operator comes out on top on these instances.
  @inproceedings{friedrich2018heavytailed, abstract = {A core feature of evolutionary algorithms is their mutation operator. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this line of work, we propose a new mutation operator and analyze its performance on the (1+1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1+1)EA on classes of problems for which results on the other mutation operators are available. We present a jump function for which the performance of the (1+1)EA using any static uniform mutation and any restart strategy can be worse than the performance of the (1+1)EA using our mutation operator with no restarts. We show that the (1+1)EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve this problem. Finally, we evaluate experimentally the performance of the (1+1)EA using our operator, on real-world graphs of different origins with up to \(\sim\)37\,000 vertices and \(\sim\)1.6 million edges. In comparison with uniform mutation and a recently proposed dynamic scheme our operator comes out on top on these instances.}, author = {Friedrich, Tobias and Göbel, Andreas and Quinzan, Francesco and Wagner, Markus}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {andreasgoebel francescoquinzan markuswagner ppsn tobiasfriedrich year2018}, pages = {134-145}, title = {Heavy-tailed Mutation Operators in Single-Objective Combinatorial Optimization}, year = 2018 }
• 
  Chauhan, Ankit; Lenzner, Pascal; Molitor, LouiseSchelling Segregation with Strategic Agents. Symposium on Algorithmic Game Theory (SAGT) 2018
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Schelling’s segregation model is a landmark model in sociology. It shows the counter-intuitive phenomenon that residential segregation between individuals of different groups can emerge even when all involved individuals are tolerant. Although the model is widely studied, no pure game-theoretic version where rational agents strategically choose their location exists. We close this gap by introducing and analyzing generalized game-theoretic models of Schelling segregation, where the agents can also have individual location preferences. For our models we investigate the convergence behavior and the efficiency of their equilibria. In particular, we prove guaranteed convergence to an equilibrium in the version which is closest to Schelling’s original model. Moreover, we provide tight bounds on the Price of Anarchy.
  @inproceedings{chauhan2018schelling, abstract = {Schelling’s segregation model is a landmark model in sociology. It shows the counter-intuitive phenomenon that residential segregation between individuals of different groups can emerge even when all involved individuals are tolerant. Although the model is widely studied, no pure game-theoretic version where rational agents strategically choose their location exists. We close this gap by introducing and analyzing generalized game-theoretic models of Schelling segregation, where the agents can also have individual location preferences. For our models we investigate the convergence behavior and the efficiency of their equilibria. In particular, we prove guaranteed convergence to an equilibrium in the version which is closest to Schelling’s original model. Moreover, we provide tight bounds on the Price of Anarchy.}, author = {Chauhan, Ankit and Lenzner, Pascal and Molitor, Louise}, booktitle = {Symposium on Algorithmic Game Theory (SAGT)}, keywords = {ankitchauhan louisemolitor pascallenzner sagt year2018}, title = {Schelling Segregation with Strategic Agents}, year = 2018 }
• 
  Cseh, Ágnes; Fleiner, TamásThe Complexity of Cake Cutting with Unequal Shares. Symposium Algorithmic Game Theory (SAGT) 2018: 19-30
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
   
  An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this paper, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.
  @inproceedings{cseh2018complexity, abstract = {An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. In this paper, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.}, author = {Cseh, Ágnes and Fleiner, Tamás}, booktitle = {Symposium Algorithmic Game Theory (SAGT)}, keywords = {sys:relevantfor:ae agnescseh bestpaper sagt tamasfleiner year2018}, pages = {19-30}, title = {The Complexity of Cake Cutting with Unequal Shares}, year = 2018 }
• 
  Friedrich, Tobias; Rothenberger, RalfSharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT. Theory and Applications of Satisfiability Testing (SAT) 2018: 273-291

  Best Paper Award
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\|p\|_2^2 = O_n(t^{-2/k})\) and \(\|p\|_\infty\) \(= o_n(t^-k/(2k-1) \log^{-(k-1)/(2k-1)(t))\). This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.
  @inproceedings{friedrich2018sharpness, abstract = {We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\|p\|_2^2 = O_n(t^{-2/k})\) and \(\|p\|_\infty\) \(= o_n(t^{-k/(2k-1)} \log^{-(k-1)/(2k-1)}(t))\). This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.}, author = {Friedrich, Tobias and Rothenberger, Ralf}, booktitle = {Theory and Applications of Satisfiability Testing (SAT)}, keywords = {bestpaper ralfrothenberger sat scalefree_sat tobiasfriedrich year2018}, note = {Best Paper Award}, pages = {273-291}, title = {Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT}, year = 2018 }
• 
  Battaglia, Francesco; Cucina, Domenico; Rizzo, ManuelGeneralized Periodic Autoregressive Models for Trend and Seasonality Varying Time Series. Scientific Meeting of the Italian Statistical Society (SIS) 2018
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Many nonstationary time series exhibit changes in the trend and seasonality structure, that may be modeled by splitting the time axis into different regimes. We propose multi-regime models where, inside each regime, the trend is linear and seasonality is explained by a Periodic Autoregressive model. In addition, for achieving parsimony, we allow season grouping, i.e. seasons may consist of one, two, or more consecutive observations. Identification is obtained by means of a Genetic Algorithm that minimizes an identification criterion.
  @inproceedings{battagliageneralized, abstract = {Many nonstationary time series exhibit changes in the trend and seasonality structure, that may be modeled by splitting the time axis into different regimes. We propose multi-regime models where, inside each regime, the trend is linear and seasonality is explained by a Periodic Autoregressive model. In addition, for achieving parsimony, we allow season grouping, i.e. seasons may consist of one, two, or more consecutive observations. Identification is obtained by means of a Genetic Algorithm that minimizes an identification criterion.}, author = {Battaglia, Francesco and Cucina, Domenico and Rizzo, Manuel}, booktitle = {Scientific Meeting of the Italian Statistical Society (SIS)}, keywords = {domenicocucina francescobattaglia manuelrizzo sis year2018}, title = {Generalized Periodic Autoregressive Models for Trend and Seasonality Varying Time Series}, year = 2018 }
• 
  Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, JustinMemory-restricted Routing With Tiled Map Data. Systems, Man, and Cybernetics (SMC) 2018: 3347-3354
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.
  @inproceedings{blasius2018memory, abstract = {Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.}, author = {Bläsius, Thomas and Eube, Jan and Feldtkeller, Thomas and Friedrich, Tobias and Krejca, Martin S. and Lagodzinski, J. A. Gregor and Rothenberger, Ralf and Severin, Julius and Sommer, Fabian and Trautmann, Justin}, booktitle = {Systems, Man, and Cybernetics (SMC)}, keywords = {fabiansommer gregorlagodzinski janeube juliusseverin justintrautmann martinskrejca ralfrothenberger smc thomasblaesius thomasfeldtkeller tobiasfriedrich year2018}, month = 10, pages = {3347-3354}, title = {Memory-restricted Routing With Tiled Map Data}, year = 2018 }
• 
  Bilò, Davide; Lenzner, PascalOn the Tree Conjecture for the Network Creation Game. Symposium on the Theoretical Aspects of Computer Science (STACS) 2018: 14:1-14:15
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. [PODC'03] is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all \($\alpha$\) and that for \($\alpha \geq n$\) all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bounds for both conjectures. In particular we show that for \($\alpha > 4n-13$\) all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.
  @inproceedings{bil2018conjecture, abstract = {Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. [PODC'03] is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all $\alpha$ and that for $\alpha \geq n$ all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bounds for both conjectures. In particular we show that for $\alpha > 4n-13$ all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.}, author = {Bilò, Davide and Lenzner, Pascal}, booktitle = {Symposium on the Theoretical Aspects of Computer Science (STACS)}, keywords = {pascallenzner stacs year2018}, pages = {14:1-14:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, title = {On the Tree Conjecture for the Network Creation Game}, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton; Striebel, JonathanTowards a Systematic Evaluation of Generative Network Models. Workshop on Algorithms and Models for the Web Graph (WAW) 2018: 99-114
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters. As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.
  @inproceedings{blasius2018towards, abstract = {Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters. As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton and Striebel, Jonathan}, booktitle = {Workshop on Algorithms and Models for the Web Graph (WAW)}, keywords = {antonkrohmer jonathanstriebel maximiliankatzmann thomasblaesius tobiasfriedrich waw year2018}, pages = {99-114}, title = {Towards a Systematic Evaluation of Generative Network Models}, year = 2018 }

2018

• 
  Issac, Davis; Bhattacharya, Anup; Kumar, Amit; Jaiswal, RageshSampling in space restricted settings. Algorithmica 2018: 1439-1458
  [ Abstract ] [ BibTeX ] [ URL ] [ Download ]
   
  Space efficient algorithms play an important role in dealing with large amount of data. In such settings, one would like to analyze the large data using small amount of “working space”. One of the key steps in many algorithms for analyzing large data is to maintain a (or a small number) random sample from the data points. In this paper, we consider two space restricted settings-(i) the streaming model, where data arrives over time and one can use only a small amount of storage, and (ii) the query model, where we can structure the data in low space and answer sampling queries. In this paper, we prove the following results in the above two settings: \begin{itemize item In the streaming setting, we would like to maintain a random sample from the elements seen so far. We prove that one can maintain a random sample using \( \mathcal{O(\log n) \) random bits and \( \mathcal{O(\log n) \) bits of space, where n is the number of elements seen so far. We can extend this to the case when elements have weights as well. item In the query model, there are n elements with weights \(w_1, \dots, w_n \) (which are w-bit integers) and one would like to sample a random element with probability proportional to its weight. Bringmann and Larsen (STOC 2013) showed how to sample such an element using \(n \omega + 1\) bits of space (whereas, the information theoretic lower bound is \(n \omega \)). We consider the approximate sampling problem, where we are given an error parameter \( \varepsilon \), and the sampling probability of an element can be off by an \( \varepsilon \) factor. We give matching upper and lower bounds for this problem. \end{itemize
  @article{ibkj-ssrs-2018, abstract = {Space efficient algorithms play an important role in dealing with large amount of data. In such settings, one would like to analyze the large data using small amount of “working space”. One of the key steps in many algorithms for analyzing large data is to maintain a (or a small number) random sample from the data points. In this paper, we consider two space restricted settings-(i) the streaming model, where data arrives over time and one can use only a small amount of storage, and (ii) the query model, where we can structure the data in low space and answer sampling queries. In this paper, we prove the following results in the above two settings: \begin{itemize} \item In the streaming setting, we would like to maintain a random sample from the elements seen so far. We prove that one can maintain a random sample using \( \mathcal{O}(\log n) \) random bits and \( \mathcal{O}(\log n) \) bits of space, where n is the number of elements seen so far. We can extend this to the case when elements have weights as well. \item In the query model, there are n elements with weights \(w_1, \dots, w_n \) (which are w-bit integers) and one would like to sample a random element with probability proportional to its weight. Bringmann and Larsen (STOC 2013) showed how to sample such an element using \(n \omega + 1\) bits of space (whereas, the information theoretic lower bound is \(n \omega \)). We consider the approximate sampling problem, where we are given an error parameter \( \varepsilon \), and the sampling probability of an element can be off by an \( \varepsilon \) factor. We give matching upper and lower bounds for this problem. \end{itemize}}, author = {Issac, Davis and Bhattacharya, Anup and Kumar, Amit and Jaiswal, Ragesh}, booktitle = {Algorithmica}, keywords = {sys:relevantfor:ae algorithmica amitkumar anupbhattacharya davisissac rageshjaiswal year2018}, month = {June}, pages = {1439-1458}, title = {Sampling in space restricted settings}, volume = 80, year = 2018 }
• 
  Arulselvan, Ashwin; Cseh, Ágnes; Groß, Martin; Manlove, David F.; Matuschke, JannikMatchings with Lower Quotas: Algorithms and Complexity. Algorithmica 2018: 185-208
  [ 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 classical 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]. The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee \($u_{\max}+1$\), which is asymptotically best possible unless \($P=NP$\). Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.
  @article{arulselvan2018matchings, 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 classical 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]. The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee $u_{\max}+1$, which is asymptotically best possible unless $P=NP$. Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.}, author = {Arulselvan, Ashwin and Cseh, Ágnes and Groß, Martin and Manlove, David F. and Matuschke, Jannik}, journal = {Algorithmica}, keywords = {sys:relevantfor:ae agnescseh algorithmica ashwinarulselvan davidfmanlove jannikmatuschke martingross year2018}, pages = {185-208}, title = {Matchings with Lower Quotas: Algorithms and Complexity}, year = 2018 }
• 
  Bläsius, Thomas; Karrer, Annette; Rutter, IgnazSimultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. Algorithmica 2018: 1214-1277
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 ∩ G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem SEFE). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given SEFE instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^∪ = G^1 ∪ G^2\) , (2) most separating pairs of \(G^∪\), and (3) connected components of G that are biconnected but not a cycle. Second, we give an \(O(n³)\)-time algorithm solving Sefe for instances with the following restriction. Let u be a pole of a P-node \(µ\) in the SPQR-tree of a block of \(G^1\) or \(G^2\). Then at most three virtual edges of \(µ\) may contain common edges incident to u. All algorithms extend to the sunflower case, i.e., to the case of more than two graphs pairwise intersecting in the same common graph.
  @article{blsius2018simultaneous, abstract = {A simultaneous embedding (with fixed edges) of two graphs \(G^1\) and \(G^2\) with common graph \(G = G^1 ∩ G^2\) is a pair of planar drawings of \(G^1\) and \(G^2\) that coincide on \(G\). It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem SEFE). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given SEFE instance, producing a set of equivalent Sefe instances without such substructures. The structures we can remove are (1) cutvertices of the union graph \(G^∪ = G^1 ∪ G^2\) , (2) most separating pairs of \(G^∪\), and (3) connected components of G that are biconnected but not a cycle. Second, we give an \(O(n³)\)-time algorithm solving Sefe for instances with the following restriction. Let u be a pole of a P-node \(µ\) in the SPQR-tree of a block of \(G^1\) or \(G^2\). Then at most three virtual edges of \(µ\) may contain common edges incident to u. All algorithms extend to the sunflower case, i.e., to the case of more than two graphs pairwise intersecting in the same common graph.}, author = {Bläsius, Thomas and Karrer, Annette and Rutter, Ignaz}, journal = {Algorithmica}, keywords = {algorithmica thomasblaesius year2018}, number = 4, pages = {1214-1277}, title = {Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices}, volume = 80, year = 2018 }
• 
  Kötzing, Timo; Sudholt, DirkPreface to the Special Issue on Theory of Genetic and Evolutionary Computation. Algorithmica 2018: 1575-1578
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Evolutionary algorithms (EAs) are randomized search heuristics that can be employed to solve complex optimization problems, including multimodal or highly constrained problems. EAs work by mimicking principles from natural evolution: maintaining a collection of possible solutions (a population) and iteratively creating variants of the individuals (the offspring) and then choosing a new set of individuals for the next iteration (selection). EAs are popular because they represent general-purpose optimizers that can be easily applied to various problems, even in cases where little or no in-depth knowledge about the problem is available. In order to guide practitioners devising new and effective algorithms, theoretical computer scientists employ methods from the field of randomized algorithms to analyze the working principles of EAs with mathematical rigor. Key questions concern the impact of parameter choices (such as, for example, the offspring size or the choice of variation operators) as well as foundational work on developing powerful analysis methods. The theory track of the annual ACM Genetic and Evolutionary Computation Conference (GECCO) is the first tier event for advances in this direction. In this special issue six selected papers from the 2016 edition of the GECCO theory track are collected, each one of them carefully revised and extended to meet the high quality standards of Algorithmica.
  @article{DBLP:journals/algorithmica/KotzingS18, abstract = {Evolutionary algorithms (EAs) are randomized search heuristics that can be employed to solve complex optimization problems, including multimodal or highly constrained problems. EAs work by mimicking principles from natural evolution: maintaining a collection of possible solutions (a population) and iteratively creating variants of the individuals (the offspring) and then choosing a new set of individuals for the next iteration (selection). EAs are popular because they represent general-purpose optimizers that can be easily applied to various problems, even in cases where little or no in-depth knowledge about the problem is available. In order to guide practitioners devising new and effective algorithms, theoretical computer scientists employ methods from the field of randomized algorithms to analyze the working principles of EAs with mathematical rigor. Key questions concern the impact of parameter choices (such as, for example, the offspring size or the choice of variation operators) as well as foundational work on developing powerful analysis methods. The theory track of the annual ACM Genetic and Evolutionary Computation Conference (GECCO) is the first tier event for advances in this direction. In this special issue six selected papers from the 2016 edition of the GECCO theory track are collected, each one of them carefully revised and extended to meet the high quality standards of Algorithmica.}, author = {Kötzing, Timo and Sudholt, Dirk}, journal = {Algorithmica}, keywords = {algorithmica timokoetzing year2018}, number = 5, pages = {1575-1578}, title = {Preface to the Special Issue on Theory of Genetic and Evolutionary Computation}, volume = 80, year = 2018 }
• 
  Doerr, Benjamin; Doerr, Carola; Kötzing, TimoStatic and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables. Algorithmica 2018: 1732-1768
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The most common representation in evolutionary computation are bit strings. With very little theoretical work existing on how to use evolutionary algorithms for decision variables taking more than two values, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over \(\Omega={0,1,\dots,r−1}^n\). We observe a crucial difference in how we extend the one-bit-flip and standard-bit mutation operators to the multi-valued domain. While it is natural to modify a random position of the string or select each position of the solution vector for modification independently with probability \(1/n\), there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of \(\Theta(n r \log n)\). If we change each selected position by \(+1\) or \(−1\) (random choice), the optimization time reduces to \(\Theta(n r + n \log n)\). If we use a random mutation strength \(i \in {0,1,\dots,r−1}\) with probability inversely proportional to \(i\) and change the selected position by \(+i\) or \(−i\) (random choice), then the optimization time becomes \(\Theta(n \log(r)(\log n + \log r))\), which is asymptotically faster than the previous if \(r = \omega(\log(n)\log\log(n))\). Interestingly, a better expected performance can be achieved with a self-adjusting mutation strength that is based on the success of previous iterations. For the mutation operator that modifies a randomly chosen position, we show that the self-adjusting mutation strength yields an expected optimization time of \(\Theta(n(\log n + \log r))\), which is best possible among all dynamic mutation strengths. In our proofs, we use a new multiplicative drift theorem for computing lower bounds, which is not restricted to processes that move only towards the target.
  @article{DBLP:journals/algorithmica/DoerrDK18, abstract = {The most common representation in evolutionary computation are bit strings. With very little theoretical work existing on how to use evolutionary algorithms for decision variables taking more than two values, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over \(\Omega={0,1,\dots,r−1}^n\). We observe a crucial difference in how we extend the one-bit-flip and standard-bit mutation operators to the multi-valued domain. While it is natural to modify a random position of the string or select each position of the solution vector for modification independently with probability \(1/n\), there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of \(\Theta(n r \log n)\). If we change each selected position by \(+1\) or \(−1\) (random choice), the optimization time reduces to \(\Theta(n r + n \log n)\). If we use a random mutation strength \(i \in {0,1,\dots,r−1}\) with probability inversely proportional to \(i\) and change the selected position by \(+i\) or \(−i\) (random choice), then the optimization time becomes \(\Theta(n \log(r)(\log n + \log r))\), which is asymptotically faster than the previous if \(r = \omega(\log(n)\log\log(n))\). Interestingly, a better expected performance can be achieved with a self-adjusting mutation strength that is based on the success of previous iterations. For the mutation operator that modifies a randomly chosen position, we show that the self-adjusting mutation strength yields an expected optimization time of \(\Theta(n(\log n + \log r))\), which is best possible among all dynamic mutation strengths. In our proofs, we use a new multiplicative drift theorem for computing lower bounds, which is not restricted to processes that move only towards the target.}, author = {Doerr, Benjamin and Doerr, Carola and Kötzing, Timo}, journal = {Algorithmica}, keywords = {algorithmica benjamindoerr caroladoerr timokoetzing year2018}, number = 5, pages = {1732-1768}, title = {Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables}, volume = 80, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, AntonCliques in Hyperbolic Random Graphs. Algorithmica 2018: 2324-2344
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  Most complex real world networks display scale-free features. This characteristic 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 Krioukov et al. 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 \(\beta = 3\). More precisely, for \(\beta\)\(\in\)\((2,3)\) we prove \(E[K_k] = \) \(n^{k(3-\beta)/2} \Theta(k)^{-k}\) and \(\omega(G) = \) \(\Theta\)\((n^{(3-\beta)/2})\), while for \(\beta \geq 3\) we prove \(E[K_k]=n \Theta(k)^{-k}\) and \(\omega(G)=\Theta(\log(n)/ \log\log n)\). Furthermore, we show that for \(\beta \geq 3\), cliques in hyperbolic random graphs can be computed in time \(O(n)\). If the underlying geometry is known, cliques can be found with worst-case runtime \(O(m n^{2.5})\) for all values of \(\beta\).
  @article{journals/algorithmica/Blasius0K18, abstract = {Most complex real world networks display scale-free features. This characteristic 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 Krioukov et al. 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 \(\beta = 3\). More precisely, for \(\beta\)\(\in\)\((2,3)\) we prove \(E[K_k] = \) \(n^{k(3-\beta)/2} \Theta(k)^{-k}\) and \(\omega(G) = \) \(\Theta\)\((n^{(3-\beta)/2})\), while for \(\beta \geq 3\) we prove \(E[K_k]=n \Theta(k)^{-k}\) and \(\omega(G)=\Theta(\log(n)/ \log\log n)\). Furthermore, we show that for \(\beta \geq 3\), cliques in hyperbolic random graphs can be computed in time \(O(n)\). If the underlying geometry is known, cliques can be found with worst-case runtime \(O(m n^{2.5})\) for all values of \(\beta\).}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton}, journal = {Algorithmica}, keywords = {algorithmica antonkrohmer hyperbolic_analysis thomasblaesius tobiasfriedrich year2018}, pages = {2324-2344}, title = {Cliques in Hyperbolic Random Graphs}, volume = 80, year = 2018 }
• 
  Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, HenningClustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework. Algorithmica 2018: 2517-2550
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios, however, the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality \(k\) without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to \(k\). Further, we derive some polynomial-time solvable cases for \(k=2\) with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of \(k\).
  @article{abukhzam2018clustering, abstract = {Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios, however, the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality \(k\) without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to \(k\). Further, we derive some polynomial-time solvable cases for \(k=2\) with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of \(k\).}, author = {Abu-Khzam, Faisal N. and Bazgan, Cristina and Casel, Katrin and Fernau, Henning}, journal = {Algorithmica}, keywords = {algorithmica cristinabazgan faisalnabukhzam henningfernau katrincasel year2018}, number = 9, pages = {2517-2550}, title = {Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework}, volume = 80, year = 2018 }
• 
  Bringmann, Karl; Friedrich, Tobias; Krohmer, AntonDe-anonymization of Heterogeneous Random Graphs in Quasilinear Time. Algorithmica 2018: 3397–3427
  [ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
   
  There are hundreds of online social networks with altogether billions of users. Many such networks publicly release structural information, with all personal information removed. Empirical studies have shown, however, that this provides a false sense of privacy - it is possible to identify almost all users that appear in two such anonymized network as long as a few initial mappings are known. We analyze this problem theoretically by reconciling two versions of an artificial power-law network arising from independent subsampling of vertices and edges. We present a new algorithm that identifies most vertices and makes no wrong identifications with high probability. The number of vertices matched is shown to be asymptotically optimal. For an n-vertex graph, our algorithm uses \(n^\varepsilon\) seed nodes (for an arbitrarily small \(\varepsilon\)) and runs in quasilinear time. This improves previous theoretical results which need \(\Theta(n)\) seed nodes and have runtimes of order \(n^{1+\Omega(1)}\). Additionally, the applicability of our algorithm is studied experimentally on different networks.
  @article{DBLP:journals/algorithmica/BringmannFK18, abstract = {There are hundreds of online social networks with altogether billions of users. Many such networks publicly release structural information, with all personal information removed. Empirical studies have shown, however, that this provides a false sense of privacy - it is possible to identify almost all users that appear in two such anonymized network as long as a few initial mappings are known. We analyze this problem theoretically by reconciling two versions of an artificial power-law network arising from independent subsampling of vertices and edges. We present a new algorithm that identifies most vertices and makes no wrong identifications with high probability. The number of vertices matched is shown to be asymptotically optimal. For an n-vertex graph, our algorithm uses \(n^\varepsilon\) seed nodes (for an arbitrarily small \(\varepsilon\)) and runs in quasilinear time. This improves previous theoretical results which need \(\Theta(n)\) seed nodes and have runtimes of order \(n^{1+\Omega(1)}\). Additionally, the applicability of our algorithm is studied experimentally on different networks.}, author = {Bringmann, Karl and Friedrich, Tobias and Krohmer, Anton}, journal = {Algorithmica}, keywords = {antonkrohmer tobiasfriedrich}, number = 11, pages = {3397–3427}, title = {De-anonymization of Heterogeneous Random Graphs in Quasilinear Time}, volume = 80, year = 2018 }
• 
  Aschenbach, Martin; Kötzing, Timo; Seidel, KarenLearning from Informants: Relations between Learning Success Criteria. ArXiv 2018: 37

  ArXiv preprint
  [ Abstract ] [ BibTeX ] [ Download ]
   
  Learning from positive and negative information, so-called informants, being one of the models for human and machine learning introduced by Gold [1967], is investigated. Particularly, naturally arising questions about this learning setting, originating in results on learning from solely positive information, are answered. By a carefully arranged argument learners can be assumed to only change their hypothesis in case it is inconsistent with the data (such a learning behavior is called conservative). The deduced main theorem states the relations between the most important delayable learning success criteria, being the ones not ruined by a delayed in time hypothesis output. Additionally, our investigations concerning the non-delayable requirement of consistent learning underpin the claim for delayability being the right structural property to gain a deeper understanding concerning the nature of learning success criteria. Moreover, we obtain an anomalous hierarchy when allowing for an increasing finite number of anomalies of the hypothesized language by the learner compared with the language to be learned. In contrast to the vacillatory hierarchy for learning from solely positive information, we observe a duality depending on whether infinitely many vacillations between different (almost) correct hypotheses are still considered a successful learning behavior.
  @article{2018kötzingseidel, abstract = {Learning from positive and negative information, so-called informants, being one of the models for human and machine learning introduced by Gold [1967], is investigated. Particularly, naturally arising questions about this learning setting, originating in results on learning from solely positive information, are answered. By a carefully arranged argument learners can be assumed to only change their hypothesis in case it is inconsistent with the data (such a learning behavior is called conservative). The deduced main theorem states the relations between the most important delayable learning success criteria, being the ones not ruined by a delayed in time hypothesis output. Additionally, our investigations concerning the non-delayable requirement of consistent learning underpin the claim for delayability being the right structural property to gain a deeper understanding concerning the nature of learning success criteria. Moreover, we obtain an anomalous hierarchy when allowing for an increasing finite number of anomalies of the hypothesized language by the learner compared with the language to be learned. In contrast to the vacillatory hierarchy for learning from solely positive information, we observe a duality depending on whether infinitely many vacillations between different (almost) correct hypotheses are still considered a successful learning behavior.}, author = {Aschenbach, Martin and Kötzing, Timo and Seidel, Karen}, journal = {ArXiv}, keywords = {arxiv karenseidel timokoetzing year2018}, note = {ArXiv preprint}, number = {arXiv:1801.10502}, pages = 37, title = {Learning from Informants: Relations between Learning Success Criteria}, year = 2018 }
• 
  Bläsius, Thomas; Stumpf, Peter; Ueckerdt, TorstenLocal and Union Boxicity. Discrete Mathematics 2018: 1307 - 1315
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  The boxicity \(box(H)\) of a graph \(H\) is the smallest integer \(d\) such that \(H\) is the intersection of \(d\) interval graphs, or equivalently, that \(H\) is the intersection graph of axis-aligned boxes in \(R^d\). These intersection representations can be interpreted as covering representations of the complement \(H^c\) of \(H\) with co-interval graphs, that is, complements of interval graphs. We follow the recent framework of global, local and folded covering numbers (Knauer and Ueckerdt, 2016) to define two new parameters: the local boxicity \(box_l(H)\) and the union boxicity \(box_u(H)\) of \(H\). The union boxicity of \(H\) is the smallest \(d\) such that \(H^c\) can be covered with \(d\) vertex-disjoint unions of co-interval graphs, while the local boxicity of \(H\) is the smallest \(d\) such that \(H^c\) can be covered with co-interval graphs, at most \(d\) at every vertex. We show that for every graph \(H\) we have \(box_l(H) leq box_u(H) leq box(H) \) and that each of these inequalities can be arbitrarily far apart. Moreover, we show that local and union boxicity are also characterized by intersection representations of appropriate axis-aligned boxes in \(R^d\) . We demonstrate with a few striking examples, that in a sense, the local boxicity is a better indication for the complexity of a graph, than the classical boxicity.
  @article{blsius2018local, abstract = {The boxicity \(box(H)\) of a graph \(H\) is the smallest integer \(d\) such that \(H\) is the intersection of \(d\) interval graphs, or equivalently, that \(H\) is the intersection graph of axis-aligned boxes in \(R^d\). These intersection representations can be interpreted as covering representations of the complement \(H^c\) of \(H\) with co-interval graphs, that is, complements of interval graphs. We follow the recent framework of global, local and folded covering numbers (Knauer and Ueckerdt, 2016) to define two new parameters: the local boxicity \(box_l(H)\) and the union boxicity \(box_u(H)\) of \(H\). The union boxicity of \(H\) is the smallest \(d\) such that \(H^c\) can be covered with \(d\) vertex-disjoint unions of co-interval graphs, while the local boxicity of \(H\) is the smallest \(d\) such that \(H^c\) can be covered with co-interval graphs, at most \(d\) at every vertex. We show that for every graph \(H\) we have \(box_l(H) \leq box_u(H) \leq box(H) \) and that each of these inequalities can be arbitrarily far apart. Moreover, we show that local and union boxicity are also characterized by intersection representations of appropriate axis-aligned boxes in \(R^d\) . We demonstrate with a few striking examples, that in a sense, the local boxicity is a better indication for the complexity of a graph, than the classical boxicity.}, author = {Bläsius, Thomas and Stumpf, Peter and Ueckerdt, Torsten}, journal = {Discrete Mathematics}, keywords = {thomasblaesius year2018}, number = 5, pages = {1307 - 1315}, title = {Local and Union Boxicity}, volume = 341, year = 2018 }
• 
  Baum, Moritz; Bläsius, Thomas; Gemsa, Andreas; Rutter, Ignaz; Wegner, FranziskaScalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. Journal of Computational Geometry 2018: 27-73
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.
  @article{baum2018scalable, abstract = {Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.}, author = {Baum, Moritz and Bläsius, Thomas and Gemsa, Andreas and Rutter, Ignaz and Wegner, Franziska}, journal = {Journal of Computational Geometry}, keywords = {jocg thomasblaesius year2018}, number = 1, pages = {27-73}, title = {Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths}, volume = 9, year = 2018 }
• 
  Rizzo, Manuel; Battaglia, FrancescoStatistical and Computational Tradeoff in Genetic Algorithm-Based Estimation. Journal of Statistical Computation and Simulation 2018: 3081-3097
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  When a genetic algorithm (GA) is employed in a statistical problem, the result is affected by both variability due to sampling and the stochastic elements of algorithm. Both of these components should be controlled in order to obtain reliable results. In the present work we analyze parametric estimation problems tackled by GAs, and pursue two objectives: the first one is related to a formal variability analysis of final estimates, showing that it can be easily decomposed in the two sources of variability. In the second one we introduce a framework of GA estimation with fixed computational resources, which is a form of statistical and the computational tradeoff question, crucial in recent problems. In this situation the result should be optimal from both the statistical and computational point of view, considering the two sources of variability and the constraints on resources. Simulation studies will be presented for illustrating the proposed method and the statistical and computational tradeoff question.
  @article{doi:10.1080/00949655.2018.1499740, abstract = {When a genetic algorithm (GA) is employed in a statistical problem, the result is affected by both variability due to sampling and the stochastic elements of algorithm. Both of these components should be controlled in order to obtain reliable results. In the present work we analyze parametric estimation problems tackled by GAs, and pursue two objectives: the first one is related to a formal variability analysis of final estimates, showing that it can be easily decomposed in the two sources of variability. In the second one we introduce a framework of GA estimation with fixed computational resources, which is a form of statistical and the computational tradeoff question, crucial in recent problems. In this situation the result should be optimal from both the statistical and computational point of view, considering the two sources of variability and the constraints on resources. Simulation studies will be presented for illustrating the proposed method and the statistical and computational tradeoff question.}, author = {Rizzo, Manuel and Battaglia, Francesco}, journal = {Journal of Statistical Computation and Simulation}, keywords = {francescobattaglia jscs manuelrizzo year2018}, number = 16, pages = {3081-3097}, publisher = {Taylor & Francis}, title = {Statistical and Computational Tradeoff in Genetic Algorithm-Based Estimation}, volume = 88, year = 2018 }
• 
  Cseh, Ágnes; Kavitha, TelikepalliPopular edges and dominant matchings. Mathematical Programming 2018: 209-229
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
   
  Given a bipartite graph \($G=(A \cup B, E)$\) with strict preference lists and given an edge \($e^* \in E$\), we ask if there exists a popular matching in \($G$\) that contains \($e^*$\). We call this the popular edge problem. A matching \($M$\) is popular if there is no matching \($M'$\) such that the vertices that prefer \($M'$\) to \($M$\) outnumber those that prefer \($M$\) to \($M'$\). It is known that every stable matching is popular; however \($G$\) may have no stable matching with the edge \($e^*$\). In this paper we identify another natural subclass of popular matchings called "dominant matchings" and show that if there is a popular matching that contains the edge \($e^*$\), then there is either a stable matching that contains \($e^*$\) or a dominant matching that contains \($e^*$\). This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an \($O(n^3)$\) algorithm to find a popular matching containing a given set of edges or report that none exists, where \($n=|A|+|B|$\).
  @article{cseh2018popular, abstract = {Given a bipartite graph $G=(A \cup B, E)$ with strict preference lists and given an edge $e^* \in E$, we ask if there exists a popular matching in $G$ that contains $e^*$. We call this the popular edge problem. A matching $M$ is popular if there is no matching $M'$ such that the vertices that prefer $M'$ to $M$ outnumber those that prefer $M$ to $M'$. It is known that every stable matching is popular; however $G$ may have no stable matching with the edge $e^*$. In this paper we identify another natural subclass of popular matchings called "dominant matchings" and show that if there is a popular matching that contains the edge $e^*$, then there is either a stable matching that contains $e^*$ or a dominant matching that contains $e^*$. This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an $O(n^3)$ algorithm to find a popular matching containing a given set of edges or report that none exists, where $n=|A|+|B|$.}, author = {Cseh, Ágnes and Kavitha, Telikepalli}, journal = {Mathematical Programming}, keywords = {sys:relevantfor:ae agnescseh mp telikepallikavitha year2018}, pages = {209-229}, title = {Popular edges and dominant matchings}, year = 2018 }
• 
  Friedrich, Tobias; Krohmer, AntonOn the diameter of hyperbolic random graphs. SIAM Journal on Discrete Mathematics 2018: 1314-1334
  [ Abstract ] [ BibTeX ] [ URL ] [ 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 is close to optimal (Boguñá, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation has 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))+1})\)(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 \(\beta > 3\), we show that the latter bound is tight by proving an upper bound of \(O(\log n)\) for the diameter.
  @article{friedrich2018diameter, 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 is close to optimal (Boguñá, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation has 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))+1})\)(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 \(\beta > 3\), we show that the latter bound is tight by proving an upper bound of \(O(\log n)\) for the diameter.}, author = {Friedrich, Tobias and Krohmer, Anton}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {antonkrohmer hyperbolic_analysis sidma tobiasfriedrich year2018}, number = 2, pages = {1314-1334}, publisher = {SIAM}, title = {On the diameter of hyperbolic random graphs}, volume = 32, year = 2018 }
• 
  Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonUnbounded Discrepancy of Deterministic Random Walks on Grids. SIAM Journal on Discrete Mathematics 2018: 2441-2452
  [ Abstract ] [ BibTeX ] [ URL ] [ 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\geq1\) and arbitrary discrepancies~\(\ell \geq 0\), we construct configurations that reach a discrepancy of at least \(\ell\).
  @article{friedrich2018unbounded, 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\geq1\) and arbitrary discrepancies~\(\ell \geq 0\), we construct configurations that reach a discrepancy of at least \(\ell\).}, author = {Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {antonkrohmer maximiliankatzmann sidma tobiasfriedrich year2018}, number = 4, pages = {2441-2452}, publisher = {SIAM}, title = {Unbounded Discrepancy of Deterministic Random Walks on Grids}, volume = 32, year = 2018 }
• 
  Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th.The many facets of upper domination. Theoretical Computer Science 2018: 2-25
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  This paper studies Upper Domination, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph with respect to classical and parameterised complexity as well as approximability.
  @article{DBLP:journals/tcs/BazganBCFJKLLMP18, abstract = {This paper studies Upper Domination, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph with respect to classical and parameterised complexity as well as approximability.}, author = {Bazgan, Cristina and Brankovic, Ljiljana and Casel, Katrin and Fernau, Henning and Jansen, Klaus and Klein, Kim{-}Manuel and Lampis, Michael and Liedloff, Mathieu and Monnot, J{{é}}r{{ô}}me and Paschos, Vangelis Th.}, journal = {Theoretical Computer Science}, keywords = {cristinabazgan henningfernau jeromemonnot katrincasel kimmanuelklein klausjansen ljiljanabrankovic mathieuliedloff michaellampis tcs vangelisthpaschos year2018}, pages = {2-25}, title = {The many facets of upper domination}, volume = 717, year = 2018 }
• 
  Dang, Duc-Cuong; Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew M.Escaping Local Optima Using Crossover with Emergent Diversity. Transactions on Evolutionary Computation 2018: 484-497
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the \((\mu+1)\) GA using uniform crossover on the fitness function \(Jump_k\). All previous results in this context only hold for unrealistically low crossover probability \(p_c=O(k/n)\), while we give analyses for the setting of constant \(p_c < 1\) in all but one case. Our bounds show a dependence on the problem size \(n\), the jump length \(k\), the population size \(\mu\), and the crossover probability \(p_c\). For the typical case of constant \(k > 2\) and constant \(p_c\), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of \(\mu\): \(O(n^{k-1})\) for duplicate elimination/minimisation, \(O(n^2 \log n)\) for maximising the convex hull, \(O(n \log n)\) for det. crowding (assuming \(p_c = k/n\)), \(O(n \log n)\) for maximising the Hamming distance, \(O(n \log n)\) for fitness sharing, \(O(n \log n)\) for the single-receiver island model. This proves a sizeable advantage of all variants of the \((\mu+1)\) GA compared to the (1+1) EA, which requires \(\Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.
  @article{dang2017escaping, abstract = {Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the \((\mu+1)\) GA using uniform crossover on the fitness function \(Jump_k\). All previous results in this context only hold for unrealistically low crossover probability \(p_c=O(k/n)\), while we give analyses for the setting of constant \(p_c < 1\) in all but one case. Our bounds show a dependence on the problem size \(n\), the jump length \(k\), the population size \(\mu\), and the crossover probability \(p_c\). For the typical case of constant \(k > 2\) and constant \(p_c\), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of \(\mu\): \(O(n^{k-1})\) for duplicate elimination/minimisation, \(O(n^2 \log n)\) for maximising the convex hull, \(O(n \log n)\) for det. crowding (assuming \(p_c = k/n\)), \(O(n \log n)\) for maximising the Hamming distance, \(O(n \log n)\) for fitness sharing, \(O(n \log n)\) for the single-receiver island model. This proves a sizeable advantage of all variants of the \((\mu+1)\) GA compared to the (1+1) EA, which requires \(\Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.}, author = {Dang, Duc-Cuong and Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Lehre, Per Kristian and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew M.}, editor = {Tan, Kay Chen}, journal = {Transactions on Evolutionary Computation}, keywords = {andrewmsutton martinskrejca tevoc timokoetzing tobiasfriedrich year2018}, month = {jun}, number = 3, pages = {484-497}, publisher = {IEEE}, title = {Escaping Local Optima Using Crossover with Emergent Diversity}, volume = 22, year = 2018 }
• 
  Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, SörenEfficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. Transactions on Networking 2018: 920-933
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require at least a quadratic runtime. Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics, like Log-likelihood and greedy routing, our algorithm discovers embeddings that are very close to the ground truth.
  @article{journals/ton/BlasiusFKL18, abstract = {Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require at least a quadratic runtime. Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics, like Log-likelihood and greedy routing, our algorithm discovers embeddings that are very close to the ground truth.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, Sören}, journal = {Transactions on Networking}, keywords = {antonkrohmer hyperbolic_embedding thomasblaesius tobiasfriedrich transnetw year2018}, number = {1-57570FN}, pages = {920-933}, publisher = {IEEE & ACM}, title = {Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}, volume = 26, year = 2018 }