Linear and combinatorial sharing problems (Q1081535)

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.