Online Algorithms to Minimize Resource Reallocations and Network Communication
In this paper, the authors consider two new online optimization problems (Each with several variants), present similar online algorithms for both, and show that one reduces to the other. Both problems involve a control trying to minimize the number of changes that need to be made in maintaining a state that satisfies each of many users' requirements. The algorithms have the property that the control only needs to be informed of a change in users needs when the current state no longer satisfies the user. This is particularly important when the application is one of trying to minimize communication between the users and the control. The Resource Allocation Problem (RAP) is an abstraction of scheduling malleable and evolving jobs on multiprocessor machines.