New scaling algorithms for the assignment and minimum mean cycle problems
From MaRDI portal
Publication:1190599
DOI10.1007/BF01586040zbMath0764.90059WikidataQ59592667 ScholiaQ59592667MaRDI QIDQ1190599
James B. Orlin, Ravindra K. Ahuja
Publication date: 26 September 1992
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
assignmentbipartite matchingauction algorithmsuccessive shortest path algorithmscaling algorithmsmean cost of a cycleminimum mean cycle problem
Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Boolean programming (90C09)
Related Items
Fair matchings and related problems, Computing maximum mean cuts, An approximate binary search algorithm for the multiple-choice knapsack problem, The assignment problem revisited, The complexity of mean payoff games on graphs, Understanding retiming through maximum average-delay cycles, Approximating a class of combinatorial problems with rational objective function, Linear-Time Approximation for Maximum Weight Matching, The container transshipment problem: searching representation landscapes with metaheuristic algorithms, Incremental assignment problem, Solving MIPs via scaling-based augmentation, A new algorithm for the assignment problem: An alternative to the Hungarian method, Algorithms for dense graphs and networks on the random access computer, A dual approximation approach to weighted matroid intersection, Fractional 0-1 programming: applications and algorithms, A Fast Approximation Algorithm For The Subset-Sum Problem, Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory, Satisfiability problems on intervals and unit intervals, A branch‐and‐cut algorithm for a bipartite graph construction problem in digital communication systems, The quickest flow problem, On maximum ratio clique relaxations, Interval graphs with side (and size) constraints, Vyacheslav Tanaev: contributions to scheduling and related areas, An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem, A simple reduction from maximum weight matching to maximum cardinality matching, Algorithms and codes for dense assignment problems: The state of the art, On a matching distance between rooted phylogenetic trees, A cost-scaling algorithm for \(0-1\) submodular flows, Computing the throughput of concatenation state machines, Approximating the minimum cycle mean, Scheduling unit-length jobs with machine eligibility restrictions, On covering by translates of a set, Faster algorithms for quantitative verification in bounded treewidth graphs, An algorithm for fractional assignment problems, Unnamed Item, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, A new saling algorithm for the maximum mean cut problem, Approximate binary search algorithms for mean cuts and cycles, The maximum ratio clique problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- The auction algorithm for the transportation problem
- A strongly polynomial minimum cost circulation algorithm
- A linear time randomizing algorithm for searching ranked functions
- Dual coordinate step methods for linear network flow problems
- Parametric shortest path algorithms with an application to cyclic staffing
- A characterization of the minimum cycle mean in a digraph
- The auction algorithm: A distributed relaxation method for the assignment problem
- Network Flow and Testing Graph Connectivity
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
