The task of visually tracking multiple objects remains an active field of algorithm development even after several decades of research in the computer vision community. One reason it remains an active research area is that identifying and maintaining the location of multiple targets in a video recording can be approached from several perspectives depending on the application's needs. Another reason is simply that the general problem of automated tracking can be very challenging. Moreover, compared to tracking a single target, multi-target tracking can grow significantly more complicated. Similar appearances between different objects, crowded scenes, and inter-object occlusions among a sometimes unknown and fluctuating number of objects are additional difficulties in multi-object scenarios. Challenges such as these collectively manifest into three broader design decisions often faced by multiple object tracking (MOT) algorithms. First is how to handle what one could think of as "easy" and "hard" regions of a trajectory. The second is how to handle the sheer number of possible explanations of the data. The third is how do you model certainty. This dissertation aims to better model the uncertainty among possible answers to the tracking data in offline tracking scenarios (i.e., input is the entire video, not frame-by-frame). Furthermore, the method does so in a way that utilizes the information within the "hard to track" regions --- information that is typically not used. The way we do this results in accurate tracking that is better suited for video analysis pipelines that may need to filter or correct any tracking errors that did occur.