On the parallel approximability of a subclass of quadratic programming.

DOI10.1016/S0304-3975(99)00337-0zbMath1142.90452OpenAlexW2001671553WikidataQ61736688 ScholiaQ61736688MaRDI QIDQ5941277

Maria J. Serna, Fatos Xhafa

Publication date: 20 August 2001

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00337-0

zbMATH Keywords

Quadratic programmingDense instancesPacking / covering linear programsParallel approximationsRandomized rounding

Mathematics Subject Classification ID

Quadratic programming (90C20) Parallel algorithms in computer science (68W10) Boolean programming (90C09) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved parallel approximation of a class of integer programming problems
• Approximating linear programming is log-space complete for P
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• The ellipsoid method and its consequences in combinatorial optimization
• Linear programming is log-space hard for P
• The probabilistic method yields deterministic parallel algorithms
• Parallel approximation algorithms by positive linear programming
• Randomness is linear in space
• Quadratic programming is in NP
• Paradigms for Fast Parallel Approximability
• Computationally Related Problems
• A parallel approximation algorithm for positive linear programming

This page was built for publication: On the parallel approximability of a subclass of quadratic programming.