Tracking and recognition of objects, such as faces, in video is commonly accomplished in independent fashion. However, important information is contained in both problems that could be used to increase the overall recognition accuracy. We propose a unified integer program (IP) based framework for multi-object tracking and recognition in video, where the two tasks are conducted jointly, using a set of natural constraints. In the domain of multiple face recognition, pairing constraints limit the number of objects that can be labeled with the same identity while temporal constraints allow the important information about objects identities's to be used to improve tracking. Despite its appeal, the solving the IP objective can be inefficient in real-world scenarios. For this reason, we employ an approximate Generalized Assignment Problem (GAP) solution to the IP problem, which is both theoretically appealing and computationally highly efficient. We finally demonstrate that the IP and GAP methods of conducting multi-object tracking and recognition can be successfully applied to real world videos where the traditional methods of conducting tracking and recognition separately fail to produce satisfactory results.