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

optimizationapproximation algorithmsconstraint satisfaction problemshardness of approximationmaximum acyclic subgraph

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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
• (1 + (1))-approximation to MAX-CUT requires linear space

Cited in

(11)

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

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)