  We study the problem of multi-target tracking and data association in video.
We formulate this in terms of selecting a subset of high-quality tracks subject
to the constraint that no pair of selected tracks is associated with a common
detection (of an object). This objective is equivalent to the classic NP-hard
problem of finding a maximum-weight set packing (MWSP) where tracks correspond
to sets and is made further difficult since the number of candidate tracks
grows exponentially in the number of detections. We present a relaxation of
this combinatorial problem that uses a column generation formulation where the
pricing problem is solved via dynamic programming to efficiently explore the
space of tracks. We employ row generation to tighten the bound in such a way as
to preserve efficient inference in the pricing problem. We show the practical
utility of this algorithm for tracking problems in natural and biological video
datasets.
