Complexity and algorithm for Reallocation Problem

Complexity and algorithm for Reallocation Problem

0.00 Avg rating0 Votes
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: ,
Keywords: graphs, optimization, allocation: resources
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.