Incremental algorithms: solving problems in a changing world
Dexter C. Kozen, Alexa M. Sharp · 2007
A typical algorithm for a combinatorial optimization problem is given a static set of input, and finds a single solution. This kind of algorithm cannot be used, however, in situations where the input and solutions change over time due to evolving constraints. This dissertation explores incremental problems, one class of optimization problems that deals with this type of situation. An incremental algorithm is given a sequence of input, and finds a sequence of solutions that build incrementally while adapting to the changes in the input. Online algorithms also take in a sequence of input and produce incremental solutions; unlike their incremental counterparts, however, they do not know the input sequence in advance. We use our incremental results to better understand online algorithms and to indicate how their performance can be improved. Most combinatorial optimization problems can be extended to the incremental setting. We define general incremental formulations of covering and packing problems, and give incremental algorithms for such classes of problems. We study specific problems in detail, such as incremental bipartite matching, network flow, and edge cover, and find bounds on their complexity and competitiveness. Lastly, we explore different ways to define incremental problems, and discuss how to relax some of the constraints that limit the power of our incremental model.