Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse
0
🚀
Sign in to get full access
Preliminaries
The paper considers a recoverable version of the classic shortest path problem in a directed graph with nonnegative arc costs. The recoverable problem allows modifying the initial shortest path by applying a limited recovery action, where the modified path must be within a prescribed neighborhood of the initial path. Three types of neighborhoods are considered: arc inclusion, arc exclusion, and arc symmetric difference.
The paper introduces the recoverable robust shortest path (Rec Rob SP) problem, which seeks a first-stage path that minimizes the sum of the initial path cost and the maximum cost of the second-stage path over an uncertainty set of second-stage arc costs. It also introduces the adversarial shortest path (Adv SP) problem, which seeks the worst-case second-stage path cost for a given first-stage path.
The paper shows that the Rec Rob SP problem is strongly NP-hard for the arc exclusion and arc symmetric difference neighborhoods. It also proves that the Adv SP problem is Π2^p-hard for these neighborhoods. These results strengthen the previously known complexity results for these problems.
Hardness of the adversarial problem
The paper discusses the problem of Adversarial Shortest Path (Adv SP) under discrete budgeted uncertainty. It shows that this problem is Π2P-complete, even when the recovery parameter k is as small as 2.
The paper starts by introducing the ∀(Γ)∃CNF-SAT problem, which is Π2P-complete. It then uses this problem to show that the decision version of Adv SP is also Π2P-complete, for two different neighborhood structures: Φexcl(X,k) and Φsym(X,k).
Specifically, the paper demonstrates a reduction from ∀(Γ)∃CNF-SAT to the decision version of Adv SP. It shows that an instance of ∀(Γ)∃CNF-SAT is a yes-instance if and only if the corresponding instance of Adv SP is a yes-instance. This establishes the Π2P-hardness of Adv SP.
The paper also proves that Adv SP under the 𝒰(Γd) uncertainty set is Π2P-hard and Π2P-hard to approximate, even when k=2. These results are summarized in Corollaries 1 and 2.
In conclusion, the paper establishes the computational complexity of the Adv SP problem, showing that it is a challenging optimization problem that belongs to the Π2P complexity class.
Hardness of the recoverable robust problem
There is no text provided in this section to summarize. The section only contains a problem statement and definition without any additional explanatory text.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
🚀
0
Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse
Marcel Jackiewicz, Adam Kasperski, Pawe{l} Zieli'nski
In this paper the recoverable robust shortest path problem is investigated. Discrete budgeted interval uncertainty representation is used to model uncertain second-stage arc costs. The known complexity results for this problem are strengthened. It is shown that it is Sigma_3^p-hard for the arc exclusion and the arc symmetric difference neighborhoods. Furthermore, it is also proven that the inner adversarial problem for these neighborhoods is Pi_2^p-hard.
Read more4/1/2024
0
Robust Stochastic Shortest-Path Planning via Risk-Sensitive Incremental Sampling
Clinton Enwerem, Erfaun Noorani, John S. Baras, Brian M. Sadler
With the pervasiveness of Stochastic Shortest-Path (SSP) problems in high-risk industries, such as last-mile autonomous delivery and supply chain management, robust planning algorithms are crucial for ensuring successful task completion while mitigating hazardous outcomes. Mainstream chance-constrained incremental sampling techniques for solving SSP problems tend to be overly conservative and typically do not consider the likelihood of undesirable tail events. We propose an alternative risk-aware approach inspired by the asymptotically-optimal Rapidly-Exploring Random Trees (RRT*) planning algorithm, which selects nodes along path segments with minimal Conditional Value-at-Risk (CVaR). Our motivation rests on the step-wise coherence of the CVaR risk measure and the optimal substructure of the SSP problem. Thus, optimizing with respect to the CVaR at each sampling iteration necessarily leads to an optimal path in the limit of the sample size. We validate our approach via numerical path planning experiments in a two-dimensional grid world with obstacles and stochastic path-segment lengths. Our simulation results show that incorporating risk into the tree growth process yields paths with lengths that are significantly less sensitive to variations in the noise parameter, or equivalently, paths that are more robust to environmental uncertainty. Algorithmic analyses reveal similar query time and memory space complexity to the baseline RRT* procedure, with only a marginal increase in processing time. This increase is offset by significantly lower noise sensitivity and reduced planner failure rates.
Read more8/19/2024
0
$A^*$ for Graphs of Convex Sets
Kaarthik Sundar, Sivakumar Rathinam
We present a novel algorithm that fuses the existing convex-programming based approach with heuristic information to find optimality guarantees and near-optimal paths for the Shortest Path Problem in the Graph of Convex Sets (SPP-GCS). Our method, inspired by $A^*$, initiates a best-first-like procedure from a designated subset of vertices and iteratively expands it until further growth is neither possible nor beneficial. Traditionally, obtaining solutions with bounds for an optimization problem involves solving a relaxation, modifying the relaxed solution to a feasible one, and then comparing the two solutions to establish bounds. However, for SPP-GCS, we demonstrate that reversing this process can be more advantageous, especially with Euclidean travel costs. In other words, we initially employ $A^*$ to find a feasible solution for SPP-GCS, then solve a convex relaxation restricted to the vertices explored by $A^*$ to obtain a relaxed solution, and finally, compare the solutions to derive bounds. We present numerical results to highlight the advantages of our algorithm over the existing approach in terms of the sizes of the convex programs solved and computation time.
Read more7/26/2024
📈
0
Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
Vignesh Manoharan, Vijaya Ramachandran
We present several results in the CONGEST model on round complexity for Replacement Paths (RPaths), Minimum Weight Cycle (MWC), and All Nodes Shortest Cycles (ANSC). We study these fundamental problems in both directed and undirected graphs, both weighted and unweighted. Many of our results are optimal to within a polylog factor: For an $n$-node graph $G$ we establish near linear lower and upper bounds for computing RPaths if $G$ is directed and weighted, and for computing MWC and ANSC if $G$ is weighted, directed or undirected; near $sqrt{n}$ lower and upper bounds for undirected weighted RPaths; and $Theta(D)$ bound for undirected unweighted RPaths. We also present lower and upper bounds for approximation versions of these problems, notably a $(2-(1/g))$-approximation algorithm for undirected unweighted MWC that runs in $tilde{O}(sqrt{n}+D)$ rounds, improving on the previous best bound of $tilde{O}(sqrt{ng}+D)$ rounds, where $g$ is the MWC length. We present a $(1+epsilon)$-approximation algorithm for directed weighted RPaths, which beats the linear lower bound for exact RPaths.
Read more5/22/2024