Technical Report MSC-2008-07

 TR#: MSC-2008-07 Class: MSC Title: Correlation Clustering with Penalties and Approximating the Reordering Buffer Management Problem Authors: Amjad Aboud Supervisors: Yuval Rabani PDF MSC-2008-07.pdf 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. Copyright The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2008/MSC/MSC-2008-07), rather than to the URL of the PDF files directly. The latter URLs may change without notice.