Complexity and Algorithm for Reallocation Problem

Hiroyoshi MIWA  Hiro ITO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.4   pp.461-468
Publication Date: 1996/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
reallocation,  graph,  linear time,  NP-complete,  

Full Text: PDF(724.1KB)>>
Buy this Article



Summary: 
We define the Reallocation Problem to determine whether we can move products from their current store-houses 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. We give necessary and sufficient conditions for feasibility for Reallocation Problems under various conditions, and propose liner time algorithms, when the volume of the products is restricted to 1. Moreover, we show that the Reallocation Problem is NP-complete in the strong sense, when the volume of the products is not restricted.