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: | Shioura Akiyoshi, Moriguchi Satoko |
Keywords: | combinatorial optimization, programming: integer |
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