  Automated tracking is key to many computer vision applications. However, many
tracking systems struggle to perform in real-time due to the high computational
cost of detecting people, especially in ultra high resolution images. We
propose a new algorithm called \emph{PartiMax} that greatly reduces this cost
by applying the person detector only to the relevant parts of the image.
PartiMax exploits information in the particle filter to select $k$ of the $n$
candidate \emph{pixel boxes} in the image. We prove that PartiMax is guaranteed
to make a near-optimal selection with error bounds that are independent of the
problem size. Furthermore, empirical results on a real-life dataset show that
our system runs in real-time by processing only 10\% of the pixel boxes in the
image while still retaining 80\% of the original tracking performance achieved
when processing all pixel boxes.
