论文标题
大学申请问题
The College Application Problem
论文作者
论文摘要
本文考虑了受预算约束的随机变量投资组合的预期最大值的最大化。我们将其称为最佳大学申请问题。当每个变量的成本或每个大学的申请费是相同的，我们表明最佳投资组合嵌套在预算限制中，从而产生确切的多项式时间算法。当大学的申请费用不同时，我们表明问题是NP完整的。我们为此更通用的设置提供了四种算法：一个分支和结合的例程，一种动态程序，在伪多样性时间内产生精确的解决方案，一种不同的动态程序，该程序产生了完全多项式时间近似方案和模拟的启发式启发式。数值实验证明了算法的准确性和效率。
This paper considers the maximization of the expected maximum value of a portfolio of random variables subject to a budget constraint. We refer to this as the optimal college application problem. When each variable's cost, or each college's application fee, is identical, we show that the optimal portfolios are nested in the budget constraint, yielding an exact polynomial-time algorithm. When colleges differ in their application fees, we show that the problem is NP-complete. We provide four algorithms for this more general setup: a branch-and-bound routine, a dynamic program that produces an exact solution in pseudopolynomial time, a different dynamic program that yields a fully polynomial-time approximation scheme, and a simulated-annealing heuristic. Numerical experiments demonstrate the algorithms' accuracy and efficiency.
