2026-05-31T07:22:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20249 2024-07-02T07:52:54Z ddc:004 open_access

Polylogarithmic Approximations for Robust s-t Path Li, Shi Xu, Chenyang Zhang, Ruilong Approximation Algorithm Randomized LP Rounding Robust s-t Path 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. Viewing each cost function as an agent, our goal is to find a fair s-t path, which minimizes the maximum cost among all agents. The problem is NP-hard to approximate within a factor of o(log k) unless NP ⊆ DTIME(n^{polylog n}), and the best-known approximation ratio is Õ(√n), which is based on the natural flow linear program. A longstanding open question is whether we can achieve a polylogarithmic approximation for the problem; it remains open even if a quasi-polynomial running time is allowed. Our main result is a O(log n log k) approximation for the Robust s-t Path problem in quasi-polynomial time, solving the open question in the quasi-polynomial time regime. The algorithm is built on a novel linear program formulation for a decision-tree-type structure, which enables us to overcome the Ω(√n) integrality gap for the natural flow LP. Furthermore, we show that for graphs with bounded treewidth, the quasi-polynomial running time can be improved to a polynomial. We hope our techniques can offer new insights into this problem and other related problems in robust optimization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shi Li and Chenyang Xu and Ruilong Zhang 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.106 urn:nbn:de:0030-drops-202497 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.106 eng https://creativecommons.org/licenses/by/4.0/legalcode