Positive linear programming, parallel approximation and PCP's

DOI10.1007/3-540-61680-2_47MaRDI QIDQ4595478zbMATH OpenOpenAlexFDO

Authors Luca Trevisan

Publication date 5 December 2017

Published in Algorithms — ESA '96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61680-2_47

Mathematics Subject Classification ID

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

Recommendations

• Parallel approximation algorithms by positive linear programming
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Gadgets, Approximation, and Linear Programming

Cited in

(11)

• A note on approximate linear programming
• Parallel approximation algorithms by positive linear programming
• 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.
• Reactive local search techniques for the maximum k-conjunctive constraint satisfaction problem (MAX-k-CCSP)
• Parallel approximation of min-max problems
• scientific article; zbMATH DE number 871908 (Why is no real title available?)
• On the parallel approximability of a subclass of quadratic programming.
• Linear-consistency testing.
• Approximating linear programming is log-space complete for P
• Approximate clustering of incomplete fingerprints

This page was built for publication: Positive linear programming, parallel approximation and PCP's

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