Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph (Q5002610): Difference between revisions

@@ label / en / label / en @@
+Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q4373665
@@ Property / cites work: Q4373665 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228453
@@ Property / cites work: Q4228453 / rank @@
+Normal rank
@@ Property / cites work @@
+Is constraint satisfaction over two variables always easy?
+Normal rank
@@ Property / cites work @@
+Oblivious algorithms for the maximum directed cut problem
+Normal rank
@@ Property / cites work @@
+Q3549651
@@ Property / cites work: Q3549651 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+Towards a Characterization of Approximation Resistance for Symmetric CSPs
+Normal rank
@@ Property / cites work @@
+Q2913811
@@ Property / cites work: Q2913811 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2768265
@@ Property / cites work: Q2768265 / rank @@
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Every 2-CSP allows nontrivial approximation
@@ Property / cites work: Every 2-CSP allows nontrivial approximation / rank @@
+Normal rank
@@ Property / cites work @@
+Stable distributions, pseudorandom generators, embeddings, and data stream computation
+Normal rank
@@ Property / cites work @@
+Streaming Lower Bounds for Approximating MAX-CUT
@@ Property / cites work: Streaming Lower Bounds for Approximating MAX-CUT / rank @@
+Normal rank
@@ Property / cites work @@
+(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space
+Normal rank
@@ Property / cites work @@
+Q5302080
@@ Property / cites work: Q5302080 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Finite-Valued CSPs
@@ Property / cites work: The Complexity of Finite-Valued CSPs / rank @@
+Normal rank
@@ Property / cites work @@
+Parallel approximation algorithms by positive linear programming
+Normal rank
@@ Property / cites work @@
+Q5365017
@@ Property / cites work: Q5365017 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://drops.dagstuhl.de/opus/volltexte/2017/7557/pdf/LIPIcs-APPROX-RANDOM-2017-8.pdf/
+Normal rank
@@ Property / OpenAlex ID @@
+W2747965299
@@ Property / OpenAlex ID: W2747965299 / rank @@
+Normal rank
@@ Property / title @@
+Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph (English)
+Normal rank