Train-Passenger Matching problem: original definition and complexity analysis

This thesis addresses a real-world problem: determining the means of transportation used by an individual given the trajectory they have followed. The problem is first formalized in purely mathematical terms, abstracting from real-world ambiguities and focusing on the essential elements of the trajectory and transportation modes. Through this formalization, the problem is modeled as a decision problem within the framework of theoretical computer science. Subsequently, we introduce the fundamental tools of computational complexity theory to rigorously analyze the problem's inherent difficulty. The main contribution of this work is the design and analysis of a greedy algorithm that efficiently solves the problem in polynomial time. We prove the correctness and optimality of the algorithm within the formal model.