The approximability of non-Boolean satisfiability problems and restricted integer programming

DOI10.1016/j.tcs.2004.10.014zbMath1070.68156OpenAlexW2026391598WikidataQ61736686 ScholiaQ61736686MaRDI QIDQ1770383

Luca Trevisan, Fatos Xhafa, Maria J. Serna

Publication date: 6 April 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.014

zbMATH Keywords

Randomized roundingNon-approximabilityMaximum capacity representativesNon-Boolean constraint satisfactionParallel approximation algorithmsPositive linear programming

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Boolean programming (90C09) Approximation algorithms (68W25)

Related Items (4)

Supermodular functions and the complexity of MAX CSP ⋮ Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming ⋮ Integer programming as a framework for optimization and approximability ⋮ Generalized network design polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy theorem for maximum generalized satisfiability problems.
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Optimization, approximation, and complexity classes
• Quantifiers and approximation
• Integer programming as a framework for optimization and approximability
• Logical definability of NP optimization problems
• Parallel approximation algorithms by positive linear programming
• Approximation properties of NP minimization classes
• The geometry of graphs and some of its algorithmic applications
• The Approximability of Constraint Satisfaction Problems
• Paradigms for Fast Parallel Approximability
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• A Parallel Repetition Theorem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Efficient probabilistically checkable proofs and applications to approximations
• A parallel approximation algorithm for positive linear programming
• Some optimal inapproximability results

This page was built for publication: The approximability of non-Boolean satisfiability problems and restricted integer programming