On Hochbaum's proximity-scaling algorithm for the general resource allocation problem

On Hochbaum's proximity-scaling algorithm for the general resource allocation problem

0.00 Avg rating0 Votes
Article ID: iaor20071538
Country: United States
Volume: 29
Issue: 2
Start Page Number: 394
End Page Number: 397
Publication Date: May 2004
Journal: Mathematics of Operations Research
Authors: ,
Keywords: combinatorial optimization, programming: integer
Abstract:

It is pointed out that the polynomial-time scaling algorithm by Hochbaum does not work correctly for the general resource allocation problem. Hochbaum's algorithm increases a variable by one unit if the variable cannot feasibly be increased by the scaling unit. We modify the algorithm to increase such a variable by the largest possible amount and show that with this modification the algorithm works correctly. The effect is to modify the factor F in the running time of Hochbaum's algorithm for finding whether a certain solution is feasible by the factor &Fmacr; of finding the maximum feasible increment (also called the saturation capacity). Therefore, the corrected algorithm runs in O(n(log n + F) log(B/n)) time.

Reviews

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