Simultaneous Approximation of Constraint Satisfaction Problems

DOI10.1007/978-3-662-47672-7_16zbMath1403.68341arXiv1407.7759OpenAlexW1887937548MaRDI QIDQ3448785

Amey Bhangale, Sushant Sachdeva, Swastik Kopparty

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.7759

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (6)

Simultaneous Approximation of Constraint Satisfaction Problems ⋮ Democratic fair allocation of indivisible goods ⋮ Sign rank vs discrepancy ⋮ Simultaneous max-cut is harder to approximate than max-cut ⋮ Socially fair network design via iterative rounding ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving MAX-\(r\)-SAT above a tight lower bound
• Parameterizing above or below guaranteed values
• Parallel approximation algorithms by positive linear programming
• Which problems have strongly exponential complexity?
• A survey and annotated bibliography of multiobjective combinatorial optimization
• The hardness of 3-uniform hypergraph coloring
• Approximation algorithms for the bi-criteria weighted MAX-CUT problem
• The Approximability of Constraint Satisfaction Problems
• Applications of Discrepancy Theory in Multiobjective Approximation
• Proof verification and the hardness of approximation problems
• Approximation Algorithm for Non-boolean MAX k-CSP
• Simultaneous Approximation of Constraint Satisfaction Problems
• Cutting two graphs simultaneously
• On the power of unique 2-prover 1-round games
• Probabilistic checking of proofs
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Judicious partitions of bounded‐degree graphs
• How to Round Any CSP
• Maximizing Several Cuts Simultaneously
• The complexity of satisfiability problems
• Some optimal inapproximability results
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Approximation resistance from pairwise independent subgroups
• On the complexity of \(k\)-SAT

This page was built for publication: Simultaneous Approximation of Constraint Satisfaction Problems