Linear and Combinatorial Sharing Problems
Zimmermann, Uwe
(1986)
Linear and Combinatorial Sharing Problems.
Published in:
Discrete applied mathematics Vol. 15 (1).
pp. 85104.
Abstract
Sharing problems are minimax problems with separable objective, i.e. min {F(x)  x in P} where F(x) := max {fi(xi)  j=1,...,n}. For quasiconvex and lower semicontinuous functions fi on arbitrary totally ordered sets, we derive a duality theory. In particular, a general dual method is shown to apply to linear, combinatorial and convex sharing problems. For linear and bottleneck share functions fi the method is polynomially bounded in many applications.
Actions:
Content information:
Item Type:  Article 

Citations:  6 (Google Scholar)  5 (Web of Science) 
Uncontrolled Keywords:  groupvalued submodular flow sharing knapsack sharing perfect bmatching sharing polynomial complexity sharing problem threshold techniques 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
Deposit Information:
ZAIK Number:  zpr84003 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  25 Oct 2011 12:53 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/3 