Randomized local search, evolutionary algorithms, and the minimum spanning tree problem

DOI10.1016/J.TCS.2006.11.002zbMATH Open1117.68090OpenAlexW2153401898MaRDI QIDQ884444FDOQ884444

Authors: F. Neumann, Ingo Wegener 

Publication date: 6 June 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2003/5454

Recommendations

• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
• Runtime analysis of evolutionary algorithms for the depth restricted \((1,2)\)-minimum spanning tree problem
• A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem
• Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem
• A biased random-key genetic algorithm for the capacitated minimum spanning tree problem

zbMATH Keywords

minimum spanning trees\((1+\lambda)\) EAanalysis of expected optimization timeparallel random search

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• STACS 2005
• The Metropolis algorithm for graph bisection
• Title not available (Why is that?)
• On the spanning trees of weighted graphs
• How to analyse evolutionary algorithms.
• Title not available (Why is that?)
• On spanning tree problems with multiple objectives
• On the analysis of the \((1+1)\) evolutionary algorithm
• Genetic algorithm approach on multi-criteria minimum spanning tree problem
• Maximum of k-th maximal spanning trees of a weighted graph
• The time complexity of maximum matching by simulated annealing

Cited In (50)

• Fourier analysis meets runtime analysis: precise runtimes on plateaus
• Stagnation detection in highly multimodal fitness landscapes
• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• Fixed-parameter evolutionary algorithms and the vertex cover problem
• Ranking-based black-box complexity
• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• Towards a runtime comparison of natural and artificial evolution
• Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints
• Hybridizing evolutionary algorithms with variable-depth search to overcome local optima
• Runtime analysis of the 1-ANT ant colony optimizer
• The life span method -- a new variant of local search
• Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint
• Title not available (Why is that?)
• Runtime analysis of a binary particle swarm optimizer
• Welch sets for random generation and representation of reversible one-dimensional cellular automata
• Title not available (Why is that?)
• Ant colony optimization and the minimum spanning tree problem
• Kruskal with embedded c-semirings to solve MST problems with partially-ordered costs
• (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error
• Plateaus can be harder in multi-objective optimization
• Fixed-target runtime analysis
• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
• Stagnation detection with randomized local search
• Black-box search by unbiased variation
• Computing minimum cuts by randomized search heuristics
• Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution
• Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem
• Variable solution structure can be helpful in evolutionary optimization
• Practical performance models of algorithms in evolutionary program induction and other domains
• On the approximability of the fixed-tree balanced minimum evolution problem
• Runtime analysis of the \((1+1)\) EA on computing unique input output sequences
• Evolutionary algorithms and matroid optimization problems
• Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances
• Approximate optimal hybrid control synthesis by classification-based derivative-free optimization
• First steps to the runtime complexity analysis of ant colony optimization
• Runtime analysis of evolutionary algorithms for the depth restricted \((1,2)\)-minimum spanning tree problem
• Free lunches on the discrete Lipschitz class
• Adaptive drift analysis
• Multiplicative drift analysis
• Comparison of simple diversity mechanisms on plateau functions
• An analysis on recombination in multi-objective evolutionary optimization
• Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem
• On the analysis of the \((1+1)\) evolutionary algorithm for the maximum leaf spanning tree problem
• Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem
• Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
• The impact of parametrization in memetic evolutionary algorithms
• Drift conditions for estimating the first hitting times of evolutionary algorithms
• Evolutionary algorithms and dynamic programming
• Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems
• A comparative performance analysis of evolutionary algorithms on \(k\)-median and facility location problems

This page was built for publication: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q884444)