A Monge property for the d-dimensional transportation problem

详细信息    查看全文

• 作者：Bein ; Wolfgang W. ; Brucker ; Peter ; Park ; James K. ; Pathak ; Pramod K.
• 刊名：Discrete Applied Mathematics
• 出版年：1995
• 出版时间：March 24, 1995
• 年：1995
• 卷：58
• 期：2
• 页码：97-109
• 全文大小：691 K

文摘

In 1963, Hoffman gave necessary and sufficient conditions under which a family of O(mn)-time greedy algorithms solves the classical two-dimensional transportation problem withm sources and n sinks. One member of this family, an algorithm based on the “northwest corner rule”, is of particular interest, as its running time is easily reduced to O(m + n). When restricted to this algorithm, Hoffman's result can be expressed as follows: the northwest-corner-rule greedy algorithm solves the two-dimensional transportation problem for all source and supply vectors if and only if the problem's cost array C = {c[i,j]} possesses what is known as the (two-dimensional) Monge property, which requires c[i₁, j₁] +c [i₂, j₂] ≤ c[i₁, j₂] +c [i₂, j₁] fori₁ < i₂ and j₁ < j₂. This paper generalizes this last result to a higher dimensional variant of the transportation problem. We show that the natural extension of the northwest-corner-rule greedy algorithm solves an instance of the d-dimensional transportation problem if and only if the problem's cost array possesses a d-dimensional Monge property recently proposed by Aggarwal and Park in the context of their study of monotone arrays. We also give several new examples of cost arrays with this d-dimensional Monge property.