Abstract
Weakly admissible transformations are introduced for solving algebraic assignment and transportation problems, which cover so important classes as problems with sum objectives, bottleneck objectives, lexicographical objectives and others. A transformation of the cost matrix is called weakly admissible, if there are two constants α and β in the underlying semigroup that for all feasible solutions the composition of α and the objective value with respect to the original cost coefficients is equal to the composition of β and the objective value with respect to the transformed cost coefficients. The elements α and β can be determined by shortest path algorithms. An optimal solution for the algebraic assignment problem can be found after at most n weakly admissible transformations, therefore the proposed method yields an O(n 3) algorithm for algebraic assignment problems.
Preview
Unable to display preview. Download preview PDF.
References
R.E. Burkard, “A general Hungarian method for the algebraic transportation problem”, Discrete Mathematics 22 (1978) 219–232.
R.E. Burkard, W. Hahn and U. Zimmermann, “An algebraic approach to assignment problems”, Mathematical Programming 12 (1977) 318–327.
R.E. Burkard, H. Hamacher and U. Zimmermann, “The algebraic network flow problem”, Report 1976-7, Mathematisches Institut der Universität zu Köln (Köln, 1976).
U. Derigs and U. Zimmermann, “An augmenting path method for solving linear bottleneck assignment problems”, Computing 19 (1978) 285–295.
U. Derigs and U. Zimmermann, “An augmenting path method for solving linear bottleneck transportation problems”, Computing 22 (1978) 1–15.
E.W. Dijkstra, “A note on two problems in connection with graphs”, Numerische Mathematik 1 (1959) 269–271.
B. Dorhout, “Het lineaire toewijzingsprobleem, Vergelijken van algoritment”, Report BN 21/73, Stichting Mathematisch Centrum (Amsterdam, 1973).
L. Fuchs, Partially ordered algebraic systems. (Addison-Wesley, Reading, MA, 1963).
J. Ponstein, “On the maximal flow problem with real arc capacities”, Mathematical Programming 3 (1972) 254–256.
N. Tomizawa, “On some techniques useful for solution of transportation network problems”, Networks 1 (1972) 179–194.
U. Zimmermann, “Boole'sche Optimierungsprobleme mit separabler Zielfunktion und matroidalen Restriktionen”, Thesis, Universität zu Köln (Köln 1976).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1980 The Mathematical Programming Society
About this chapter
Cite this chapter
Burkard, R.E., Zimmermann, U. (1980). Weakly admissible transformations for solving algebraic assignment and transportation problems. In: Padberg, M.W. (eds) Combinatorial Optimization. Mathematical Programming Studies, vol 12. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0120884
Download citation
DOI: https://doi.org/10.1007/BFb0120884
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00801-6
Online ISBN: 978-3-642-00802-3
eBook Packages: Springer Book Archive