The College Application Problem

Author name not available (Why is that?)

Publication date: 3 May 2022

Abstract: 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.

Has companion code repository: https://github.com/maxkapur/optimalapplication

This page was built for publication: The College Application Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6398210)