Paper Info
Title
Parameterized average-case complexity of the hypervolume indicator
Abstract
The hypervolume indicator (HYP) is a popular measure for the quality of a set of n solutions in ℜRd. We discuss its asymptotic worst-case runtimes and several lower bounds depending on different complexity-theoretic assumptions. Assuming that P ≠ NP, there is no algorithm with runtime poly(n,d). Assuming the exponential time hypothesis, there is no algorithm with runtime no(d). In contrast to these worst-case lower bounds, we study the average-case complexity of HYP for points distributed i.i.d. at random on a d-dimensional simplex. We present a general framework which translates any algorithm for HYP with worst-case runtime n f(d) to an algorithm with worst-case runtime n f(d)+1 and fixed-parameter-tractable (FPT) average-case runtime. This can be used to show that HYP can be solved in expected time O(d d2/2, n + d, n2), which implies that HYP is FPT on average while it is W[1]-hard in the worst-case. For constant dimension d this gives an algorithm for HYP with runtime O(n2) on average. This is the first result proving that HYP is asymptotically easier in the average case. It gives a theoretical explanation why most HYP algorithms perform much better on average than their theoretical worst-case runtime predicts.
Year
DOI
Venue
2013
10.1145/2463372.2463450
GECCO
Keywords
Field
DocType
theoretical worst-case runtime,n solution,hypervolume indicator,parameterized average-case complexity,asymptotic worst-case runtimes,runtime poly,runtime o,hyp algorithm,average-case runtime,worst-case runtime n,average case,worst-case lower bound,theory,multiobjective optimization,selection
Average-case complexity,Combinatorics,Mathematical optimization,Parameterized complexity,Multi-objective optimization,Simplex,Mathematics,Exponential time hypothesis
Conference
Citations 
PageRank 
References 
11
0.56
30
Authors
2
Name
Order
Citations
PageRank
Karl Bringmann142730.13
Tobias Friedrich2110.56