Faster parametric shortest path and minimum‐balance algorithms
From MaRDI portal
Publication:5752305
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
shortest pathsdirected multigraphparametric shortest path problemcycle-cancelling min-cost max-flow algorithmsmin-balance problemminimum-mean-cost cycle problem
Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Abstract computational complexity for mathematical programming problems (90C60)
Related Items
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, 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
