Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem

• URL: http://arxiv.org/abs/2404.11784v1
• Date: Wed, 17 Apr 2024 22:20:02 GMT
• Title: Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem
• Authors: Jonathan Gadea Harder, Aneta Neumann, Frank Neumann,
• Abstract summary: We show that the $(mu+1)$EA achieves maximal diversity with an expected runtime of $O(mu2 m4 log(m))$ for the small gap case. The $2P-EA_D$ displays stronger performance, with bounds of $O(mu2 n2 log(m))$ for the small gap case, $O(mu3 m3)$ for paths.
• Score: 10.506038775815094
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper explores the enhancement of solution diversity in evolutionary algorithms (EAs) for the maximum matching problem, concentrating on complete bipartite graphs and paths. We adopt binary string encoding for matchings and use Hamming distance to measure diversity, aiming for its maximization. Our study centers on the $(\mu+1)$-EA and $2P-EA_D$, which are applied to optimize diversity. We provide a rigorous theoretical and empirical analysis of these algorithms. For complete bipartite graphs, our runtime analysis shows that, with a reasonably small $\mu$, the $(\mu+1)$-EA achieves maximal diversity with an expected runtime of $O(\mu^2 m^4 \log(m))$ for the small gap case (where the population size $\mu$ is less than the difference in the sizes of the bipartite partitions) and $O(\mu^2 m^2 \log(m))$ otherwise. For paths, we establish an upper runtime bound of $O(\mu^3 m^3)$. The $2P-EA_D$ displays stronger performance, with bounds of $O(\mu^2 m^2 \log(m))$ for the small gap case, $O(\mu^2 n^2 \log(n))$ otherwise, and $O(\mu^3 m^2)$ for paths. Here, $n$ represents the total number of vertices and $m$ the number of edges. Our empirical studies, which examine the scaling behavior with respect to $m$ and $\mu$, complement these theoretical insights and suggest potential for further refinement of the runtime bounds.

Related papers

• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  We show that even the special case of $k$-Center in dimension $Theta(log n)$ is $(sqrt3/2- o(1))$hard to approximate for FPT algorithms. We also show that even the special case of $k$-Center in dimension $Theta(log n)$ is $(sqrt3/2- o(1))$hard to approximate for FPT algorithms.
  arXiv  Detail & Related papers  (2023-05-12T08:43:28Z)
• Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm [7.421135890148154]
  Genetic algorithm with population size $mu=O(n)$ optimize jump functions with gap size $k ge 3$ in time. We show that this diversity persist with high probability for a time exponential in $mu$ (instead of quadratic) We obtain stronger runtime guarantees, among them the statement that for all $cln(n)lemu le n/log n$, with $c$ a suitable constant, the runtime of the $(mu+1)$ GA on $mathrmJump_k$, with $k
  arXiv  Detail & Related papers  (2023-02-24T10:50:24Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  We structured convex optimization problems with additive objective $r:=p + q$, where $r$ is $mu$-strong convex similarity. We proposed a method to solve problems master to agents' communication and local calls. The proposed method is much sharper than the $mathcalO(sqrtL_q/mu)$ method.
  arXiv  Detail & Related papers  (2022-05-30T14:28:02Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  We show a quantum algorithm with complexity $widetilde O(T_Dn)$, where $T_D D+1$. While the best known classical algorithm is $textpoly(m,n)log n T_Dn$, the time complexity of our quantum algorithm is $textpoly(m,n)log n T_Dn$.
  arXiv  Detail & Related papers  (2021-04-29T14:50:03Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Revisiting EXTRA for Smooth Distributed Optimization [70.65867695317633]
  We give a sharp complexity analysis for EXTRA with the improved $Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$. Our communication complexities of the accelerated EXTRA are only worse by the factors of $left(logfracLmu (1-sigma_2(W))right)$ and $left(logfrac1epsilon (1-
  arXiv  Detail & Related papers  (2020-02-24T08:07:08Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.