TR#: | MSC-2008-07 |

Class: | MSC |

Title: | Correlation Clustering with Penalties and Approximating the Reordering Buffer Management Problem |

Authors: | Amjad Aboud |

Supervisors: | Yuval Rabani |

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.

To the list of the MSC technical reports of 2008

To the main CS technical reports page