# Incremental Optimal Assignment for Real-Time Crowd Tracking

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 23 Jul 2026.

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

- [Simple Online and Realtime Tracking](https://mlsanity.com/paper/1602.00763/) (2016)
- [ByteTrack: Multi-Object Tracking by Associating Every Detection Box](https://mlsanity.com/paper/2110.06864/) (2021)
- [HOTA: A Higher Order Metric for Evaluating Multi-Object Tracking](https://mlsanity.com/paper/2009.07736/) (2020)
- [MOT16: A Benchmark for Multi-Object Tracking](https://mlsanity.com/paper/1603.00831/) (2016)
- [MOT20: A benchmark for multi object tracking in crowded scenes](https://mlsanity.com/paper/2003.09003/) (2020)
- [Observation-Centric SORT: Rethinking SORT for Robust Multi-Object Tracking](https://mlsanity.com/paper/2203.14360/) (2022)
- [CrowdHuman: A Benchmark for Detecting Human in a Crowd](https://mlsanity.com/paper/1805.00123/) (2018)
- [Crowded Scene Analysis: A Survey](https://mlsanity.com/paper/1502.01812/) (2015)
- [Visible-Thermal Multiple Object Tracking: Large-scale Video Dataset and Progressive Fusion Approach](https://mlsanity.com/paper/2408.00969/) (2024)
- [Visual Multi-Object Tracking with Re-Identification and Occlusion Handling using Labeled Random Finite Sets](https://mlsanity.com/paper/2407.08872/) (2024)

## Abstract (arXiv)

Multi-object tracking in dense crowds requires solving a bipartite assignment problem between detections and trajectories at every video frame. The classical Hungarian algorithm solves this in O(N3) time, which becomes a bottleneck for large scenes with hundreds of people. We propose an incremental assignment algorithm that exploits the block-sparse structure of crowd tracking cost matrices --- dense within each crowd cluster, near-zero between clusters. We compute the exact same optimal N × N assignment as the Hungarian algorithm, but via an incremental strategy: we add one person at a time, exploiting the fact that after step n-1 the dual potentials are exactly optimal for the (n-1)×(n-1) subproblem --- a strictly stronger condition than the intermediate feasibility maintained by the Hungarian algorithm during its N outer iterations. Each new step therefore requires only a single augmenting path search from a certified optimal starting point. This avoids repeated full-matrix scans while guaranteeing an identical globally optimal result. A diagonal-reordering invariant keeps the data structure compact and cache-friendly. On realistic crowd benchmarks with N ∈ [200, 5000] people organised into dense clusters, our algorithm achieves 3.7--6.5× speedup over the Hungarian baseline while producing provably optimal matchings identical to those of Hungarian. The speedup grows with N and remains stable beyond N=3000, making the method especially attractive for large-scale crowd scenes such as stadium exits and mass public events.