An algebraic approach to assignment problems |
| |
Authors: | Rainer E Burkard Willi Hahn Uwe Zimmermann |
| |
Institution: | (1) University of Cologne, Cologne, Germany;(2) Fachhochschule des Landes Rheinland Pfalz, Bingen, Germany |
| |
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. |
| |
Keywords: | Combinatorial Optimization Assignment Problem Ordered Semigroups Bottleneck Objective Lexicographical Objective Labeling Method Admissible Transformation |
本文献已被 SpringerLink 等数据库收录! |