In this paper, we view multiple object tracking as a graphpartitioning problem. Given any object detector, we build the graph ofall detections and aim to partition it into trajectories. To quantifythe similarity of any two detections, we consider local cues such as pointtracks and speed, global cues such as appearance, as well as intermediateones such as trajectory straightness. These different clues are dealt jointlyto make the approach robust to detection mistakes (missing or extradetections). We thus define a Conditional Random Field and optimizeit using an efficient combination of message passing and move-makingalgorithms. Our approach is fast on video batch sizes of hundreds offrames. Competitive and stable results on varied videos demonstrate the robustnessand efficiency of our approach.