M.Sc Thesis

M.Sc StudentKhawaja Tamer
SubjectNear Linear Time Approximation for Multi- Constrained
Shortest Path
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Ariel Orda
DR. Dean H. Lorenz
Full Thesis textFull thesis text - English Version


We generalize Bernstein paper Near Linear Time (1??)-Approximation for Restricted Shortest Path in Undirected Graphs”, to the case of multi-restriction in which we are given two vertices s,t and the goal is to find the shortest path subject to multiple side constraints. More formally, rather than just having a single distance-weight and single delay-weight, each edge has a single distance-weight and multiple delay-weights. We are given a k-vector of threshods T which corresponds to maximum delay we can afford and the goal is to find the s-t path which minimize total distance while still having delay lengths at most T.

There are many applications for this problem, as it can model situation where we need a path that has to achieve some balanced tradeoff between distance and other side constraints. The exact version of the problem is known to be NP-Hard. But there has been a series of results on (1??)-approximations, which culminated in O(mn/epsilon) for general graphs in 2012.

We generalize Bernstein approach to get the first result that breaks through this barrier, achieving close to linear running time, technically O(mnd) for all d>0.

It still has the same drawbacks, however. It is randomized (Las Vegas), it only works for undirected graphs, and it approximate all parameters (distance and all delays ).

These results could potentially be generalized to work for directed graphs and to approximate only paprt of the parameters and not all.