Article ID: | iaor19962191 |
Country: | Japan |
Volume: | E79-A |
Issue: | 4 |
Start Page Number: | 461 |
End Page Number: | 468 |
Publication Date: | Apr 1996 |
Journal: | Transactions on Fundamentals of Electronics, Communications and Computer Sciences |
Authors: | Ito Hiro, Miwa Hiroyoshi |
Keywords: | graphs, optimization, allocation: resources |
The authors define the Reallocation Problem to determine whether we can move products from their current storehouses to target storehouses in a number of moves which is less than or equal to a given number. This problem is defined simply and can be applied to many practical problems. The authors give necessary and sufficient conditions for feasibility for Reallocation Problems under various conditions, and propose linear-time algorithms, when the volume of the products is restricted to 1. Moreover, they show that the Reallocation Problem is NP-complete in the strong sense, when the volume of the products is not restricted.