This paper presents globally optimal and efficient algorithms for multi-object tracking in video sequences. The problem is formulated using a cost function that requires estimating the number of tracks, as well as their birth and death states. The authors show that a greedy algorithm, which sequentially instantiates tracks using shortest path computations on a flow network, can achieve the global solution. This approach allows for the embedding of pre-processing steps such as non-maximum suppression within the tracking algorithm. Additionally, a near-optimal algorithm based on dynamic programming is introduced, which runs in linear time with respect to the number of objects and the sequence length. The algorithms are fast, simple, and scalable, enabling the processing of dense input data and achieving state-of-the-art performance. The paper introduces a novel analysis of an integer linear program (ILP) formulation of multi-object tracking. It shows that the optimal solution can be derived by a local modification to the solution obtained for k tracks. This insight leads to the development of an approximate greedy algorithm with linear time complexity in sequence length. The algorithms are shown to be effective in processing large input sequences and modeling long occlusions, producing state-of-the-art results on benchmark datasets. The paper also presents experimental results on the Caltech Pedestrian dataset and the ETHMS dataset, demonstrating the effectiveness of the proposed algorithms. The results show that the algorithms outperform previous state-of-the-art methods in terms of detection accuracy and running time. The algorithms are shown to be robust to occlusions and can maintain track identities even when objects are occluded. The algorithms are also shown to be efficient, with the proposed dynamic programming approach running in linear time with respect to the number of objects and sequence length. The results demonstrate that the proposed algorithms are effective in tracking a variable number of objects in video sequences.This paper presents globally optimal and efficient algorithms for multi-object tracking in video sequences. The problem is formulated using a cost function that requires estimating the number of tracks, as well as their birth and death states. The authors show that a greedy algorithm, which sequentially instantiates tracks using shortest path computations on a flow network, can achieve the global solution. This approach allows for the embedding of pre-processing steps such as non-maximum suppression within the tracking algorithm. Additionally, a near-optimal algorithm based on dynamic programming is introduced, which runs in linear time with respect to the number of objects and the sequence length. The algorithms are fast, simple, and scalable, enabling the processing of dense input data and achieving state-of-the-art performance. The paper introduces a novel analysis of an integer linear program (ILP) formulation of multi-object tracking. It shows that the optimal solution can be derived by a local modification to the solution obtained for k tracks. This insight leads to the development of an approximate greedy algorithm with linear time complexity in sequence length. The algorithms are shown to be effective in processing large input sequences and modeling long occlusions, producing state-of-the-art results on benchmark datasets. The paper also presents experimental results on the Caltech Pedestrian dataset and the ETHMS dataset, demonstrating the effectiveness of the proposed algorithms. The results show that the algorithms outperform previous state-of-the-art methods in terms of detection accuracy and running time. The algorithms are shown to be robust to occlusions and can maintain track identities even when objects are occluded. The algorithms are also shown to be efficient, with the proposed dynamic programming approach running in linear time with respect to the number of objects and sequence length. The results demonstrate that the proposed algorithms are effective in tracking a variable number of objects in video sequences.