Parameterized average-case complexity of the hypervolume indicator
Karl Bringmann, Tobias Friedrich · 2013
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.