Parallel approximation algorithms by positive linear programming
From MaRDI portal
Publication:1386460
DOI10.1007/PL00009209zbMath0896.68072OpenAlexW1992866589MaRDI QIDQ1386460
Publication date: 24 May 1998
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00009209
Linear programming (90C05) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)
Related Items (22)
Simultaneous Approximation of Constraint Satisfaction Problems ⋮ Approximating CSPs Using LP Relaxation ⋮ The complexity of linear programming in \((\gamma ,\kappa )\)-form ⋮ On the approximability of digraph ordering ⋮ Unnamed Item ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Building a small and informative phylogenetic supertree ⋮ 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 ⋮ Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming ⋮ Affine reductions for LPs and SDPs ⋮ Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph ⋮ Unnamed Item ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ On the parallel approximability of a subclass of quadratic programming. ⋮ Unnamed Item ⋮ Approximation in (Poly-) logarithmic space ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Oblivious algorithms for the maximum directed cut problem
This page was built for publication: Parallel approximation algorithms by positive linear programming
