Complexity of approximating CSP with balance/hard constraints
type: Item
instance of: scholarly article
title: Complexity of approximating CSP with balance/hard constraints
zbMATH Open document ID: 1350.68142
author: Venkatesan Guruswami
author: Euiwoong Lee
published in: Theory of Computing Systems
publication date: 2016-09-21T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6628965
zbMATH Keywords: constraint satisfaction problems
zbMATH Keywords: complexity dichotomy
zbMATH Keywords: approximation algorithms
zbMATH Keywords: hardness of approximation
zbMATH Keywords: unique games hardness
MaRDI profile type: Publication
full work available at URL: s00224-015-9638-0
OpenAlex ID: W791130099
cites work: O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
cites work: Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
cites work: Q3002828
cites work: Approximation and Online Algorithms
cites work: Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
cites work: Q2934583
cites work: Nonuniform Boolean constraint satisfaction problems with cardinality constraint
cites work: Robust Satisfiability for CSPs
cites work: On the hardness of approximating minimum vertex cover
cites work: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
cites work: Approximating minimum feedback sets and multicuts in directed graphs
cites work: Q4535020
cites work: Q3499508
cites work: New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Complexity of approximating CSP with balance / hard constraints
cites work: Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
cites work: Q4537699
cites work: Some optimal inapproximability results
cites work: A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
cites work: The approximability of constraint satisfaction problems
cites work: On the power of unique 2-prover 1-round games
cites work: Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Q4737518
cites work: Noise stability of functions with low influences: invariance and optimality
cites work: Optimization, approximation, and complexity classes
cites work: Q5743406
cites work: The complexity of satisfiability problems
cites work: Hardness of Vertex Deletion and Project Scheduling
cites work: A .699-approximation algorithm for Max-Bisection.
cites work: Q4542575
DOI: 10.1007/S00224-015-9638-0
description: scientific article; zbMATH DE number 6628965