Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
From MaRDI portal
Publication:2321329
Abstract: Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization problems. During the past two decades, promising results on the running time analysis (one essential theoretical aspect) of EAs have been obtained, while most of them focused on isolated combinatorial optimization problems, which do not reflect the general-purpose nature of EAs. To provide a general theoretical explanation of the behavior of EAs, it is desirable to study their performance on general classes of combinatorial optimization problems. To the best of our knowledge, the only result towards this direction is the provably good approximation guarantees of EAs for the problem class of maximizing monotone submodular functions with matroid constraints. The aim of this work is to contribute to this line of research. Considering that many combinatorial optimization problems involve non-monotone or non-submodular objective functions, we study the general problem classes, maximizing submodular functions with/without a size constraint and maximizing monotone approximately submodular functions with a size constraint. We prove that a simple multi-objective EA called GSEMO-C can generally achieve good approximation guarantees in polynomial expected running time.
Recommendations
- Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences
- Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
- On the approximation ability of evolutionary optimization with application to minimum set cover
- Fast algorithms for maximizing monotone nonsubmodular functions
- Evolutionary algorithms and matroid optimization problems
Cites work
- scientific article; zbMATH DE number 976350 (Why is no real title available?)
- scientific article; zbMATH DE number 5686753 (Why is no real title available?)
- A tight linear time (1/2)-approximation for unconstrained submodular maximization
- An 0. 828-approximation algorithm for the uncapacitated facility location problem
- An analysis of approximations for maximizing submodular set functions—I
- An analysis on recombination in multi-objective evolutionary optimization
- Applied multivariate statistical analysis.
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Computing minimum cuts by randomized search heuristics
- Determinantal point processes for machine learning
- Drift analysis and average time complexity of evolutionary algorithms
- Evolutionary algorithms and matroid optimization problems
- Evolutionary learning: advances in theories and algorithms
- Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Maximizing Non-monotone Submodular Functions
- Minimum spanning trees made easier via multi-objective optimization
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Non-monotone submodular maximization under matroid and knapsack constraints
- On the analysis of the \((1+1)\) evolutionary algorithm
- Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
- Restricted strong convexity implies weak submodularity
- STACS 2005
- Some optimal inapproximability results
- Submodular maximization with cardinality constraints
Cited in
(5)- Pareto optimization for subset selection with dynamic cost constraints
- Result diversification by multi-objective evolutionary algorithms with theoretical guarantees
- Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II)
- Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations
- Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences
This page was built for publication: Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2321329)
