Paper Info
Title
Approximating the least hypervolume contributor: NP-hard in general, but fast in practice
Abstract
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.
Year
DOI
Venue
2012
10.1016/j.tcs.2010.09.026
Theoretical Computer Science
Keywords
Field
DocType
optimization algorithm,exact calculation,hypervolume indicator,Multi-objective optimization,minimal contribution,Evolutionary algorithms,hypervolume contributor,hypervolume contribution,Hypervolume indicator,single solution,fast approximation algorithm,Pareto set,large problem instance,exact algorithm
Approximation algorithm,Mathematical optimization,Optimization algorithm,Time complexity,Pareto principle,Mathematics
Journal
Volume
ISSN
Citations 
425,
Theoretical Computer Science
54
PageRank 
References 
Authors
2.05
24
2
Name
Order
Citations
PageRank
Karl Bringmann142730.13
Tobias Friedrich221113.48