Beyond Quantum Advantage: Improved Classical Algorithms for the Binary Paint Shop Problem

Mark Goh, Lara Caroline Pereira dos Santos, Matthias Sperl +1

The binary paint shop problem (BPSP) is an APX-hard optimization problem in which, given $n$ car models that occur twice in a sequence of length $2n$, the objective is to find a co…