Parametric shortest path algorithms with an application to cyclic staffing
From MaRDI portal
Publication:1149254
DOI10.1016/0166-218X(81)90026-3zbMath0453.68032WikidataQ59592772 ScholiaQ59592772MaRDI QIDQ1149254
Richard M. Karp, James B. Orlin
Publication date: 1981
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items
Computing maximum mean cuts, An FPTAS for the parametric knapsack problem, The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory, Optimal Embedding into Star Metrics, The cost-to-time ratio problem for large or infinite graphs, An approximation algorithm for a general class of parametric optimization problems, Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs, Computing the sequence of \(k\)-cardinality assignments, A new pivot selection rule for the network simplex algorithm, Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory, Maximum flows in parametric graph templates, The quickest flow problem, The multi-weighted spanning tree problem, Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint, Vyacheslav Tanaev: contributions to scheduling and related areas, Cyclic flowshop scheduling with operators and robots: Vyacheslav Tanaev's vision and lasting contributions, 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, New scaling algorithms for the assignment and minimum mean cycle problems, Approximation schemes for the parametric knapsack problem, Polynomial-time primal simplex algorithms for the minimum cost network flow problem, Parametric multiroute flow and its application to multilink-attack network, Approximating the minimum cycle mean, Multiple Routing Strategies in a Labelled Network, Facets of the \(p\)-cycle polytope, A fast parametric assignment algorithm with applications in max-algebra, A polyhedral study of the acyclic coloring problem, An FPTAS for the knapsack problem with parametric weights, Cycle-based facets of chromatic scheduling polytopes, A parametric critical path problem and an application for cyclic scheduling, An approximation algorithm for a general class of multi-parametric optimization problems, A heuristic approach to hard constrained shortest path problems, The single most vital arc in the most economical path problem -- a parametric analysis, Approximate binary search algorithms for mean cuts and cycles, Computing optimal scalings by parametric network algorithms
Cites Work
