Fully dynamic approximation algorithms
Zoran Ivković · 1996
In this dissertation, we study fully dynamic approximation algorithms. In general, fully dynamic algorithms model situations where the problem instance changes (slowly) over time. In this context, we study fully dynamic algorithms that incorporate Insert and Delete operations, and certain (problem dependent) queries. We consider a fully dynamic algorithm efficient if its running time, either uniform or amortized over a sequence of operations or queries, is asymptotically faster than a repeated execution of the best (known) off-line algorithm after every change. Fully dynamic approximation algorithms maintain approximate solutions within a constant multiplicative factor, called the competitive ratio, from an optimal solution under a sequence of Insert and Delete operations and queries. The running times of interest must be faster than mere recomputation of the entire solution after each operation or query via the best off-line algorithms. Competitive ratios of fully dynamic approximation algorithms should be (nearly) as good as those of the best off-line algorithms. We first study fully dynamic approximation algorithms for vertex cover, a classic NP-complete minimization problem on graphs. We present $A\sb1$, a fully dynamic approximation algorithm for vertex cover. We further provide for a generalization of this algorithm and present a family of algorithms $A\sb{k}, k\geq1$. Algorithms $A\sb{k}$ support Insert and Deletes of edges. Each $A\sb k$ requires ${\cal O}((v+e){1+\sqrt{1+4(k+1)(2k+3)}\over2(2k+3)})$ amortized running time per Insert/Delete operation. It follows that this amortized running time may be made arbitrarily close to ${\cal O}((v+e){\sqrt{2}\over2})$. Each of the algorithms $A\sb{k}$ is 2-competitive, thereby matching the competitive ratio of the best existing off-line approximation algorithms for vertex cover. The algorithms $A\sb{k}$ are the first known fully dynamic approximation algorithms for vertex cover. We then study fully dynamic approximation algorithms for bin packing, another classic NP-complete minimization problem. Our main result is a fully dynamic approximation algorithm for bin packing MMP that is ${5\over4}$-competitive and requires $\Theta(\log n)$ time per an Insert or a Delete of an item. This competitive ratio of ${5\over4}$ is nearly as good as that of the best practical off-line algorithms. Further, in the case where there are no Deletes of items, we provide an approximation scheme such that for any competitive ratio exceeding 1, there is an algorithm having that competitive ratio, and an amortized running time of $\Theta(\log n)$ per Insert operation. Again, MMP is the first known fully dynamic approximation algorithm for bin packing. Some of the techniques developed in the course of designing the fully dynamic algorithms for bin packing lead to the development of LINBP, a practical ${4\over3}$-competitive off-line algorithm for linear time bin packing. This algorithm significantly decreases the gap between the best practical linear time bin packing approximation algorithms and the existing linear time polynomial time approximation schemes. For a bounded bin packing problem, where the item sizes are from $({1\over3},1\rbrack$, we present a family of linear time approximation algorithms $A\sb\epsilon$ with a competitive ratio of ${5+\epsilon\over4}$ for arbitrarily small $\epsilon>0$. Finally, we note that there is a simple parallel version of LINBP that is optimal and requires ${\cal O}(\log n\log\sp* n)$ time and n processors on the EREW PRAM.