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

The hypervolume indicator is an increasingly popular set measure to compare the quality of two Pareto sets. The basic ingredient of most hypervolume indicator based optimization algorithms is the calculation of the hypervolume contribution of single solutions regarding a Pareto set. We show that exact calculation of the hypervolume contribution is #P-hard while its approximation is NP-hard. The same holds for the calculation of the minimal contribution. We also prove that it is NP-hard to decide whether a solution has the least hypervolume contribution. Even deciding whether the contribution of a solution is at most (1 + *** ) times the minimal contribution is NP-hard. This implies that it is neither possible to efficiently find the least contributing solution (unless P = NP) nor to approximate it (unless NP = BPP). Nevertheless, in the second part of the paper we present a very fast approximation algorithm for this problem. We prove that for arbitrarily given *** ,*** > 0 it calculates a solution with contribution at most (1 + *** ) times the minimal contribution with probability at least (1 *** *** ). Though it cannot run in polynomial time for all instances, it performs extremely fast on various benchmark datasets. The algorithm solves very large problem instances which are intractable for exact algorithms (e.g., 10000 solutions in 100 dimensions) within a few seconds.

• Publication year

  2008

• Venue

  Theoretical Computer Science

• Publication date

  2008-12-14

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.tcs.2010.09.026arXiv 0812.2636
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization

  2011cited by this paper
• Bandit-Based Estimation of Distribution Algorithms for Noisy Optimization: Rigorous Runtime Analysis

  2010cited by this paper
• Don't be greedy when calculating hypervolume contributions

  2009cited by this paper
• Approximating the volume of unions and intersections of high-dimensional geometric objects

  2008influential reference
• A Fast Incremental Hypervolume Algorithm

  2008influential reference
• A Fast Algorithm for Computing the Contribution of a Point to the Hypervolume

  2007cited by this paper
• Faster s-metric calculation by considering dominated hypervolume as klee's measure problem

  2006cited by this paper
• A faster algorithm for calculating hypervolume

  2006influential reference
• An EMO Algorithm Using the Hypervolume Measure as Selection Criterion

  2005cited by this paper
• I Computational Complexity

  2005cited by this paper
• Multi-objective optimisation using S-metric selection: application to three-dimensional solution spaces

  2005cited by this paper
• Heuristics for optimizing the calculation of hypervolume for multi-objective optimization problems

  2005cited by this paper
• Performance assessment of multiobjective optimizers: an analysis and review

  2003cited by this paper
• SPEA2: Improving the Strength Pareto Evolutionary Algorithm For Multiobjective Optimization

  2002cited by this paper
• Scalable multi-objective optimization test problems

  2002cited by this paper
• A fast and elitist multiobjective genetic algorithm: NSGA-II

  2002cited by this paper
• Local-search and hybrid evolutionary algorithms for Pareto optimization

  2002cited by this paper
• A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II

  2000cited by this paper
• Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach

  1999cited by this paper
• Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study

  1998cited by this paper
• On the Hardness of Approximate Reasoning

  1993cited by this paper
• Numerical Recipes: The Art of Scientific Computing

  1989cited by this paper
• New upper bounds in Klee's measure problem

  1988cited by this paper
• Numerical recipes: The art of scientific computing

  1987cited by this paper
• Numerical Recipes in C: The Art of Sci-entific Computing

  1986cited by this paper
• The Complexity of Computing the Permanent

  1979cited by this paper
• Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?

  1977cited by this paper
• Can the Measure of be Computed in Less than O(n log n) Steps

  1977cited by this paper
• A note on a method for generating points uniformly on n-dimensional spheres

  1959cited by this paper

• Approximation of Box Decomposition Algorithm for Fast Hypervolume-Based Multi-Objective Optimization

  2025cites this paper
• DPP-HSS: Toward Fast and Scalable Hypervolume Subset Selection for Many-Objective Optimization

  2025cites this paper
• Efficient Greedy Decremental Hypervolume Subset Selection Using Space Partition Tree

  2025cites this paper
• Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples

  2025cites this paper
• Partitioning Strategies for Parallel Computation of Flexible Skylines

  2025cites this paper
• Parallelizing the Computation of Robustness for Measuring the Strength of Tuples

  2024cites this paper
• Multicriteria Optimization and Decision Making: Principles, Algorithms and Case Studies

  2024cites this paper
• Adaptive nested Monte Carlo approach for multi-objective efficient global optimization

  2024cites this paper
