License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.127
URN: urn:nbn:de:0030-drops-39282
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3928/
Go to the corresponding LIPIcs Volume Portal

Iwata, Yoichi ; Yoshida, Yuichi

Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra

pdf-format:
16.pdf (0.6 MB)

Abstract

We study the constraint satisfaction problem over the point algebra.
In this problem, an instance consists of a set of variables and a set of binary constraints of forms (x < y), (x <= y), (x \neq y) or (x = y). Then, the objective is to assign integers to variables so as to satisfy as many constraints as possible.This problem contains many important problems such as Correlation Clustering, Maximum Acyclic Subgraph, and Feedback Arc Set.

We first give an exact algorithm that runs in O^*(3^{\frac{log 5}{log 6}n}) time, which improves the previous best O^*(3^n) obtained by a standard dynamic programming.
Our algorithm combines the dynamic programming with the split-and-list technique. The split-and-list technique involves matrix products and we make use of sparsity of matrices to speed up the computation.

As for approximation, we give a 0.4586-approximation algorithm when the objective is maximizing the number of satisfied constraints, and give an O(log n log log n)-approximation algorithm when the objective is minimizing the number of unsatisfied constraints.

BibTeX - Entry

@InProceedings{iwata_et_al:LIPIcs:2013:3928,
  author =	{Yoichi Iwata and Yuichi Yoshida},
  title =	{{Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{127--138},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3928},
  URN =		{urn:nbn:de:0030-drops-39282},
  doi =		{10.4230/LIPIcs.STACS.2013.127},
  annote =	{Keywords: Constraint Satisfaction Problems, Point Algebra, Exact Algorithms, Approximation Algorithms}
}

Keywords: Constraint Satisfaction Problems, Point Algebra, Exact Algorithms, Approximation Algorithms
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI