# Making Higher Order MOT Scalable: An Efficient Approximate Solver for Lifted Disjoint Paths

arXiv: https://arxiv.org/abs/2108.10606 · HTML: https://mlsanity.com/paper/2108.10606/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 71 references that are in the map.
- First posted on arXiv 24 Aug 2021.

## Builds on (most cited first, 24 of 24)

- [Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks](https://mlsanity.com/paper/1506.01497/) (2015)
- [You Only Look Once: Unified, Real-Time Object Detection](https://mlsanity.com/paper/1506.02640/) (2015)
- [Simple Online and Realtime Tracking with a Deep Association Metric](https://mlsanity.com/paper/1703.07402/) (2017)
- [Focal Loss for Dense Object Detection](https://mlsanity.com/paper/1708.02002/) (2017)
- [Performance Measures and a Data Set for Multi-Target, Multi-Camera Tracking](https://mlsanity.com/paper/1609.01775/) (2016)
- [CenterNet: Keypoint Triplets for Object Detection](https://mlsanity.com/paper/1904.08189/) (2019)
- [MOT16: A Benchmark for Multi-Object Tracking](https://mlsanity.com/paper/1603.00831/) (2016)
- [Tracking Objects as Points](https://mlsanity.com/paper/2004.01177/) (2020)
- [Person Transfer GAN to Bridge Domain Gap for Person Re-Identification](https://mlsanity.com/paper/1711.08565/) (2017)
- [Tracking without bells and whistles](https://mlsanity.com/paper/1903.05625/) (2019)
- [MOT20: A benchmark for multi object tracking in crowded scenes](https://mlsanity.com/paper/2003.09003/) (2020)
- [Joint Discriminative and Generative Learning for Person Re-identification](https://mlsanity.com/paper/1904.07223/) (2019)
- [Learning a Neural Solver for Multiple Object Tracking](https://mlsanity.com/paper/1912.07515/) (2019)
- [PnPNet: End-to-End Perception and Prediction with Tracking in the Loop](https://mlsanity.com/paper/2005.14711/) (2020)
- [MOTChallenge 2015: Towards a Benchmark for Multi-Target Tracking](https://mlsanity.com/paper/1504.01942/) (2015)
- [Online Multi-Object Tracking with Dual Matching Attention Networks](https://mlsanity.com/paper/1902.00749/) (2019)
- [Tracking The Untrackable: Learning To Track Multiple Cues with Long-Term Dependencies](https://mlsanity.com/paper/1701.01909/) (2017)
- [Spatial-Temporal Relation Networks for Multi-Object Tracking](https://mlsanity.com/paper/1904.11489/) (2019)
- [Deep Cosine Metric Learning for Person Re-Identification](https://mlsanity.com/paper/1812.00442/) (2018)
- [Lifted Disjoint Paths with Application in Multiple Object Tracking](https://mlsanity.com/paper/2006.14550/) (2020)
- [End-to-end Learning of Multi-sensor 3D Tracking by Detection](https://mlsanity.com/paper/1806.11534/) (2018)
- [Multi-Person Tracking by Multicut and Deep Matching](https://mlsanity.com/paper/1608.05404/) (2016)
- [A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems](https://mlsanity.com/paper/1612.05460/) (2016)
- [Multiple People Tracking Using Hierarchical Deep Tracklet Re-identification](https://mlsanity.com/paper/1811.04091/) (2018)

## Built on by (most cited first, 19 of 19)

- [Observation-Centric SORT: Rethinking SORT for Robust Multi-Object Tracking](https://mlsanity.com/paper/2203.14360/) (2022)
- [StrongSORT: Make DeepSORT Great Again](https://mlsanity.com/paper/2202.13514/) (2022)
- [Unifying Short and Long-Term Tracking with Graph Hierarchies](https://mlsanity.com/paper/2212.03038/) (2022)
- [SparseTrack: Multi-Object Tracking by Performing Scene Decomposition based on Pseudo-Depth](https://mlsanity.com/paper/2306.05238/) (2023)
- [LMGP: Lifted Multicut Meets Geometry Projections for Multi-Camera Multi-Object Tracking](https://mlsanity.com/paper/2111.11892/) (2021)
- [Adiabatic Quantum Computing for Multi Object Tracking](https://mlsanity.com/paper/2202.08837/) (2022)
- [Learning of Global Objective for Network Flow in Multi-Object Tracking](https://mlsanity.com/paper/2203.16210/) (2022)
- [Multi-Object Tracking and Segmentation via Neural Message Passing](https://mlsanity.com/paper/2207.07454/) (2022)
- [FastDOG: Fast Discrete Optimization on GPU](https://mlsanity.com/paper/2111.10270/) (2021)
- [Multi-Scene Generalized Trajectory Global Graph Solver with Composite Nodes for Multiple Object Tracking](https://mlsanity.com/paper/2312.08951/) (2023)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [Cell Tracking according to Biological Needs -- Strong Mitosis-aware Multi-Hypothesis Tracker with Aleatoric Uncertainty](https://mlsanity.com/paper/2403.15011/) (2024)
- [NOOUGAT: Towards Unified Online and Offline Multi-Object Tracking](https://mlsanity.com/paper/2509.02111/) (2025)
- [Joint Spatial-Temporal and Appearance Modeling with Transformer for Multiple Object Tracking](https://mlsanity.com/paper/2205.15495/) (2022)
- [Learnable Graph Matching: A Practical Paradigm for Data Association](https://mlsanity.com/paper/2303.15414/) (2023)
- [QPM: Discrete Optimization for Globally Interpretable Image Classification](https://mlsanity.com/paper/2502.20130/) (2025)
- [Learning a Neural Association Network for Self-supervised Multi-Object Tracking](https://mlsanity.com/paper/2411.11514/) (2024)
- [A Hybrid Approach To Real-Time Multi-Object Tracking](https://mlsanity.com/paper/2308.01248/) (2023)
- [RTAT: A Robust Two-stage Association Tracker for Multi-Object Tracking](https://mlsanity.com/paper/2408.07344/) (2024)

## Abstract (arXiv)

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.