• FHR-NSGA-III: A hybrid many-objective optimizer for intercity multimodal timetable optimization considering travel mode choice

  2023cites this paper
• Multi-Objective Archiving

  2023cites this paper
• Ensemble R2-based Hypervolume Contribution Approximation

  2023cites this paper
• A Diversity-Enhanced Subset Selection Framework for Multimodal Multiobjective Optimization

  2022cites this paper
• Publications of Tobias Friedrich

  2022cites this paper
• A Hypervolume Approximation Method Based on Angular Point

  2022cites this paper
• Towards fast approximations for the hypervolume indicator for multi-objective optimization problems by Genetic Programming

  2022cites this paper
• Learning to Approximate: Auto Direction Vector Set Generation for Hypervolume Contribution Approximation

  2022cites this paper
• On the Construction of Pareto-Compliant Combined Indicators

  2022cites this paper
• Improved Lebesgue Indicator-Based Evolutionary Algorithm: Reducing Hypervolume Computations

  2021influential citation
• A Survey on the Hypervolume Indicator in Evolutionary Multiobjective Optimization

  2021cites this paper
• Uniform mixture design via evolutionary multi-objective optimization

  2021cites this paper
• Publications of Tobias Friedrich

  2021cites this paper
• Greedy approximated hypervolume subset selection for many-objective optimization

  2021cites this paper
• Publications of Tobias Friedrich

  2021cites this paper
• Multi-Objective Optimization for High-Dimensional Expensively Constrained Black-Box Problems

  2021cites this paper
• Approximate Hypervolume Calculation with Guaranteed or Confidence Bounds

  2020cites this paper
• The Hypervolume Indicator

  2020cites this paper
• Indicator-based Multi-objective Evolutionary Algorithms

  2020cites this paper
• A New Hypervolume-Based Evolutionary Algorithm for Many-Objective Optimization

  2020cites this paper
• On the Performance of Generational and Steady-State MOEA/D in the Multi-Objective 0/1 Knapsack Problem

  2020cites this paper
• MHACO: a Multi-Objective Hypervolume-Based Ant Colony Optimizer for Space Trajectory Optimization

  2020cites this paper
• Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets

  2020cites this paper
• Approximating Hypervolume and Hypervolume Contributions Using Polar Coordinate

  2019cites this paper
• of Birmingham Quality evaluation of solution sets in multiobjective optimisation

  2019cites this paper
• Comparison of Reference- and Hypervolume-Based MOEA on Solving Many-Objective Optimization Problems

  2019cites this paper
• Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures: Van Emde Boas Tree for Non-dominated Sorting

  2019cites this paper
• Learning Choice Functions

  2019cites this paper
• Multi-objective grey wolf optimizer based on decomposition

  2019cites this paper
• Approximating Hypervolume Contributions Using Kriging

  2019cites this paper
• Generalized incremental orthant search: towards efficient steady-state evolutionary multiobjective algorithms

  2019cites this paper
• Tutorial on evolutionary multiobjective optimization

  2019cites this paper
• Archiver effects on the performance of state-of-the-art multi- and many-objective evolutionary algorithms

  2019cites this paper
• Scheduling Beyond CPUs for HPC

  2019influential citation
• Quality Evaluation of Solution Sets in Multiobjective Optimisation

  2019cites this paper
• Hypervolume Subset Selection with Small Subsets

  2019influential citation
• LIBEA: A Lebesgue Indicator-Based Evolutionary Algorithm for multi-objective optimization

  2019cites this paper
• Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation

  2018cites this paper
• Maximum Volume Subset Selection for Anchored Boxes

  2018cites this paper
• Deep architectures for learning context-dependent ranking functions

  2018cites this paper
• Computing and Updating Hypervolume Contributions in Up to Four Dimensions

  2018cites this paper
• Generalized offline orthant search: one code for many problems in multiobjective optimization

  2018cites this paper
• Evolutionary many-objective optimization based on linear assignment problem transformations

  2018cites this paper
• GECCO 2018 tutorial on evolutionary multiobjective optimization

  2018cites this paper
• Examining the effect of different configuration issues of the multiobjective evolutionary algorithms on the efficient frontier formulation for the constrained portfolio optimization problem

  2018cites this paper
• An Improved S-Metric Selection Evolutionary Multi-Objective Algorithm With Adaptive Resource Allocation

  2018cites this paper
• R2-Based Hypervolume Contribution Approximation

  2018cites this paper
• Scalarized Preferences in Multi-objective Optimization

  2018cites this paper
