Faster parametric shortest path and minimum‐balance algorithms

DOI10.1002/NET.3230210206zbMath0719.90087arXivcs/0205041OpenAlexW3105140593MaRDI QIDQ5752305

James B. Orlin, Neal E. Young, Robert Endre Tarjan

Publication date: 1991

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0205041

zbMATH Keywords

shortest pathsdirected multigraphparametric shortest path problemcycle-cancelling min-cost max-flow algorithmsmin-balance problemminimum-mean-cost cycle problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (42)

Balancing problems in acyclic networks ⋮ An FPTAS for the parametric knapsack problem ⋮ The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory ⋮ Max-balanced flows in oriented matroids ⋮ The complexity of mean payoff games on graphs ⋮ An approximation algorithm for a general class of parametric optimization problems ⋮ Computing the sequence of \(k\)-cardinality assignments ⋮ How to compute least infeasible flows ⋮ A general approximation method for bicriteria minimization problems ⋮ Fractional 0-1 programming: applications and algorithms ⋮ Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory ⋮ The quickest flow problem ⋮ Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint ⋮ Near-linear convergence of the random Osborne algorithm for matrix balancing ⋮ Unnamed Item ⋮ The representation polyhedron of a semiorder. ⋮ Response time analysis of digraph real-time tasks scheduled with static priority: generalization, approximation, and improvement ⋮ Possibilistic bottleneck combinatorial optimization problems with ill-known weights ⋮ Vyacheslav Tanaev: contributions to scheduling and related areas ⋮ Online Regret Bounds for Markov Decision Processes with Deterministic Transitions ⋮ On the complexity of time-dependent shortest paths ⋮ A minimum mean cycle cancelling method for nonlinear multicommodity flow problems ⋮ An algorithm for single-source shortest paths enumeration in parameterized weighted graphs ⋮ Computing periodic request functions to speed-up the analysis of non-cyclic task models ⋮ About the minimum mean cycle-canceling algorithm ⋮ Approximation schemes for the parametric knapsack problem ⋮ Computing the throughput of concatenation state machines ⋮ Characterizations of max-balanced flows ⋮ Approximating the minimum cycle mean ⋮ Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chip ⋮ Online regret bounds for Markov decision processes with deterministic transitions ⋮ A fast parametric assignment algorithm with applications in max-algebra ⋮ Directed shortest paths via approximate cost balancing ⋮ An FPTAS for the knapsack problem with parametric weights ⋮ A parametric critical path problem and an application for cyclic scheduling ⋮ On visualization scaling, subeigenvectors and Kleene stars in max algebra ⋮ A comparison of schedulability analysis methods using state and digraph models for the schedulability analysis of synchronous FSMs ⋮ Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights ⋮ An approximation algorithm for a general class of multi-parametric optimization problems ⋮ Max-Balanced Hungarian Scalings ⋮ Extensions of Dinkelbach's algorithm for solving nonlinear fractional programming problems ⋮ The single most vital arc in the most economical path problem -- a parametric analysis

Cites Work

• A characterization of the minimum cycle mean in a digraph

This page was built for publication: Faster parametric shortest path and minimum‐balance algorithms