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.
