M.Sc Thesis | |

M.Sc Student | Aboud Amjad |
---|---|

Subject | Correlation Clustering with Penalties and Approximating the Recordering Buffer Management Problem |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Yuval Rabani |

Full Thesis text |

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.