Article ID: | iaor200971527 |
Country: | Germany |
Volume: | 3 |
Issue: | 4 |
Start Page Number: | 491 |
End Page Number: | 497 |
Publication Date: | Sep 2009 |
Journal: | Optimization Letters |
Authors: | Zheng Yujun, Xu Chuanqing, Xue Jinyun |
Keywords: | combinatorial optimization |
Greedy algorithms for combinatorial optimization problems are typically direct and efficient, but hard to prove optimality. The paper presents a special class of transportation problems where a supplier sends goods to a set of customers, returning to the source after each delivery. We show that these problems with different objective functions share a common structural property, and therefore a simple but powerful generic greedy algorithm yields optimal solutions for all of them.