Positive linear programming, parallel approximation and PCP's

DOI10.1007/3-540-61680-2_47zbMATH Open1379.68357OpenAlexW1798514331MaRDI QIDQ4595478FDOQ4595478

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

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

Mathematics Subject Classification ID

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

Cited In (10)

• Approximate clustering of incomplete fingerprints
• Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
• Title not available (Why is that?)
• Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\)
• Linear-consistency testing.
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Parallel approximation of min-max problems
• Approximating linear programming is log-space complete for P
• On the parallel approximability of a subclass of quadratic programming.
• A note on approximate linear programming

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)