论文标题
连续的平等背包与概率风格的目标
Continuous Equality Knapsack with Probit-Style Objectives
论文作者
论文摘要
我们研究了连续的，平等的背包问题，具有均匀的可分离，非凸的目标函数，这些函数是连续的，对某个点的反对称性，并且具有凹形和凸区域。例如，该模型捕获了一个简单的分配问题，其目标是优化期望值，而目标是相同分布的正常分布的累积分布函数的总和（即，逆向概率函数的总和）。我们在一般假设下证明了该模型的结构结果，并提供了两种算法以进行有效的优化：（1）在线性时间和（2）以恒定数量的操作中运行，并给出了对目标函数的预处理。
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.
