M.Sc Thesis

M.Sc StudentAboud Amjad
SubjectCorrelation Clustering with Penalties and Approximating the
Recordering Buffer Management Problem
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Yuval Rabani
Full Thesis textFull thesis text - English Version


Correlation Clustering with Penalties: We study a graph-theoretic clustering criterion that allows for the presence of outliers. More specifically, we consider the correlation clustering problem where, in addition to the input complete graph with edges marked “+” or “-”, there is a penalty function on the nodes, and nodes can be discarded from the clustering at the cost of their assigned penalty. We give a simple 9-approximation algorithm for this problem. Our algorithm is based on the primal-dual schema. We use the primal-dual schema to compute a potentially infeasible solution whose purpose is to indicate an approximately best set of nodes to be discarded from the clustering. In addition, we consider a general version of the previous problem, where instead of marking edges with “+” or “-”, we have two weight functions on the edges. A “+” function (“-” function) that indicates the desire of each edge to be marked “+” (“-”).

We present the modification to the algorithm to solve the general version under specific probability that achieves 17-approximation.

Reordering Buffer Management Problem: A sequence of objects which are characterized by their color has to be processed and their processing order influences how efficiently they can be processed. A color change between two successive objects produces non-uniform cost; this is the non-uniform case of the problem. A reordering buffer which is a random access buffer with storage capacity of k objects can be used to rearrange this sequence in such a way that the total cost is minimized. The strategy with the best known competitive ratio is MAP. An upper bound of O(log k) on the competitive ratio of MAP is known and a non-constant lower bound on the competitive ratio is not known.

Based on a specific sequence input, we proof that the previously used proof techniques are not suitable to show an o(log k) upper bound on the competitive ratio of MAP.