Opening Pandora’s Box
A harrowing thing that happens in research is that occasionally, you stumble upon a paper from 1979 (paywall) that appears to solve the exact problem that you’ve been working on for months, but that escaped your attention because it used different terminology or notation.
That almost happened to me this week, but mercy was on my side. The paper linked above, Martin Weitzman’s “Optimal Search for the Best Alternative,” considers a problem called the Pandora’s Box problem that resembles my college application problem except for one crucial difference: The Pandora’s Box problem has a time dimension, whereas the college application problem is static.
The unusual thing is that the static problem appears more difficult.
Migrating to Jekyll
After reflecting on my unsustainable dependency on Google services, I have decided to bite the bullet and migrate my blog from Blogger to the open-source Jekyll, with hosting provided by GitHub. In the full version of this post, I explain some of the technical reasons for making this change.
Thesis defense
This week, I defended my master’s thesis at Seoul National University. My thesis concerns an NP-hard portfolio optimization problem that I call the college application problem. My slides, presentation script, and the thesis itself live on this GitHub repository, and all are provided in both English and Korean versions. I also have a very brief deck of reveal.js slides introducing the problem, and I recently wrote some documentation for OptimalApplication.jl, the Julia implementation of my solution algorithms.
The defense process was relatively painless: I received some very helpful comments and reference suggestions from the professors on my committee, and I was pleased that they were persuaded by my argument that the model of the college admissions process I have chosen represents the best tradeoff between realism and tractability.
I also was able to give a brief presentation about my research at a conference in Jeju at the end of last month. Here’s a terrible photo for Mom:
The college application problem, presented in Korean
I gave a brief presentation about the college application problem at a research fair hosted by our department. English subtitles are included.
“College Application” on arXiv
In advance of a conference I will be attending with my labmates next month in Jeju, my thesis advisor and I have posted a preliminary version of “The College Application Problem” on arXiv. Here’s the 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.
Rolling updates to the paper as well as various slideshows presenting the research are available on GitHub.