Randomized Shortest-Path Problems: Two Related Models

DOI10.1162/NECO.2009.11-07-643MaRDI QIDQ5323768zbMATH OpenOpenAlexWikidataFDO

Authors Marco Saerens, Youssef Achbany, François Fouss, Luh Yen

Publication date 30 July 2009

Published in Neural Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1162/neco.2009.11-07-643

zbMATH Keywords

expected Shannon entropy spreadfinite Markov chainnecessary conditionsoptimal policy

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Stochastic network models in operations research (90B15)

Recommendations

• Sparse randomized shortest paths routing with Tsallis divergence regularization
• Randomized shortest paths with net flows and capacity constraints
• Shortest paths in stochastic networks with correlated link costs
• scientific article; zbMATH DE number 4057261
• Stochastic shortest path problems with recourse

Cites work

• A Mathematical Theory of Communication
• Algorithms on Strings, Trees and Sequences
• Approximate Dynamic Programming
• Biological Sequence Analysis
• Characteristic functions of directed graphs and applications to stochastic equilibrium problems
• Decomposition of Path Choice Entropy in General Transport Networks
• Direct Methods for Sparse Linear Systems
• Elements of Information Theory
• Entropy maximization for Markov and semi-Markov processes
• Entropy Rate and Maximum Entropy Methods for Countable Semi-Markov Chains
• Fastest Mixing Markov Chain on a Graph
• Graphs, networks and algorithms.
• scientific article; zbMATH DE number 5987898 (Why is no real title available?)
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 4215340 (Why is no real title available?)
• scientific article; zbMATH DE number 3711960 (Why is no real title available?)
• scientific article; zbMATH DE number 108390 (Why is no real title available?)
• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• scientific article; zbMATH DE number 3514781 (Why is no real title available?)
• scientific article; zbMATH DE number 1237738 (Why is no real title available?)
• scientific article; zbMATH DE number 1239298 (Why is no real title available?)
• scientific article; zbMATH DE number 1321699 (Why is no real title available?)
• scientific article; zbMATH DE number 1160035 (Why is no real title available?)
• scientific article; zbMATH DE number 1455133 (Why is no real title available?)
• scientific article; zbMATH DE number 773958 (Why is no real title available?)
• scientific article; zbMATH DE number 2201583 (Why is no real title available?)
• Information Theory and Statistical Mechanics
• Planning Algorithms
• Quantum computer feasibility and quantum mechanics interpretation
• Space-time approach to non-relativistic quantum mechanics
• The entropy of Markov trajectories
• The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem

Cited in

(18)

• The shortest-path problem for graphs with random arc-lengths
• Interpolating between random walks and optimal transportation routes: flow with multiple sources and targets
• Developments in the theory of randomized shortest paths with a comparison of graph node distances
• Sparse randomized shortest paths routing with Tsallis divergence regularization
• A simple extension of the bag-of-paths model weighting path lengths by a Poisson distribution
• Randomized shortest paths with net flows and capacity constraints
• Different closed-form expressions for generalized entropy rates of Markov chains
• A bag-of-paths framework for network data analysis
• The stochastic shortest-path problem for Markov chains with infinite state space with applications to nearest-neighbor lattice chains
• Probabilistic choice (models) as a result of balancing multiple goals
• Design of biased random walks on a graph with application to collaborative recommendation
• Factorizing shortest paths with randomized optimum models
• Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem
• The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms
• Maximum likelihood estimation for randomized shortest paths with trajectory data
• A sum-over-paths extension of edit distances accounting for all sequence alignments
• Semi-supervised classification and betweenness computation on large, sparse, directed graphs
• Agglomerative clustering via maximum incremental path integral

Describes a project that uses

Uses Software

• GMRFLib

This page was built for publication: Randomized Shortest-Path Problems: Two Related Models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5323768)