College Applications with Non-Homogeneous Application Costs

A college applicant submits costly applications to a set of colleges while uncertain which colleges will admit her. If she knows the application costs, her utility of attending each college, and her probability of being admitted to each college, which subset of colleges should she apply to maximize her expected net payoff? The problem is an instance of non-monotone submodular maximization. There are two principal variants in the literature, one where the events of getting into different colleges are independent, and the other where they are correlated. The main results in the literature handle cases where all application costs are the same. We provide exact and approximate algorithms for the problem when college application costs vary.