In graph theory, the shortest path problem can be defined as a problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. A topic that is revered in the field of graph theory and has numerous practical applications including vehicular routing, network designs, etc., the shortest path problem has had several notable approaches to it, including Floyd-Warshall Algorithm, Bellman-Ford Algorithm, and the most renowned Dijkstra's Algorithm. When I came across the algorithm behind Dijkstra's method of solving the shortest path problem in a weighted directed graph (though it can be applied to undirected graphs as well), I wondered if I could come up with my own algorithm for solving the problem using one of Python's data structures: Lists. After over a month of tens of trial-and-error attempts, my peer Syed Abdul Azeem and I came up with an algorithm to solve the problem. The code will not be shared on account of confidentiality, however, you, the reader, might as well be able to figure out the code as we go ahead and explain our approach to a given problem.

This paper introduces a novel technique to track structures in time varying graphs. The method uses a maximum a posteriori approach for adjusting a three-dimensional co-clustering of the source vertices, the destination vertices and the time, to the data under study, in a way that does not require any hyper-parameter tuning. The three dimensions are simultaneously segmented in order to build clusters of source vertices, destination vertices and time segments where the edge distributions across clusters of vertices follow the same evolution over the time segments. The main novelty of this approach lies in that the time segments are directly inferred from the evolution of the edge distribution between the vertices, thus not requiring the user to make any a priori quantization. Experiments conducted on artificial data illustrate the good behavior of the technique, and a study of a real-life data set shows the potential of the proposed approach for exploratory data analysis.

We study transportation problems where robots have to deliver packages and can transfer the packages among each other. Specifically, we study the package-exchange robot-routing problem (PERR), where each robot carries one package, any two robots in adjacent locations can exchange their packages, and each package needs to be delivered to a given destination. We prove that exchange operations make all PERR instances solvable. Yet, we also show that PERR is NP-hard to approximate within any factor less than 4/3 for makespan minimization and is NP-hard to solve for flowtime minimization, even when there are only two types of packages. Our proof techniques also generate new insights into other transportation problems, for example, into the hardness of approximating optimal solutions to the standard multi-agent path-finding problem (MAPF). Finally, we present optimal and suboptimal PERR solvers that are inspired by MAPF solvers, namely a flow-based ILP formulation and an adaptation of conflict-based search. Our empirical results demonstrate that these solvers scale well and that PERR instances often have smaller makespans and flowtimes than the corresponding MAPF instances.