License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.8
URN: urn:nbn:de:0030-drops-75570
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7557/
Go to the corresponding LIPIcs Volume Portal

Guruswami, Venkatesan ; Velingker, Ameya ; Velusamy, Santhoshini

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

pdf-format:
LIPIcs-APPROX-RANDOM-2017-8.pdf (0.5 MB)

Abstract

We study the complexity of estimating the optimum value of a Boolean 2CSP (arity two constraint satisfaction problem) in the single-pass streaming setting, where the algorithm is presented the constraints in an arbitrary order. We give a streaming algorithm to estimate the optimum within a factor approaching 2/5 using logarithmic space, with high probability. This beats the trivial factor 1/4 estimate obtained by simply outputting 1/4-th of the total number of constraints.

The inspiration for our work is a lower bound of Kapralov, Khanna, and Sudan (SODA'15) who showed that a similar trivial estimate (of factor 1/2) is the best one can do for Max CUT. This lower bound implies that beating a factor 1/2 for Max DICUT (a special case of Max 2CSP), in particular, to distinguish between the case when the optimum is m/2 versus when it is at most (1/4+eps)m, where m is the total number of edges, requires polynomial space. We complement this hardness result by showing that for DICUT, one can distinguish between the case in which the optimum exceeds (1/2+eps)m and the case in which it is close to m/4.

We also prove that estimating the size of the maximum acyclic subgraph of a directed graph, when its edges are presented in a single-pass stream, within a factor better than 7/8 requires polynomial space.

BibTeX - Entry

@InProceedings{guruswami_et_al:LIPIcs:2017:7557,
  author =	{Venkatesan Guruswami and Ameya Velingker and Santhoshini Velusamy},
  title =	{{Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7557},
  URN =		{urn:nbn:de:0030-drops-75570},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.8},
  annote =	{Keywords: approximation algorithms, constraint satisfaction problems, optimization, hardness of approximation, maximum acyclic subgraph}
}

Keywords: approximation algorithms, constraint satisfaction problems, optimization, hardness of approximation, maximum acyclic subgraph
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

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