A parallel approximation algorithm for positive linear programming

Keywords

Citation, Computer science, Linear programming, Algorithm, Approximation algorithm

References

• Probabilistic construction of deterministic algorithms: Approximating packing integer programsPrabhakar Raghavan — 1986
• A deterministic view of random sampling and its use in geometryBernard Chazelle, Joel Friedman — 1988
• On the hardness of approximating minimization problemsCarsten Lund, Mihalis Yannakakis — 1993
• On Parallel Prefix ComputationSanjeev Saxena, P.C.P. Bhatt, V.C. Prasad — 1994
• Approximate max flow on small depth networksEdith Cohen — 1992
• Fast approximation algorithms for fractional packing and covering problemsSerge Plotkin, David B. Shmoys, Éva Tardos — 1991
• Introduction to Parallel AlgorithmsJoseph F. JáJá — 1992
• Parallel merge sortRichard Cole — 1988
• Efficient NC algorithms for set cover with applications to learning and geometryBonnie Berger, John Rompel, Peter W. Shor — 1989

Cited by

• Work efficient parallel scheduling algorithmsHans Stadtherr — 1998
• Space-efficient Simulations of Quantum Interactive ProofsXiaodi Wu — 2013
• Combinatorial Problems of Packing and Covering and Related Problems of Integer Linear ProgrammingN. N. Kuzjurin — 2002
• A rank-predicted pseudo-greedy approach to efficient text selection from large-scale corpus for maximum coverage of target unitsWei Li, Qiang Huo — 2008
• A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex CoversSamir Khuller, Uzi Vishkin, Neal E. Young — 1994
• On the Complexity of Succinct Zero-Sum GamesLance Fortnow, Russell Impagliazzo, Valentine Kabanets — 2005
• Minimizing the total cost of network measurements in a distributed manner: a primal-dual approachBaruch Awerbuch, Rohit Khandekar — 2007
• Solving Packing Integer Programs via Randomized Rounding with AlterationsNikhil Bansal, Nitish Korula, Viswanath Nagarajan — 2012
• Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP SolverZeyuan Allen-Zhu, Yin Tat Lee, Lorenzo Orecchia — 2015
• Solving Linear Programs in MapReduceMahdi Ebrahimi, Gerhard Weikum, Rainer Gemulla — 2011
• Distributed combinatorial optimizationFabian Kühn, Roger Wattenhofer — 2005
• A Fast Distributed Algorithm for α-Fair Packing ProblemsJelena Marašević, Clifford Stein, Gil Zussman — 2015
• A Novel, Simple Interpretation of Nesterov's Accelerated Method as a Combination of Gradient and Mirror DescentZeyuan Allen Zhu, Lorenzo Orecchia — 2014
• A Distributed Approximation Algorithm for Mixed Packing-Covering Linear ProgramsFaraz Makari, Rainer Gemulla — 2013
• (De)randomized construction of small sample spaces in /spl Nscr//spl Cscr/David R. Karger, Daphne Koller — 1994
• Distributed storage allocations for neighborhood-based data accessDušan Jakovetić, Aleksandar Minja, Dragana Bajović — 2014
• Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and PracticeDaniel Bienstock — 2002
• Lagrangian relaxation based algorithms for convex programming problemsRohit Khandekar — 2004
• Approximating Scheduling Unrelated Parallel Machines in ParallelMarı́a Serna, Fatos Xhafa — 2002
• Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b-Matching Problems in Nonbipartite GraphsKook Jin Ahn, Sudipto Guha — 2013

Related papers

• Remarks on Algorithm 2, Algorithm 3, Algorithm 15, Algorithm 25 and Algorithm 26J. H. Wilkinson — 1961
• Remarks on Algorithm 332: Jacobi polynomials: Algorithm 344: student's t-distribution: Algorithm 351: modified Romberg quadrature: Algorithm 359: factoral analysis of varianceAhj Sale — 1970
• Citation Form in Transition: The ALWD Citation ManualVickie Rainwater — 2000
• A Research on Citation StandardLai Fang-zhon — 2013
• An improved filtering algorithm based on median filtering algorithm and medium filtering algorithmHeng Liu, Ningning Zhou — 2012
• The Evolution of Principia Mathematica; Bertrand Russell's Manuscripts and Notes for the Second EditionGregory Landini — 2013
• Remarks on algorithms 372 [A1]: An algorithm to produce complex primes, csieve and Algorithm 401 [A1]: an improved algorithm to produce complex primesPaul Bratley — 1970
• Citation ManagersBOB JOPSON — 1998
• A Non-Peshitta Jeremiah Citation by AphrahatJerome A. Lund — 2007