Journal
DISCRETE APPLIED MATHEMATICS
Volume 159, Issue 12, Pages 1284-1289Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2011.04.007
Keywords
Transportation problem; Basic feasible solution; Computational complexity; Sum matrix
Categories
Funding
- 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)
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available