Incremental Approximations

虽然近似算法和在线算法都得到了相当广泛的研究，但很少有人同时研究近似算法和在线算法。也就是说，设计以迭代方式工作的近似算法。设计这样的算法的双重目标是使算法运行得更快，并产生良好的近似值。增量近似的研究旨在研究增量近似所涉及的权衡和问题，并针对寄存器分配、分组无线网络调度和装箱中的具体问题开发增量近似方法。

Although approximation algorithms and on-line algorithms have each been studied rather extensively, there has been very little work that examines the approximation and on-line aspects in tandem. That is, the design of approximation algorithms that work in an iterative fashion. The dual goals in designing such algorithms are to make the algorithm run fast, and to produce a good approximation. This research on incremental approximations is aimed at examining the tradeoffs and issues involved, as well as to develop incremental approximation methods for specific problems in register allocation, scheduling for packet radio networks, and bin-packing.