ISSN:
1436-4646
Schlagwort(e):
Combinatorial Optimization
;
Assignment Problem
;
Ordered Semigroups
;
Bottleneck Objective
;
Lexicographical Objective
;
Labeling Method
;
Admissible Transformation
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract For assignment problems a class of objective functions is studied by algebraic methods and characterized in terms of an axiomatic system. It says essentially that the coefficients of the objective function can be chosen from a totally ordered commutative semigroup, which obeys a divisibility axiom. Special cases of the general model are the linear assignment problem, the linear bottleneck problem, lexicographic multicriteria problems,p-norm assignment problems and others. Further a polynomial bounded algorithm for solving this generalized assignment problem is stated. The algebraic approach can be extended to a broader class of combinatorial optimization problems.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01593800
Permalink
