M.Sc Student | Khawaja Tamer |
---|---|

Subject | Near Linear Time Approximation for Multi- Constrained Shortest Path |

Department | Department of Electrical Engineering |

Supervisors | Professor Ariel Orda |

Dr. Dean H. Lorenz | |

Full Thesis text |

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

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(mn ^{d}) 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.