  We present an efficient approximate message passing solver for the lifted
disjoint paths problem (LDP), a natural but NP-hard model for multiple object
tracking (MOT). Our tracker scales to very large instances that come from long
and crowded MOT sequences. Our approximate solver enables us to process the
MOT15/16/17 benchmarks without sacrificing solution quality and allows for
solving MOT20, which has been out of reach up to now for LDP solvers due to its
size and complexity. On all these four standard MOT benchmarks we achieve
performance comparable or better than current state-of-the-art methods
including a tracker based on an optimal LDP solver.
