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.
The school location problem
I’ve spent a few days thinking about a facility location problem that we might call the school location problem. The goal is to place schools to serve families, such that the furthest distance between any family and their nearest school is minimized. This problem is almost a -means or ellipsoid fitting problem, but its unusual “minimin” form makes it computationally challenging.
In the video below, and associated Jupyter notebook (GitHub, HTML viewer), I discuss the formulation of this problem, show to express it as a mixed-integer second-order convex program, and then solve a small instance using the Julia/JuMP/Juniper/SCS stack.
Here’s the video link.
Administrative vs. allocative efficiency
This fall marks my final semester of coursework, and penultimate semester overall, of the master’s course in industrial engineering here at Seoul National University. I’m taking courses in combinatorial optimization and advanced microeconomics, as well as continuing my study of college admissions markets as a research assistant in the Management Science/Optimization Lab.
Recently, I have been focusing on risk-averse behavior in college applications. In an ideal universe, college applications are completely standardized and there are no constraints on students’ ability to apply to many schools or on schools’ ability to assess a large number of applicants. In reality, many highly qualified students fail to apply to top schools because they doubt their ability to get in or receive a sufficient financial-aid package. For these students, the time and money required to submit an additional application to a so-called reach school takes away from time that could be spent refining an application to a target school. This opportunity cost is not trivial, because modern admissions offices strongly prefer students who tailor their personal statement to the characteristics and interests of the target school or program.