Linear and combinatorial sharing problems
type: Item
instance of: scholarly article
title: Linear and combinatorial sharing problems
zbMATH Open document ID: 0601.90120
DOI: 10.1016/0166-218X(86)90022-3
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: The sharing problem of the following form: min\(\{\) f(x)\(|\) \(x\in P\}\), where \(f(x)=\max_{j}f_ j(x_ j)\) and P denotes the set of feasible solutions, is investigated. A rather general class of share functions - residuated functions defined on totally ordered sets - is considered. The general concept developed by the author enables to construct threshold techniques for different share functions (linear, bottleneck) and different variables (real, rational or integer): (1) an algorithm for a knapsack sharing problem \(P=\{x| b\leq \sum^{n}_{j=1}x_ j\), \(x_ j\in M_ j\), \(j=1,...,n\}\); (2) a dual method for sharing on polyhedra \(P=\{x\in R^ n| Ax\geq b\), \(0\leq x\leq u\}\), so-called linear programming sharing problems; (3) finite dual methods for group-valued submodular flow sharing problems and for perfect b-matching sharing problems. The last-mentioned methods have polynomial complexity for bottleneck and some linear share functions.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3970537
zbMATH Keywords: sharing problem
zbMATH Keywords: threshold techniques
zbMATH Keywords: knapsack sharing
zbMATH Keywords: group-valued submodular flow sharing
zbMATH Keywords: perfect b-matching sharing
zbMATH Keywords: polynomial complexity
author: Uwe T. Zimmermann
reviewed by: Oleg A. Shcherbina
MaRDI profile type: Publication
cites work: Reductions to 1–matching polyhedra
cites work: New Finite Pivoting Rules for the Simplex Method
cites work: Q4056047
cites work: The Knapsack Sharing Problem
cites work: The Sharing Problem
cites work: The flow circulation sharing problem
cites work: Bottleneck extrema
cites work: Q4149476
cites work: Q5675543
cites work: Q3929415
cites work: An Algorithm for Submodular Functions on Graphs
cites work: Algebraic Linear Programming
cites work: Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
cites work: Structures of polyhedra determined by submodular functions on crossing families
cites work: Q4194764
cites work: FINDING THE WEIGHTED MINIMAX FLOW IN A POLYNOMIAL TIME
cites work: WEIGHTED MINIMAX REAL-VALUED FLOWS
cites work: Optimal sharing
cites work: Application of Programs with Maximin Objective Functions to Problems of Optimal Resource Allocation
cites work: Q4133994
cites work: Optimal flows in networks with multiple sources and sinks
cites work: A good algorithm for lexicographically optimal flows in multi-terminal networks
cites work: Combinatorial Optimization with Rational Objective Functions
cites work: Linear max-min programming
cites work: On the solution of discrete bottleneck problems
cites work: Linear and combinatorial optimization in ordered algebraic structures
cites work: Minimization on submodular flows
cites work: Q3725833
full work available at URL: 0166-218x(86)90022-3
OpenAlex ID: W2057624035
description: scientific article; zbMATH DE number 3970537