2026-07-22T19:10:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7557 2024-03-06T10:40:36Z ddc:004 open_access

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph Guruswami, Venkatesan Velingker, Ameya Velusamy, Santhoshini approximation algorithms constraint satisfaction problems optimization hardness of approximation maximum acyclic subgraph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Venkatesan Guruswami and Ameya Velingker and Santhoshini Velusamy 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.8 urn:nbn:de:0030-drops-75570 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode