Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.8zbMath1467.68064OpenAlexW2747965299MaRDI QIDQ5002610

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

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

Related Items (4)

Revisiting maximum satisfiability and related problems in data streams ⋮ Unnamed Item ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Fixed parameter tractability of graph deletion problems over data streams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel approximation algorithms by positive linear programming
• Oblivious algorithms for the maximum directed cut problem
• Is constraint satisfaction over two variables always easy?
• The Complexity of Finite-Valued CSPs
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space
• Towards a Characterization of Approximation Resistance for Symmetric CSPs
• Streaming Lower Bounds for Approximating MAX-CUT
• Some optimal inapproximability results
• Every 2-CSP allows nontrivial approximation

This page was built for publication: Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph