2020/06/25 by Andrea Horňáková, Andrea Hornakova, Hornakova, Andrea +6 · 84 citations
Computer Science · Environmental Science · Mathematics · Social Sciences · #Algorithm #Artificial intelligence #Computer Vision and Pattern Recognition (cs.CV) #Computer science #Cutting-plane method #Discrete Mathematics (cs.DM) #Discrete mathematics #Disjoint sets #FOS: Computer and information sciences #Human Mobility and Location-Based Analysis #Integer programming #Linear programming #Linear programming relaxation #Mathematical optimization #Mathematics #Object (grammar) #Path (computing) #Range (aeronautics) #Reduction (mathematics) #Relaxation (psychology) #Tracking (education) #Video Surveillance and Tracking Methods #Wildlife-Road Interactions and Conservation #cs.CV #cs.DM
paper · pdf · doi:10.48550/arxiv.2006.14550
published in arXiv (Cornell University) (Cornell University) · ICML 2020, Codebase available at https://github.com/AndreaHor/LifT_Solver
arxiv created 2020/06/25 · openalex publication_date 2020/06/25 · arxiv updated 2020/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an extension to the disjoint paths problem in which additional lifted edges are introduced to provide path connectivity priors. We call the resulting optimization problem the lifted disjoint paths problem. We show that this problem is NP-hard by reduction from integer multicommodity flow and 3-SAT. To enable practical global optimization, we propose several classes of linear inequalities that produce a high-quality LP-relaxation. Additionally, we propose efficient cutting plane algorithms for separating the proposed linear inequalities. The lifted disjoint path problem is a natural model for multiple object tracking and allows an elegant mathematical formulation for long range temporal interactions. Lifted edges help to prevent id switches and to re-identify persons. Our lifted disjoint paths tracker achieves nearly optimal assignments with respect to input detections. As a consequence, it leads on all three main benchmarks of the MOT challenge, improving significantly over state-of-the-art.