ISSN:
1436-4646
Keywords:
Combinatorial Optimization
;
Assignment Problem
;
Ordered Semigroups
;
Bottleneck Objective
;
Lexicographical Objective
;
Labeling Method
;
Admissible Transformation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01593800
Permalink