• Theoretical and empirical evaluation of diversity-preserving mechanisms in evolutionary algorithms: on the rigorous runtime analysis of diversity-preserving mechanisms in evolutionary algorithms

  2018cites this paper
• Large-scale design optimization methods for problems with expensive objectives and constraints

  2018cites this paper
• A fast hypervolume driven selection mechanism for many-objective optimisation problems

  2017cites this paper
• GECCO 2017 tutorial on evolutionary multiobjective optimization

  2017cites this paper
• Speeding up evolutionary multi-objective optimisation through diversity-based parent selection

  2017cites this paper
• Improving the integration of the IGD+ indicator into the selection mechanism of a Multi-objective Evolutionary Algorithm

  2017cites this paper
• Simultaneous Optimization of Airspace Congestion and Flight Delay in Air Traffic Network Flow Management

  2017cites this paper
• The Unreasonable Destructiveness of Political Correctness in Philosophy

  2017cites this paper
• Multi-objective Optimization with Unbounded Solution Sets

  2016cites this paper
• A Faster Algorithm for the Binary Epsilon Indicator Based on Orthant Minimum Search

  2016cites this paper
• Improving and Extending the HV4D Algorithm for Calculating Hypervolume Exactly

  2016cites this paper
• Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms

  2016cites this paper
• IGD+-EMOA: A multi-objective evolutionary algorithm based on IGD+

  2016cites this paper
• A coevolutionary approach to many objective optimization based on a novel ranking method

  2016cites this paper
• Multi-objective inventory routing with uncertain demand using population-based metaheuristics

  2016cites this paper
• Selection mechanisms based on the maximin fitness function to solve multi-objective optimization problems

  2016cites this paper
• Extending quick hypervolume

  2016cites this paper
• Improving the IWFG algorithm for calculating incremental hypervolume

  2016cites this paper
• A neuro-genetic approach for modeling and optimizing a complex cogeneration process

  2016cites this paper
• Evolutionary Many-Objective Optimization Based on Kuhn-Munkres' Algorithm

  2015cites this paper
• Efficient optimization of many objectives by approximation-guided evolution

  2015cites this paper
• GD-MOEA: A New Multi-Objective Evolutionary Algorithm Based on the Generational Distance Indicator

  2015cites this paper
• On Gradient-Based and Swarm-Based Algorithms for Set-Oriented Bicriteria Optimization

  2015cites this paper
• Indicator-Based Selection

  2015cites this paper
• A Study on Many-Objective Optimization Using the Kriging-Surrogate-Based Evolutionary Algorithm Maximizing Expected Hypervolume Improvement

  2015cites this paper
• Multiobjective optimisation on a budget: Exploring surrogate modelling for robust multi-reservoir rules generation under hydrological uncertainty

  2015cites this paper
• An alternative hypervolume-based selection mechanism for multi-objective evolutionary algorithms

  2015influential citation
• Tutorial on Evolutionary Multiobjective Optimization

  2015cites this paper
• Sampling from Discrete Distributions and Computing Frechet Distances

  2015cites this paper
• 2 Indicator-Based Multiobjective Search

  2015cites this paper
• A Simple and Fast Hypervolume Indicator-Based Multiobjective Evolutionary Algorithm

  2015cites this paper
• Beam Search for integer multi-objective optimization

  2015cites this paper
• MD-MOEA : A new MOEA based on the maximin fitness function and Euclidean distances between solutions

  2014cites this paper
• Kriging model based many-objective optimization with efficient calculation of expected hypervolume improvement

  2014cites this paper
• Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization

  2014cites this paper
• A More Efficient Selection Scheme in iSMS-EMOA

  2014cites this paper
• Empirical Performance of the Approximation of the Least Hypervolume Contributor

  2014influential citation
• Seeding the initial population of multi-objective evolutionary algorithms: A computational study

  2014cites this paper
• Bi-objective hypervolume-based Pareto optimization

  2014cites this paper
• Convergence of Hypervolume-Based Archiving Algorithms

  2014cites this paper
• Consistencies and Contradictions of Performance Metrics in Multiobjective Optimization

  2014cites this paper
• Optimized Approximation Sets for Low-Dimensional Benchmark Pareto Fronts

  2014cites this paper
• GECCO 2014 tutorial on evolutionary multiobjective optimization

  2014cites this paper
• Efficient parent selection for Approximation-Guided Evolutionary multi-objective optimization

  2013cites this paper