Linear and combinatorial sharing problems

DOI10.1016/0166-218X(86)90022-3zbMath0601.90120OpenAlexW2057624035MaRDI QIDQ1081535

Uwe T. Zimmermann

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90022-3

zbMATH Keywords

polynomial complexityknapsack sharinggroup-valued submodular flow sharingperfect b-matching sharingsharing problemthreshold techniques

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items

Sharing problems, Minimum dispersion problems, Reshipments and overshipments in transportation problems with minimax objective, Duality for balanced submodular flows

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear and combinatorial optimization in ordered algebraic structures
• On the solution of discrete bottleneck problems
• Minimization on submodular flows
• Reductions to 1–matching polyhedra
• Structures of polyhedra determined by submodular functions on crossing families
• Combinatorial Optimization with Rational Objective Functions
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• FINDING THE WEIGHTED MINIMAX FLOW IN A POLYNOMIAL TIME
• WEIGHTED MINIMAX REAL-VALUED FLOWS
• Linear max-min programming
• Optimal sharing
• Algebraic Linear Programming
• Optimal flows in networks with multiple sources and sinks
• A good algorithm for lexicographically optimal flows in multi-terminal networks
• The Sharing Problem
• The Knapsack Sharing Problem
• New Finite Pivoting Rules for the Simplex Method
• An Algorithm for Submodular Functions on Graphs
• The flow circulation sharing problem
• Application of Programs with Maximin Objective Functions to Problems of Optimal Resource Allocation
• Bottleneck extrema