Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph

DOI10.4230/LIPICS.APPROX-RANDOM.2017.8MaRDI QIDQ5002610zbMATH OpenOpenAlexFDO

Authors Ameya Velingker, Santhoshini Velusamy, Venkatesan Guruswami

Publication date 28 July 2021

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7557/pdf/LIPIcs-APPROX-RANDOM-2017-8.pdf/

zbMATH Keywords

approximation algorithmsconstraint satisfaction problemshardness of approximationmaximum acyclic subgraphoptimization

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Streaming Lower Bounds for Approximating MAX-CUT
• (1 + (1))-approximation to MAX-CUT requires linear space
• An optimal space lower bound for approximating MAX-CUT
• Sketching cuts in graphs and hypergraphs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP

Cites work

• (1 + (1))-approximation to MAX-CUT requires linear space
• Combinatorial approximation algorithms for the maximum directed cut problem
• Every 2-CSP allows nontrivial approximation
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 1107717 (Why is no real title available?)
• scientific article; zbMATH DE number 5485569 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Is constraint satisfaction over two variables always easy?
• Oblivious algorithms for the maximum directed cut problem
• Parallel approximation algorithms by positive linear programming
• Some optimal inapproximability results
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Streaming Lower Bounds for Approximating MAX-CUT
• The streaming complexity of cycle counting, sorting by reversals, and other problems
• Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
• Towards a characterization of approximation resistance for symmetric CSPs

Cited in

(11)

• Fixed parameter tractability of graph deletion problems over data streams
• An optimal space lower bound for approximating MAX-CUT
• Streaming Lower Bounds for Approximating MAX-CUT
• scientific article; zbMATH DE number 7650072 (Why is no real title available?)
• Revisiting maximum satisfiability and related problems in data streams
• Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Streaming approximation resistance of every ordering CSP
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• Sketching approximability of all finite CSPs
• New algorithms and lower bounds for streaming tournaments

This page was built for publication: Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002610)