Ph.D Student Ph.D Thesis Rawitz Dror Combinatorial and LP-Based Methods for Designing Approximation Algorithms Department of Computer Science PROFESSOR EMERITUS Reuven Bar-Yehuda

Abstract

This thesis focuses on two approximation paradigms: the local ratio technique and the primal-dual schema.  We present two relatively simple approximation frameworks for minimization problems, one for each approach, which extend known approximation frameworks for covering problems, and we show that the two frameworks are equivalent.  We also present two equivalent frameworks for maximization problems.  We demonstrate our generic algorithms on a variety of problems.

While all applications of the local ratio technique to date use non-negative weight functions, we present local ratio analyses to several known algorithms that use weight functions with some negative coefficients.  In order to present equivalent analyses that are based on the primal-dual schema we define new integer programming formulations with constraints that have negative coefficients.

We present two new combinatorial approximation frameworks that are not based on LP-duality, or even on linear programming.  Instead, they are based on weight manipulation in the spirit of the local ratio technique.  We show that the first framework is equivalent to the method of dual fitting.  We define a method called primal fitting, and show it is tantamount to our second framework.  We demonstrate both frameworks on a variety of problems including the metric uncapacitated facility location problem.

A k-partite graph is a graph G=(V1,…,Vk,E), where V1,…,Vk are k non-empty disjoint independent sets of vertices.  Such a graph is called complete k-partite if E contains all possible edges.  We discuss three variants of the following optimization problem: given a graph and a non-negative weight function on the vertices and edges, find a minimum weight set of vertices and incident edges whose removal from the graph leaves a complete k-partite graph.  We use the local-ratio technique to develop 2-approximation algorithms for the first two variants of the problem.  We use approximation preserving reductions in order to (4-4/k)-approximate the third variant.