Technical Report MSC-2008-07

Title: Correlation Clustering with Penalties and Approximating the Reordering Buffer Management Problem
Authors: Amjad Aboud
Supervisors: Yuval Rabani
Abstract: {\bf 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.\\

\noindent {\bf 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~\cite{EW05}. 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2008
To the main CS technical reports page

Computer science department, Technion