REVIEW 4 major objections 5 minor 35 references
Incremental Optimal Assignment for Real-Time Crowd Tracking
T0 review · 4 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read A warm-started incremental assignment algorithm reproduces the exact optimal N×N matching of the Hungarian algorithm on block-sparse crowd graphs, with 3.7–6.5× speedup for N up to 5000.
desk verdict Plausible incremental assignment for crowd graphs, but the abstract overstates the speedup range and the central complexity parameter L is unmeasured; needs revision before I'd trust it. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the incremental extension of a perfect matching, chained from 1×1 to N×N, where the previous subproblem's exactly-optimal dual potentials serve as a certified warm start. The 'equality subgraph' — the set of edges whose slack is zero under the current potentials — is the object that carries the argument: a single augmenting path in it absorbs the new node. Two supporting mechanisms keep the search cheap: a diagonal-reordering invariant (SparseReorder) keeps the matching in canonical diagonal form after each augmentation, and a cumulative-offset priority queue implements the shortest-path search so that only valid, non-forbidden edges are scanned. The net effect is that each ext
What would settle it
Instrument the algorithm to record the average augmenting path length L for each N on real or synthetic crowd data; if L is not small relative to k (or is not bounded by O(1) empirically), then the O(N²L log k/C) bound loses to Hungarian. Alternatively, run the algorithm on non-clustered, uniform random cost matrices where the block-sparse assumption fails: if it is not substantially faster than Hungarian there, that would confirm the speedup is purely a structural artifact of cluster gating.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that warm-starting from dual potentials that are exactly optimal for the (n−1)×(n−1) subproblem makes the n-th incremental extension a single augmenting-path search — a strictly stronger starting condition than the mere feasibility Hungarian maintains between its outer iterations. Complementary slackness is preserved by a diagonal-reordering invariant and a cumulative-offset priority queue, so the search only follows tight, valid edges and never leaves the new node's cluster. The paper proves by induction that the diagonal matching after each step is optimal for the n×n subproblem, and hence that the final N×N matching is exactly the Hungari
Load-bearing premise
The speedup depends on the unmeasured assumption that each incremental augmenting path stays very short (length L far below the cluster size k, roughly constant in practice); if L grows toward N on harder data, the theoretical bound collapses to O(N³) and the advantage over Hungarian disappears.
Editorial extensions
If this is right
- At 25–30 fps, exact assignment becomes real-time for scenes up to roughly 1,000 tracked people, where the dense Hungarian baseline already misses the frame budget.
- The speedup grows with N and plateaus beyond 3,000 people, so large-scale events such as stadium exits stand to gain the most.
- Because the final matching is provably identical to Hungarian's, the algorithm can replace Hungarian in existing SORT/ByteTrack-style pipelines with no change to association semantics.
- The stronger subproblem-optimality condition used here suggests a general recipe: any solver that can certify optimality on a subproblem can be extended incrementally in one augmenting path.
- On the paper's model, gating and cluster separation directly control runtime, implying that better detectors with tighter gates translate into faster exact association.
Reading between the lines
- The paper asserts but never measures the average augmenting path length L; tracking L on real MOT20-style sequences would reveal whether the O(1) warm-start advantage survives beyond the synthetic cluster model.
- The warm-start principle should extend to decremental matching (people leaving the scene) and to unbalanced assignment problems, both of which are routine in tracking; the paper lists these as future work, and they are natural next results.
- If the incremental invariant holds for more general affinity functions — appearance embeddings, learned costs — the speedup could carry over to re-identification-based trackers, though block sparsity would need an analogous gating mechanism.
- The comparison baseline is a dense Hungarian implementation; a sparse Hungarian variant might outperform the reported numbers for the incremental solver on some hardware, so the claimed speedup is partly a statement about the chosen baseline and cache behavior.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an incremental exact assignment algorithm for the N×N bipartite matching problem arising in crowd tracking. The method grows the matching from 1×1 to N×N by adding one trajectory/detection pair at a time, maintaining dual potentials that are claimed to be exactly optimal for the current subproblem, and uses a Dijkstra augmenting-path search for each extension. A diagonal-reordering invariant, SparseReorder, is introduced to keep the matching in canonical form. The paper claims the same optimal matching as the Hungarian algorithm with O(N²L log k/C) complexity and 3.7–6.5× speedup on synthetic crowd instances up to N=5000, with correctness verified against Hungarian. The evaluation is entirely on synthetic clustered graphs (Scenarios S1–S3); no real MOT data or code are provided.
Significance. If the complexity claim and the measured speedups hold, the paper would make exact data association in dense crowds substantially cheaper and would provide a useful extension of the incremental assignment literature. The practice of verifying every reported run against the Hungarian optimum is a strength, as is the careful construction of block-sparse crowd-like test instances. However, the central complexity gain rests on the unmeasured augmenting-path length L, and the potential initialization as written is circular. The advertised speedup range is also not consistent with the full table of results. The paper's practical claim for real-time crowd tracking is not yet supported because no real tracking data are used. These issues are load-bearing for the main claims, so the manuscript should be revised before acceptance.
major comments (4)
- [§5.3, Eqs. (9)–(10)] The potential initialization is circular as written. Equation (9) defines Y_n using X_i for all i≤n, which includes X_n, while Eq. (10) defines X_n using Y_n. LabelCompanion therefore cannot be executed in the order presented, and Theorem 1's inductive step — which relies on LabelCompanion to establish feasibility for node n — is not substantiated. Please correct the index ranges (presumably i<n in Eq. (9)) and provide a complete proof that the resulting potentials are feasible and satisfy complementary slackness.
- [Table 2 / §6.3] The complexity bound O(N²L log k/C) and the assertion of 'short O(1) augmenting paths' depend on L, the average augmenting path length, but L is never precisely defined, measured, or bounded. If L grows like k, the incremental bound degrades to O(N³/C), which is no better than dense Hungarian. The runtime scaling in Table 3 is not reassuring: for S1, runtime grows from 0.000458 s at N=200 to 2.981 s at N=5000, a factor of ~6500, far above the N² factor of 625. This suggests L is not constant. A theorem bounding L under the stated cluster model, or at minimum an empirical measurement of L across N, is essential to support the central complexity claim.
- [Abstract vs. Table 3] The abstract and §1.2 claim a 3.7–6.5× speedup over Hungarian, but Table 3 reports speedups as low as 1.1× (S2, N=200), with additional values below 3.7× (e.g., 2.1×, 2.3×, 2.5×). The speedup claim should be revised to the observed range (1.1–6.5×), and the small-N behavior should be discussed rather than obscured by an average or best-case statement.
- [§7] The experimental evaluation is performed exclusively on synthetic graphs generated from the paper's crowd model (Table 1). No real MOT sequences, detector outputs, or trackers are used. The introduction and §7.3 frame the contribution as enabling real-time crowd tracking at 25 fps, but the feasibility numbers are only for generated instances. If the paper is intended as an algorithmic contribution on structured assignment problems, this should be stated clearly; if it is intended for tracking, evaluation on a standard benchmark such as MOT16 or MOT20 is needed. The absence of code also limits reproducibility of the timing claims.
minor comments (5)
- [§2.2 / §3.1] The scale factor is called SCALE in Eq. (1) and S in Eq. (4). Use a single notation throughout.
- [Algorithm 1] SparseReorder is described only informally. The phases 'save', 'apply', and 'reset' are hard to follow, and the invariant maintained by the σ mapping is not defined rigorously. Please give a complete pseudocode and state explicitly how matching cost and potentials are preserved.
- [Algorithm 2, line 6] The line 'parent[j*] ← src[j*]' refers to src without prior definition. Clarify what src stores (presumably the row/node that reached j*).
- [§8] The 'Key distinction' paragraph should be more precise about what is new beyond the author's prior incremental-assignment paper [12]. Simply chaining the primitive N times may not be a sufficient novelty statement; the invariant that makes warm-starting valid should be highlighted.
- [Table 3] The table is not referenced in the running text. Add a sentence such as 'Table 3 reports the raw runtimes and speedups.'
Circularity Check
Self-referential LabelCompanion initialization (Eqs. 9–10) makes the printed optimality proof non-executable; speedups remain measured rather than predicted, so circularity is localized.
-
self definitional
[Section 5.3, Eqs. (9)–(10) (LabelCompanion)]
"Y_n = max_{i≤n, w(i,n)>−∞} (w(i,n) − X_i), (9) X_n = max{ max_{j<n, w(n,j)>−∞} (w(n,j) − Y_j), w(n,n) − Y_n }. (10)"
Equation (9) maximizes over i≤n, so computing Y_n requires the already-unknown X_n; equation (10) defines X_n as a function of Y_n (including w(n,n)−Y_n). The two equations are mutually recursive with no well-founded evaluation order. Since Theorem 1's inductive step relies on 'LabelCompanion ensures feasibility for node n', the paper's proof of the central exactness claim rests on an initialization that is not actually defined/computable as printed. This is a self-reference in the derivation chain, not an independently derived initialization.
full rationale
The paper's headline speedups are direct runtime measurements against a Hungarian baseline on generated block-sparse instances, and every run is verified to match the Hungarian optimum; they are not fitted parameters renamed as predictions. The abstract's 'single augmenting path search from a certified optimal starting point' is the standard incremental-assignment primitive, and the paper invokes the author's own prior work [12,13] for that primitive, but the empirical results would still stand as measurements even if that citation were removed. The concrete circular defect is in Section 5.3: Eq. (9) defines Y_n using X_i for i≤n, including X_n, while Eq. (10) defines X_n using Y_n, making LabelCompanion self-referential and the induction proof in Theorem 1 vacuous as written. The unmeasured augmenting-path length L in Table 2 and the unsupported 'O(1) augmenting paths' assertion are serious correctness/rigor concerns, but they weaken the complexity argument rather than making the speedups circularly constructed. Overall, one self-definitional step is load-bearing for the formal proof, while the central empirical content remains independent, so a moderate score is appropriate.
Assumptions & free parameters
free parameters (4)
- Matching gate radius r =
80, 150, 130 for scenarios S1–S3
- Scale factor S =
1000 in experiments; 10 in walkthrough
- Crowd model parameters C, R, V, σ =
e.g. C=8, R=20, V=25, σ=5 for S1
- Average augmenting path length L =
claimed ≪k; never measured
assumptions (6)
- standard math LP dual complementary slackness (Eqs. 5–6) characterizes optimal assignment
- domain assumption Block-sparse structure: within-gate edges form dense k×k blocks, cross-gate edges are BAD
- standard math Dijkstra on nonnegative reduced costs finds the shortest augmenting path
- domain assumption Incremental warm-start from dual potentials optimal for the (n−1)×(n−1) subproblem is correct
- domain assumption A perfect matching exists in all benchmark instances
- ad hoc to paper SparseReorder is a pure index permutation preserving potentials and matching cost
Cite this review
Pith. "Pith review of Incremental Optimal Assignment for Real-Time Crowd Tracking." pith.science (2026). https://pith.science/paper/GO7GLKL2
@misc{pith2026260721368,
author = {Pith},
title = {Pith review of: Incremental Optimal Assignment for Real-Time Crowd Tracking},
year = {2026},
howpublished = {\url{https://pith.science/paper/GO7GLKL2}},
note = {Machine review of arXiv:2607.21368}
}
abstract
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(N^3)$ time, which becomes a bottleneck for large scenes with hundreds of people. We propose an \emph{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 \times 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 \emph{exactly optimal} for the $(n-1)\times(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 \in [200, 5000]$ people organised into dense clusters, our algorithm achieves \textbf{3.7--6.5$\times$ 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.
Figures
Reference graph
Works this paper leans on
-
[1]
Bewley, Z
A. Bewley, Z. Ge, L. Ott, F. Ramos, B. Upcroft, Simple online and realtime tracking, in: Proceedings of the IEEE International Conference on Image Processing (ICIP), 2016, pp. 3464–3468
2016
-
[2]
Zhang, P
Y . Zhang, P. Sun, Y . Jiang, D. Yu, F. Weng, Z. Yuan, P. Luo, W. Liu, X. Wang, ByteTrack: Multi-object tracking by associating every detec- tion box, in: Proceedings of the European Conference on Computer Vision (ECCV), 2022. 15
2022
-
[3]
H. W. Kuhn, The Hungarian method for the assignment problem, Naval Re- search Logistics Quarterly 2 (1–2) (1955) 83–97
1955
-
[4]
Munkres, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics 5 (1) (1957) 32–38
J. Munkres, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics 5 (1) (1957) 32–38
1957
-
[5]
D. P. Bertsekas, The auction algorithm: A distributed relaxation method for the assignment problem, Annals of Operations Research 14 (1) (1988) 105– 123
1988
-
[6]
P. Dendorfer, H. Rezatofighi, A. Milan, J. Shi, D. Cremers, I. Reid, S. Roth, K. Schindler, L. Leal-Taixé, MOT20: A benchmark for multi object tracking in crowded scenes, arXiv preprint arXiv:2003.09003 (2020)
arXiv 2003
-
[7]
D. F. Crouse, On implementing 2D rectangular assignment algorithms, IEEE Transactions on Aerospace and Electronic Systems 52 (4) (2016) 1679– 1696
2016
-
[8]
Moussaïd, N
M. Moussaïd, N. Perozo, S. Garnier, D. Helbing, G. Theraulaz, The walking behaviour of pedestrian social groups and its impact on crowd dynamics, PLOS ONE 5 (4) (2010) e10047
2010
Show all 35 references
-
[9]
Helbing, P
D. Helbing, P. Molnár, Social force model for pedestrian dynamics, Physical Review E 51 (5) (1995) 4282–4286
1995
-
[10]
Stadler, J
D. Stadler, J. Beyerer, Modelling ambiguous assignments for multi-person tracking in crowds, in: Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, 2022, pp. 133–142
2022
-
[11]
Jonker, A
R. Jonker, A. V olgenant, A shortest augmenting paths algorithm for dense and sparse linear assignment problems, Computing 38 (4) (1987) 325–340
1987
-
[12]
I. H. Toroslu, G. Üçoluk, Incremental assignment problem, Information Sci- ences 177 (6) (2007) 1523–1529
2007
-
[13]
V olgenant, An addendum on the incremental assignment problem, Infor- mation Sciences 178 (22) (2008) 4583
A. V olgenant, An addendum on the incremental assignment problem, Infor- mation Sciences 178 (22) (2008) 4583. 16
2008
-
[14]
Wang, Improving group role assignment problem by incremental assign- ment algorithm, Master’s thesis, Laurentian University, 2019
P. Wang, Improving group role assignment problem by incremental assign- ment algorithm, Master’s thesis, Laurentian University, 2019
2019
-
[15]
G. A. Mills-Tettey, A. Stentz, M. B. Dias, The dynamic Hungarian algorithm for the assignment problem with changing costs, Tech. Rep. CMU-RI-TR- 07-27, Robotics Institute, Carnegie Mellon University, 2007
2007
-
[16]
Carpaneto, P
G. Carpaneto, P. Toth, Algorithm 548: Solution of the assignment problem [H], ACM Transactions on Mathematical Software 6 (1) (1980) 104–111
1980
-
[17]
Dell’Amico, P
M. Dell’Amico, P. Toth, Algorithms and codes for dense assignment prob- lems: the state of the art, Discrete Applied Mathematics 99 (1-3) (2000) 19–48
2000
-
[18]
Kawtikwar, R
S. Kawtikwar, R. Nagi, HyLAC: Hybrid linear assignment solver in CUDA, Journal of Parallel and Distributed Computing 187 (2024) 104838
2024
-
[19]
H. N. Gabow, R. E. Tarjan, Faster scaling algorithms for network problems, Journal of the ACM 36 (4) (1989) 871–889
1989
-
[20]
Ramshaw, R
L. Ramshaw, R. E. Tarjan, On minimum-cost assignments in unbalanced bipartite graphs, Tech. Rep. HPL-2012-40R1, HP Laboratories, 2012
2012
-
[21]
Bochinski, V
E. Bochinski, V . Eiselein, T. Sikora, High-speed tracking-by-detection with- out color or appearance features, in: IEEE International Conference on Ad- vanced Video and Signal Based Surveillance (A VSS), 2018
2018
-
[22]
Cao, et al., Observation-centric SORT: Rethinking SORT for robust multi- object tracking, in: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023
J. Cao, et al., Observation-centric SORT: Rethinking SORT for robust multi- object tracking, in: IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023
2023
-
[23]
Aharon, R
N. Aharon, R. Orfaig, B.-Z. Bobrovsky, BoT-SORT: Robust associations give every detection its due, arXiv preprint arXiv:2206.10464 (2022)
2022 arXiv
-
[24]
Maggiolino, et al., Deep OC-SORT: Multi-pedestrian tracking in crowded scenes, in: IEEE/CVF CVPR Workshops, 2023
G. Maggiolino, et al., Deep OC-SORT: Multi-pedestrian tracking in crowded scenes, in: IEEE/CVF CVPR Workshops, 2023
2023
-
[25]
S. Chan, Y . Zhang, T. Wang, D. Zhang, Online multiple object tracking us- ing joint detection and embedding network, Pattern Recognition 130 (2022) 108793. 17
2022
-
[26]
Y . Zhu, Q. Wang, C. Li, J. Tang, C. Gu, Z. Huang, Visible–thermal multiple object tracking: Large-scale video dataset and progressive fusion approach, Pattern Recognition 161 (2025) 111330
2025
-
[27]
Van Ma, T
L. Van Ma, T. T. D. Nguyen, C. Shim, D. Y . Kim, N. Ha, M. Jeon, Visual multi-object tracking with re-identification and occlusion handling using la- beled random finite sets, Pattern Recognition 156 (2024) 110785
2024
-
[28]
R. M. Karp, U. V . Vazirani, V . V . Vazirani, An optimal algorithm for on-line bipartite matching, in: Proceedings of the ACM Symposium on Theory of Computing (STOC), 1990, pp. 352–358
1990
-
[29]
Mehta, A
A. Mehta, A. Saberi, U. V . Vazirani, V . V . Vazirani, AdWords and general- ized online matching, Journal of the ACM 54 (5) (2007) 22
2007
-
[30]
T. Li, H. Chang, M. Wang, B. Ni, R. Hong, S. Yan, Crowded scene analysis: A survey, IEEE Transactions on Circuits and Systems for Video Technology 25 (3) (2015) 367–386
2015
-
[31]
Zheng, T
X. Zheng, T. Zhong, J. Liu, A study of group effects in pedestrian crowd evacuation: Experiments, modelling and simulation, Safety Science 133 (2021) 105029
2021
-
[32]
W. Ge, R. T. Collins, B. Ruback, Vision-based analysis of small groups in pedestrian crowds, IEEE Transactions on Pattern Analysis and Machine In- telligence 34 (5) (2012) 1003–1016
2012
-
[33]
Milan, et al., MOT16: A benchmark for multi-object tracking, arXiv preprint arXiv:1603.00831 (2016)
A. Milan, et al., MOT16: A benchmark for multi-object tracking, arXiv preprint arXiv:1603.00831 (2016)
2016 arXiv
-
[34]
Shao, et al., CrowdHuman: A benchmark for detecting human in a crowd, arXiv preprint arXiv:1805.00123 (2018)
S. Shao, et al., CrowdHuman: A benchmark for detecting human in a crowd, arXiv preprint arXiv:1805.00123 (2018)
2018 arXiv
-
[35]
Luiten, A
J. Luiten, A. Ošep, P. Dendorfer, P. Torr, A. Geiger, L. Leal-Taixé, B. Leibe, HOTA: A higher order metric for evaluating multi-object tracking, Interna- tional Journal of Computer Vision 129 (2) (2021) 548–578. 18
2021
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.