One of my current projects involves editing several hours’ worth of subtitle files in the
.srtformat to accompany an online course in numerical optimization. Because we haven’t decided exactly how we want to break up the videos, I needed an efficient way to delay or advance all the subtitles in time, so I wrote a small Python program called
srt_delay.pytoday to help me with this task.
Usage examples below the cut, or you can just go straight to the readme in the GitHub repository.
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.
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.
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:
I gave a brief presentation about the college application problem at a research fair hosted by our department. English subtitles are included.
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.
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 \(n\) schools to serve \(m\) families, such that the furthest distance between any family and their nearest school is minimized. This problem is almost a \(k\)-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.
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.
Existing computational models of admissions markets tend to fall at one of two extremes: Either they envision a centralized admissions process in which the school board runs an algorithm that says which students go where, or a decentralized process in which colleges compete for the best students. But the Korean college admissions process cannot be adequately described in either of these terms.
Planet Money, an NPR show about economics, recently ran an episode entitled “The Marriage Pact” that deals precisely with my research topic. It’s a great episode that discusses both the basic ideas behind stable assignment as well as its applications in organ donation, job placement, and (my area of focus) school choice.
The episode begins with an interview with a Stanford econ student who designed a marriage market for his peers and managed to get 4111 of them to sign up for it. What a cool project! The student makes a few minor misstatements about the Gale–Shapley proposal algorithm that Planet Money leaves uncorrected. In this post, I want to offer a few corrections, not just because I can, but because in my opinion these marginal details are what make stable assignment an interesting and profitable research topic.
They say that we perceive time by the accumulation of novel experiences, so that if you want to have a subjectively long life, you ought to do many spontaneous and hard-to-repeat things, but if you want to have a happy life, you ought to find one or two high pleasures that you can enjoy on a spiritual level and repeat the hell out of them, because they also say that on average, people derive more happiness from repeating a good experience than from trying something new.
You could write a linear program that targets your ideal mix of longevity and happiness and it would tell you exactly how many times to do this or that activity before moving onto something new. But what this calculus leaves out is the feelings of uncertainty that stain the transitions.
I am leaving Naju, after having grown accustomed to this routine, this commute, these faces, and I cannot say with any confidence that I have reached a joy plateau. Every week of teaching here has been better than the last: my skills have improved, my confidence has grown, and the teachers and students have become only more important to me. I could be happy like this for a long time. But.
But too much comfort has a way of smearing all the time together, so that the things that take place in a given day feel less like events and more like footnote references to proto-events hovering in the firmament of the distant past. I have already seen the river clog itself with duckweed; I have already looked down the street from all four of the intersection’s corners, trying to make the buildings line up with the trees. Upon inspection, a more sensitive man might look at these rhododendrons and see something more than last year’s blossoms in a different configuration, but I am a pattern-matcher by nature, too easily bored to remain a recluse. It is time for a new challenge.
As I wrap up my Fulbright grant, I am delighted to share that I have been accepted into the Government of Korea Scholarship program, through which I will be returning to Korea in the fall to pursue a fully funded master’s degree in industrial engineering at Seoul National University.
Thank you to all who have encouraged me.
It is a well-known result in psychology that measures of intelligence correlate across domains. If you are good at math, you are probably also good at verbal reasoning, and vice versa. Therefore, if a company is hiring for a position that requires a variety of skills (as most jobs do), it should pick a candidate who has demonstrated impressive skill in one domain over someone who has demonstrated middling proficiency in a number of different domains.
The more I learn, I find myself with fewer and fewer things to say.
As a humanities student, I studied many “theories.” One theory is historicism, which says that things are the products of their historical settings. Example: At a career mixer, a well-dressed alumnus, class of ’70, approaches a sophomore journalism major. “The first thing you should do once you’re financially independent and you’ve got some money saved up is make a down payment on a house. Nobody will ever stop needing houses,” he says. The advice is a historical artifact, extruded from a certain moment in American politics and a certain set of assumptions about credit scores and work contingency and citizenship status. The student may react with with doubt; her doubt is also historical. It encodes her upbringing, and a different relationship with houses and banks and the word independent.
In August, I surveyed my students about their motivation for learning English, their opinions about our class and my teaching style, and what resources they were using to study English outside of class. By analyzing the results using some of the statistical tools I’ve taught myself this year, I came up with some effective strategies for reaching the disengaged students in my classroom.
At the moment this post goes up, I’ll be giving a presentation about that project at Fulbright Korea’s fall conference in Gyeongju. Here’s a digital version of the talk:
Fun fact: the most-viewed post on this blog, by a long shot, is the one where I shared that I’d received a Critical Language Scholarship from the US Department of State to study Korean in Gwangju. Today, I’m pleased to announce there will soon be another addition to the State Department–mandated disclaimer at the bottom of this blog.
Beginning early this July, I’ll be spending a full year in South Korea as a Fulbright fellow. I’ll be serving as an English teaching assistant at the elementary level. After our six-week orientation in Seoul, I don’t yet know the city I’ll be working in. That said, though Korea isn’t a small country, it possesses an excellent transportation infrastructure. If you’ll be there at all during the next year, send me an email so we can catch up!
Here’s a spotlight on the website of the Thornton School of Music about me and my friend Geetha, also a new Fulbright fellow.
We pretend stability by tracking our life’s progress as a series of marginal changes, so that from each day to the next we can see that we are still ourselves, changed perhaps in substance, but never in identity.
But sample two days, say, ten or twenty years apart within the spread of a life—could you recognize the images as of the same person? Over time the marginal changes penetrate to the being’s core. The transformation becomes comprehensive.
I’ve just finished my first week of class at Chonnam National Universty here in Gwangju with CLS and everything is amazing! I am staying with a host family in a suburb about 40 minutes from school by bus, so I get to practice my Korean 24/7.
Speaking in a new language can feel like doing the dishes with chopsticks. One of the conditions of the CLS scholarship is that students use only the target language when they are on campus, even outside of class, which is both exhausting and rewarding. Listening and speaking are my weakest language areas, and trying to explain a multi-step process in Korean or politely make a request of my host family often leaves all parties frustrated and confused. I am committed to the language policy, but it seems to worry my host family that I come home each day exhausted of my Korean abilities rather than more fluent.
Life in Gwangju is really nice. Gwangju is the sixth largest city in Korea, so although most people here have interacted with foreigners, we are by no means common. I certainly feel the preen of cautious eyes turning toward me when I get on the bus or enter a restaurant. The questions I most often receive from strangers are whether or not I can eat spicy food and whether I know how to use chopsticks.
I am blessed and honored to have received a Critical Language Scholarship from the US Department of State to study Korean language this summer at Chonnam University. This will be my first visit to Korea, and I am incredibly excited as well as anxious about becoming a study abroad student for the first time.
I feel very grateful for the professors who wrote my references for this program and all of those who provided me with guidance during the application. I am fortunate to live in a country that values the study of foreign languages enough to sponsor students like me using public funds. Thank you for paying your taxes.
As many of you know, visiting Korea is a dream I have been cultivating for years. That dream has now come true. Although this is mainly my poetry blog (and I will continue to post poetry), when I am in Gwangju this summer I will also share about my experiences and thoughts in a traditional blog format. Thanks for reading.
“Where did the old blog go?” On June 25, 2022, I moved by blog from Google’s Blogger service to a Jekyll blog hosted on GitHub (which you are currently viewing). I have copied over all the posts from the old blog that I think are worth reading. Nonetheless, the original Illusion Slopes, whose content runs back to November 2015, is still accessible at illusionslopes.blogspot.com.
subscribe via RSS