Topics in Approximation Algorithms

This thesis focuses on approximation and online algorithms for a few different problems.1) There have been continued improvements in the approximation algorithms for packing and covering problems. Some recent algorithms, including Fastpc, have provable good worst-case running times, but it is not known how they perform in practice compared to the simplex and interior-point algorithms that are widely used to solve these problems. We present an empirical comparison of these algorithms, using our own implementation of Fastpc and CPLEX implementations of simplex and interior-point methods. We use a variety of inputs for this experimental study. We find that Fastpc is slower for small problem instances, but its performance, relative to CPLEX algorithms, improves as the instances get bigger. Our experiments show that for reasonably large inputs Fastpc performs better than the CPLEX algorithms.2) We give deterministic algorithms for some variants of online file caching by reducing the problems to online covering. The variants considered in this study include one or both of the following features: (i) a rental cost for each slot occupied in the cache, and (ii) zapping a file by paying a cost so that the zapped file does not occupy any space in the cache and does not incur any retrieval cost. The rental cost is motivated by the idea of energy efficient caching where caching systems can save power by turning off slots not being used to store files. Our approach is based on the online covering algorithm by Koufogiannakis and Young. We give deterministic lower bounds for these variants, which are tight within con-stant factors of the upper bounds for most of the cases. We also give randomized algorithms and lower bounds for the variants with rental cost.3) We introduce online Huffman coding. In Huffman coding, the symbols are drawn from a probability distribution and revealed one by one, and the goal is to find a minimum cost prefix-code for the symbols. In the online version, the algorithm has to assign a codeword to a symbol when it is revealed for the first time. We propose an online greedy algorithm and show that it is constant-competitive for online Huffman coding. We also show a lower bound of 10/9 on the competitive ratio of any deterministic online algorithm