期刊
DISCRETE APPLIED MATHEMATICS
卷 159, 期 12, 页码 1284-1289出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2011.04.007
关键词
Transportation problem; Basic feasible solution; Computational complexity; Sum matrix
资金
- Austrian Science Fund (FWF) [P18918-N18]
- Netherlands Organisation for Scientific Research [639.033.403]
- DIAMANT (an NWO mathematics cluster)
- BSIK [03018]
- Austrian Science Fund (FWF) [P18918] Funding Source: Austrian Science Fund (FWF)
Under which conditions can one permute the rows and columns in an instance of the transportation problem, such that the Northwest corner rule solves the resulting permuted instance to optimality? And under which conditions will the Northwest corner rule find the optimal solution for every possible permutation of the instance? We show that the first question touches the area of NP-completeness, and we answer the second question by a simple characterization of such instances. (C) 2011 Published by Elsevier B.V.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据