Approximation Algorithms For Some Combinatorial Problems Of Network Design

We consider the single source rent-or-buy problem with submodular penal-ties.The single source rent-or-buy problem can be considered as a special case of the connected facility location problem.Here the opening costs are 0 and facilities may be opened anywhere in network.By exploring the properties of the submodular function,we give a 5-approximation algorithm for this problem.We also analyze the local search heuristic for the cache placement prob-lem.We analyze the locality gap of a local search procedure for a minimization problem which is the maximum ratio of a locally optimum solution to the glob-al optimum.For cache placement problem,we consider the case of using local search operation to open one or more copies of a cache and drop zero or more caches.We prove that this local search algorithm has a locality gap of at most 5 when each page is cached exactly once which improves the previous result of 8.