Approximation algorithms

In a typical optimization problem in a network, the goal is to optimize an incurred cost, while meeting a structural requirement. For example, in steiner tree problem, the structural requirement is to connect all the terminals and the incurred cost is the sum of the cost of all …

Embedding between metric spaces is a very powerful algorithmic tool and has been used for finding good approximation algorithms for several problems. In particular, embedding to an l1 norm has been used as the key step in an approximation algorithm for the sparsest cut problem. …

In this thesis, we present some approximation algorithms for the following clustering problems: Minimum Sum of Radii (MSR), Minimum Sum of Diameters (MSD), and Unsplittable Capacitated Facility Location (UCFL). Given a metric (V,d) and an integer k, we consider the problem of pa…