A Lot-Sizing Problem on Trees, Related to Network Design
研究了通信网络设计中出现的树上容量扩展问题，涉及固定批量生产和多商品竞争容量资源，提出了精确和近似算法。
We describe a capacity expansion problem on trees, which arises in the design of certain communications networks, and is related to the knapsack and the economic lot-sizing problems. One of the main features is that production takes place in fixed (and possibly large) batch sizes. Another feature is that there may be various commodities competing for capacity resources. We present various exact and ε-approximate algorithms for this problem.