Maximizing a Class of Utility Functions Over the Vertices of a Polytope
研究在多面体顶点上最大化一类含凹函数的效用问题，证明其NP难并给出1/2近似算法，实验表明解在最优的1%-2%内且速度更快。
Given a polytope X, a monotone concave univariate function g, and two vectors c and d, we study the discrete optimization problem of finding a vertex of X that maximizes the utility function c’x + g(d’x). This problem has numerous applications in combinatorial optimization with a probabilistic objective, including estimation of project duration with stochastic times, in reliability models, in multinomial logit models and in robust optimization. We show that the problem is 𝒩𝒫-hard for any strictly concave function g even for simple polytopes, such as the uniform matroid, assignment and path polytopes; and propose a 1/2-approximation algorithm for it. We discuss improvements for special cases where g is the square root, log utility, negative exponential utility and multinomial logit probability function. In particular, for the square root function, the approximation ratio is 4/5. We also propose a 1.25-approximation algorithm for a class of minimization problems in which the maximization of the utility function appears as a subproblem. Although the worst-case bounds are tight, computational experiments indicate that the suggested approach finds solutions within 1%–2% optimality gap for most of the instances, and can be considerably faster than the existing alternatives.