Parallel approximation algorithms by positive linear programming

DOI10.1007/PL00009209MaRDI QIDQ1386460zbMATH OpenOpenAlexFDO

Authors D. Massart, Luca Trevisan

Publication date 24 May 1998

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009209

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Linear programming (90C05)

Recommendations

• Positive linear programming, parallel approximation and PCP's
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• .878-approximation algorithms for MAX CUT and MAX 2SAT

Cited in

(31)

• Affine reductions for LPs and SDPs
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
• Approximation in (poly-) logarithmic space
• Oblivious algorithms for the maximum directed cut problem
• The complexity of linear programming in \((\gamma ,\kappa )\)-form
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and =(1/)-convergence
• Simultaneous approximation of constraint satisfaction problems
• Approximating CSPs using LP relaxation
• Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
• Parallel approximation of min-max problems
• Paradigms for Fast Parallel Approximability
• Positive linear programming, parallel approximation and PCP's
• scientific article; zbMATH DE number 2102778 (Why is no real title available?)
• scientific article; zbMATH DE number 871908 (Why is no real title available?)
• The quest for strong inapproximability results with perfect completeness
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• Approximation in (Poly-) Logarithmic Space
• scientific article; zbMATH DE number 7564377 (Why is no real title available?)
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• On the parallel approximability of a subclass of quadratic programming.
• Building a small and informative phylogenetic supertree
• On parallel versus sequential approximation
• Revisiting maximum satisfiability and related problems in data streams
• On maximizing sums of non-monotone submodular and linear functions
• Revisiting maximum satisfiability and related problems in data streams
• Improved parallel approximation of a class of integer programming problems
• From worst case to the average: structural guarantees in k-CSP approximation via orthogonal arrays
• Decremental (1+)-approximate maximum eigenvector: dynamic power method

This page was built for publication: Parallel approximation algorithms by positive linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386460)