  The paper revisits the robust $s$-$t$ path problem, one of the most
fundamental problems in robust optimization. In the problem, we are given a
directed graph with $n$ vertices and $k$ distinct cost functions (scenarios)
defined over edges, and aim to choose an $s$-$t$ path such that the total cost
of the path is always provable no matter which scenario is realized. With the
view of each cost function being associated with an agent, our goal is to find
a common $s$-$t$ path minimizing the maximum objective among all agents, and
thus create a fair solution for them. The problem is hard to approximate within
$o(\log k)$ by any quasi-polynomial time algorithm unless $\mathrm{NP}
\subseteq \mathrm{DTIME}(n^{\mathrm{poly}\log n})$, and the best approximation
ratio known to date is $\widetilde{O}(\sqrt{n})$ which is based on the natural
flow linear program. A longstanding open question is whether we can achieve a
polylogarithmic approximation even when a quasi-polynomial running time is
allowed.
  We give the first polylogarithmic approximation for robust $s$-$t$ path since
the problem was proposed more than two decades ago. In particular, we introduce
a $O(\log n \log k)$-approximate algorithm running in quasi-polynomial time.
The algorithm is built on a novel linear program formulation for a
decision-tree-type structure which enables us to get rid of the
$\Omega(\max\{k,\sqrt{n}\})$ integrality gap of the natural flow LP. Further,
we also consider some well-known graph classes, e.g., graphs with bounded
treewidth, and show that the polylogarithmic approximation can be achieved
polynomially on these graphs. We hope the new proposed techniques in the paper
can offer new insights into the robust $s$-$t$ path problem and related
problems in robust optimization.
