Approximating the least hypervolume contributor: NP-hard in general, but fast in practice

DOI10.1016/j.tcs.2010.09.026zbMath1237.68085OpenAlexW2029496228MaRDI QIDQ418034

Tobias Friedrich, Karl Bringmann

Publication date: 14 May 2012

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.09.026

zbMATH Keywords

multi-objective optimizationevolutionary algorithmshypervolume indicator

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (9)

Efficient optimization of many objectives by approximation-guided evolution ⋮ Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation ⋮ A note on the \(\epsilon\)-indicator subset selection ⋮ FHR-NSGA-III: a hybrid many-objective optimizer for intercity multimodal timetable optimization considering travel mode choice ⋮ Illustration of fairness in evolutionary multi-objective optimization ⋮ Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization ⋮ Speeding up many-objective optimization by Monte Carlo approximations ⋮ Bi-objective hypervolume-based Pareto optimization ⋮ Stochastic convergence of random search methods to fixed size Pareto front approximations

Uses Software

• SPEA2
• HypE

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Approximating the volume of unions and intersections of high-dimensional geometric objects
• On the hardness of approximate reasoning
• A note on a method for generating points uniformly on n -dimensional spheres
• Can the Measure of ∪ n 1 [ a i , b i be Computed in Less Than O(n logn) Steps?]
• Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects
• New Upper Bounds in Klee’s Measure Problem
• Don't be greedy when calculating hypervolume contributions
• Evolutionary Multi-Criterion Optimization

This page was built for publication: Approximating the least hypervolume contributor: NP-hard in general, but fast in practice