The approximability of non-Boolean satisfiability problems and restricted integer programming
type: Item
instance of: scholarly article
title: The approximability of non-Boolean satisfiability problems and restricted integer programming
zbMATH Open document ID: 1070.68156
author: Luca Trevisan
author: Fatos Xhafa
author: Maria Serna
published in: Theoretical Computer Science
publication date: 2005-04-06T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 90C09
zbMATH DE Number: 2153182
zbMATH Keywords: Parallel approximation algorithms
zbMATH Keywords: Non-approximability
zbMATH Keywords: Positive linear programming
zbMATH Keywords: Randomized rounding
zbMATH Keywords: Non-Boolean constraint satisfaction
zbMATH Keywords: Maximum capacity representatives
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.10.014
OpenAlex ID: W2026391598
Wikidata QID: Q61736686
cites work: Q4527016
cites work: Integer programming as a framework for optimization and approximability
cites work: Efficient probabilistically checkable proofs and applications to approximations
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: Q4293543
cites work: A dichotomy theorem for maximum generalized satisfiability problems.
cites work: Paradigms for Fast Parallel Approximability
cites work: Q4231911
cites work: New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
cites work: Q3002852
cites work: Some optimal inapproximability results
cites work: Q4228486
cites work: The approximability of constraint satisfaction problems
cites work: Logical definability of NP optimization problems
cites work: Approximation properties of NP minimization classes
cites work: Q3129925
cites work: The geometry of graphs and some of its algorithmic applications
cites work: A parallel approximation algorithm for positive linear programming
cites work: Quantifiers and approximation
cites work: Optimization, approximation, and complexity classes
cites work: Randomized rounding: A technique for provably good algorithms and algorithmic proofs
cites work: A Parallel Repetition Theorem
cites work: Q4527015
cites work: Parallel approximation algorithms by positive linear programming
DOI: 10.1016/J.TCS.2004.10.014
DBLP publication ID: journals/tcs/SernaTX05
description: scientific article; zbMATH DE number 2153182