Human Performance on an NP-Hard Partitioning Problem at Industrial Scale
Columbia Records introduced the LP format in 1948, giving listeners twenty five minutes of music per side of a vinyl record. For fifty years, every album, through vinyl and cassette, was built around this fifty-minute, two-partition limitation. In 1965, the 8-track cartridge changed the geometry: the same albums, now divided into four programs of equal length (because all four programs play across a single fixed loop of tape), and the longest program determines the length of the loop. Hardly any musician ever created an album for the 8-track medium; every 8-track is, by necessity, a repartitioning of a work designed for a different container. Simply, whoever laid out the track order on the 8-track version of an album had multiple goals: retain the musicality, split the songs evenly across the four stereo tracks of tape, and minimize the length of tape in the cartridge. This provides us a corpus of tens of thousands of human solutions to an NP-hard problem.
This corpus gives us a natural experiment for a question that’s surprisingly hard to study: how good are humans at NP-hard problems? It has been asked before. Undergrads solving traveling salesman puzzles on a screen, with toy instances and nothing at stake. The 8-track catalog is the opposite: professionals who did this all day, solving real instances they didn’t choose, under real constraints, without the aid of a computer, with the cost of every wasted foot of tape multiplied across a production run. And because an album only holds ten to fourteen songs, every one of these instances is small enough to solve to provable optimality by exhaustive search. So we can take each human solution and grade it against perfection.
In case you’re wondering, I’m putting an 8-track player in my car and I wanted a copy of Frank Ocean’s Blonde. Then I started thinking. And now we’re here.