Continuous Equality Knapsack with Probit-Style Objectives
研究了目标函数为均匀可分非凸函数的连续等式背包问题，该函数关于某点反对称且具有凹凸区域，例如优化独立同分布正态分布累积分布函数之和（逆Probit函数之和）的期望值问题。提出了线性时间算法和常数时间算法（需预处理）。
Abstract We study continuous, equality knapsack problems with uniform separable, non-convex objective functions that are continuous, antisymmetric about a point, and have concave and convex regions. For example, this model captures a simple allocation problem with the goal of optimizing an expected value where the objective is a sum of cumulative distribution functions of identically distributed normal distributions (i.e., a sum of inverse probit functions). We prove structural results of this model under general assumptions and provide two algorithms for efficient optimization: (1) running in linear time and (2) running in a constant number of operations given preprocessing of the objective function.