Research Seminar - Complexity Analysis of Restricted Pickup-and-Delivery Problems and A Bayesian Network Model for Document Rank

Dr. Xing Tan, a candidate for the Orillia LTA position in the Department of Computer Science will present a seminar.

Title: Complexity Analysis of Restricted Pickup-and-Delivery Problems and A Bayesian Network Model for Document Ranking

Abstract: The presentation introduces our recent research progress, and it contains two main parts. In part I, we perform complexity-theoretic and algorithmic analysis on computationally boundary cases of pickup-and-delivery problems and vehicle routing problems, that is, problems whose tasks are subject to precedence constraints or time-window constraints (PDPC, PDTW); and problems whose vehicles are subject to fuel-tank capacity constraints (GreenPD). We have identified several, either strongly or weakly, NP-hard problems, and additionally other ones that are polynomial-time solvable. In part II, we demonstrate how one can address the classical document ranking problem in information retrieval, using a straightforward Bayesian network model. Effectiveness of the approach is empirically verified.

Zoom link https://lakeheadu.zoom.us/j/94650647205?pwd=VDUvdmFkOThGN3poVFhTK1Nycno5... Meeting ID: 946 5064 7205 Passcode: 8297