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