Related papers: Tightest Admissible Shortest Path

Tightest Admissible Shortest Path

URL: http://arxiv.org/abs/2308.08453v2
Date: Wed, 27 Mar 2024 21:46:41 GMT
Title: Tightest Admissible Shortest Path
Authors: Eyal Weiss, Ariel Felner, Gal A. Kaminka,
Abstract summary: shortest path problem in graphs is fundamental to AI. We introduce the problem of finding the admissible shortest path (TASP), a path with the tightest suboptimality bound on the optimal cost. We present a complete algorithm for solving TASP, with guarantees on solution quality.
Score: 4.928034044959278
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The shortest path problem in graphs is fundamental to AI. Nearly all variants of the problem and relevant algorithms that solve them ignore edge-weight computation time and its common relation to weight uncertainty. This implies that taking these factors into consideration can potentially lead to a performance boost in relevant applications. Recently, a generalized framework for weighted directed graphs was suggested, where edge-weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. We build on this framework to introduce the problem of finding the tightest admissible shortest path (TASP); a path with the tightest suboptimality bound on the optimal cost. This is a generalization of the shortest path problem to bounded uncertainty, where edge-weight uncertainty can be traded for computational cost. We present a complete algorithm for solving TASP, with guarantees on solution quality. Empirical evaluation supports the effectiveness of this approach.

Related papers

Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
We propose a first-order proximal gradient algorithm to solve the perspective relaxation of the problem within a BnB framework. We show that our approach significantly accelerates dual bound computations and is highly effective in providing optimality certificates for large-scale problems.
arXiv Detail & Related papers (2025-02-13T17:14:18Z)
Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
Pathwise methods allow to efficiently compute the full path for penalized estimators. We apply these algorithms to the penalized estimation of processes observed at discrete times.
arXiv Detail & Related papers (2024-12-05T10:38:29Z)
Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
We introduce a novel approach based on the greedy algorithm by opt_einsum that computes efficient contraction paths in less time. With our approach, we are even able to compute paths for large problems where modern algorithms fail.
arXiv Detail & Related papers (2024-05-08T09:25:39Z)
Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
arXiv Detail & Related papers (2022-11-14T21:54:31Z)
A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates [13.046825574678579]
The shortest path problem in graphs is a cornerstone of AI theory and applications. We present a framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.
arXiv Detail & Related papers (2022-08-22T22:07:27Z)
Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
Various algorithms for reinforcement learning (RL) exhibit dramatic variation in their convergence rates as a function of problem structure. This research provides guarantees that explain textitex post the performance differences observed. A natural next step is to convert these theoretical guarantees into guidelines that are useful in practice.
arXiv Detail & Related papers (2022-01-21T04:25:35Z)
STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
arXiv Detail & Related papers (2021-11-01T15:43:36Z)
Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
arXiv Detail & Related papers (2021-09-23T17:38:24Z)
Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
Path finding is a well-studied problem in AI, which is often framed as graph search. We present two algorithms, grounded in the same idea, that can obtain provably optimal solutions to the considered problem.
arXiv Detail & Related papers (2021-04-14T07:59:53Z)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
arXiv Detail & Related papers (2020-10-23T09:12:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.