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.