On the public citation graph
Parallel Approximation Algorithms by Positive Linear Programming
0 signed · 89 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/jagm.1994.1045openalex-snapshot
On the Approximation of Maximum Satisfiability
inferredcites →https://doi.org/10.1007/3-540-60313-1_159openalex-snapshot
On parallel versus sequential approximation
inferredcites →https://doi.org/10.1007/3-540-61422-2_122openalex-snapshot
Randomized approximation of the constraint satisfaction problem
inferredcites →https://doi.org/10.1007/3-540-61422-2_124openalex-snapshot
Approximation algorithms for the maximum satisfiability problem
inferredcites →https://doi.org/10.1007/bf02579150openalex-snapshot
A new polynomial-time algorithm for linear programming
inferredcites →https://doi.org/10.1007/bf02579324openalex-snapshot
Randomized rounding: A technique for provably good algorithms and algorithmic proofs
inferredcites →https://doi.org/10.1016/0020-0190(91)90194-mopenalex-snapshot
Approximating linear programming is log-space complete for P
inferredcites →https://doi.org/10.1016/0020-0190(92)90132-fopenalex-snapshot
A note on approximate linear programming
inferredcites →https://doi.org/10.1016/0022-0000(88)90003-7openalex-snapshot
Probabilistic construction of deterministic algorithms: Approximating packing integer programs
inferredcites →https://doi.org/10.1016/0022-0000(91)90023-xopenalex-snapshot
Optimization, approximation, and complexity classes
inferredcites →https://doi.org/10.1017/cbo9780511666407openalex-snapshot
Paradigms for Fast Parallel Approximability
inferredcites →https://doi.org/10.1090/dimacs/020/07openalex-snapshot
Computing near-optimal solutions to combinatorial optimization problems
inferredcites →https://doi.org/10.1109/istcs.1995.377033openalex-snapshot
Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT
inferredcites →https://doi.org/10.1109/sfcs.1994.365710openalex-snapshot
Approximate graph coloring by semidefinite programming
inferredcites →https://doi.org/10.1109/sfcs.1994.365712openalex-snapshot
On syntactic versus computational views of approximability
inferredcites →https://doi.org/10.1109/sfcs.1996.548521openalex-snapshot
Gadgets, approximation, and linear programming
inferredcites →https://doi.org/10.1137/0211045openalex-snapshot
Approximation Algorithms for the Set Covering and Vertex Cover Problems
inferredcites →https://doi.org/10.1137/0215074openalex-snapshot
A Simple Parallel Algorithm for the Maximal Independent Set Problem
inferredcites →https://doi.org/10.1137/s0895480192243516openalex-snapshot
New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
inferredcites →https://doi.org/10.1137/s0895480195296221openalex-snapshot
A Geometric Approach to Betweenness
inferredcites →https://doi.org/10.1142/s0129626492000301openalex-snapshot
APPROXIMATING MAXIMUM 2-CNF SATISFIABILITY
inferredcites →https://doi.org/10.1145/167088.167211openalex-snapshot
A parallel approximation algorithm for positive linear programming
inferredcites →https://doi.org/10.1145/227683.227684openalex-snapshot
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
inferredcites →https://doi.org/10.1561/0400000009openalex-snapshot
Pairwise Independence and Derandomization
inferredcites →https://doi.org/10.2307/2584070openalex-snapshot
Introduction to the Theory of Complexity.
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/rsa.20050openalex-snapshot
Three‐query PCPs with perfect completeness over non‐Boolean domains
inferred← citeshttps://doi.org/10.1007/11523468_77openalex-snapshot
Approximating Max kCSP – Outperforming a Random Assignment with Almost a Linear Factor
inferred← citeshttps://doi.org/10.1007/3-540-44666-4_27openalex-snapshot
The Non-approximability of Non-Boolean Predicates
inferred← citeshttps://doi.org/10.1007/978-3-031-22105-7_17openalex-snapshot
Revisiting Maximum Satisfiability and Related Problems in Data Streams
inferred← citeshttps://doi.org/10.1007/978-3-319-13075-0_42openalex-snapshot
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization
inferred← citeshttps://doi.org/10.1007/978-3-540-27821-4_14openalex-snapshot
Approximating Max k CSP Using Random Restrictions
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_7openalex-snapshot
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_22openalex-snapshot
Approximation Algorithm for Non-boolean MAX k-CSP
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_16openalex-snapshot
Simultaneous Approximation of Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_67openalex-snapshot
Approximating CSPs Using LP Relaxation
inferred← citeshttps://doi.org/10.1007/978-3-662-48350-3_66openalex-snapshot
On the Approximability of Digraph Ordering
inferred← citeshttps://doi.org/10.1007/bfb0028584openalex-snapshot
The (parallel) approximability of non-boolean satisfiability problems and restricted integer programming
inferred← citeshttps://doi.org/10.1007/s00453-013-9806-zopenalex-snapshot
Oblivious Algorithms for the Maximum Directed Cut Problem
inferred← citeshttps://doi.org/10.1007/s00453-016-0227-7openalex-snapshot
On the Approximability of Digraph Ordering
inferred← citeshttps://doi.org/10.1007/s00453-021-00826-7openalex-snapshot
Approximation in (Poly-) Logarithmic Space
inferred← citeshttps://doi.org/10.1007/s00453-023-01183-3openalex-snapshot
On Maximizing Sums of Non-monotone Submodular and Linear Functions
inferred← citeshttps://doi.org/10.1007/s004530010007openalex-snapshot
Erratum: A Correction to ``Parallel Approximation Algorithms by Positive Linear Programming''
inferred← citeshttps://doi.org/10.1007/s10107-017-1221-9openalex-snapshot
Affine reductions for LPs and SDPs
inferred← citeshttps://doi.org/10.1007/s10107-018-1244-xopenalex-snapshot
Nearly linear-time packing and covering LP solvers
inferred← citeshttps://doi.org/10.1016/j.ic.2023.105082openalex-snapshot
Building a small and informative phylogenetic supertree
inferred← citeshttps://doi.org/10.1016/j.ipl.2007.08.025openalex-snapshot
The complexity of linear programming in -form
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.10.014openalex-snapshot
The approximability of non-Boolean satisfiability problems and restricted integer programming
inferred← citeshttps://doi.org/10.1016/j.tcs.2023.114271openalex-snapshot
Revisiting maximum satisfiability and related problems in data streams
inferred← citeshttps://doi.org/10.1016/j.tcs.2026.115896openalex-snapshot
From worst case to the average: Structural guarantees in k-CSP approximation via orthogonal arrays
inferred← citeshttps://doi.org/10.1016/s0129-6264(02)00087-2openalex-snapshot
THE PARALLEL APPROXIMABILITY OF THE FALSE AND TRUE GATES PROBLEMS FOR NOR-CIRCUITS
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00337-0openalex-snapshot
On the parallel approximability of a subclass of quadratic programming
inferred← citeshttps://doi.org/10.1017/cbo9780511921735openalex-snapshot
The Design of Approximation Algorithms
inferred← citeshttps://doi.org/10.1023/a:1013781304506openalex-snapshot
Approximating Scheduling Unrelated Parallel Machines in Parallel
inferred← citeshttps://doi.org/10.1051/ita:2007032openalex-snapshot
Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
inferred← citeshttps://doi.org/10.1093/nar/gkq1207openalex-snapshot
Discovering pathways by orienting edges in protein interaction networks
inferred← citeshttps://doi.org/10.1109/ccc.2000.856745openalex-snapshot
A survey of optimal PCP characterizations of NP
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214428openalex-snapshot
Three-query PCPs with perfect completeness over non-Boolean domains
inferred← citeshttps://doi.org/10.1109/ccc.2008.20openalex-snapshot
Approximation Resistant Predicates from Pairwise Independence
inferred← citeshttps://doi.org/10.1109/ccc.2011.10openalex-snapshot
Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs
inferred← citeshttps://doi.org/10.1109/ccc.2011.15openalex-snapshot
Approximation Algorithms for QMA-Complete Problems
inferred← citeshttps://doi.org/10.1109/focs.2007.41openalex-snapshot
Towards Sharp Inapproximability For Any 2-CSP
inferred← citeshttps://doi.org/10.1109/focs.2007.73openalex-snapshot
Towards Sharp Inapproximability For Any 2-CSP
inferred← citeshttps://doi.org/10.1109/ita.2018.8503261openalex-snapshot
A Parallelizable Acceleration Framework for Packing Linear Programs
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743425openalex-snapshot
Probabilistically checkable proofs with low amortized query complexity
inferred← citeshttps://doi.org/10.1137/070681612openalex-snapshot
Gowers Uniformity, Influence of Variables, and PCPs
inferred← citeshttps://doi.org/10.1137/070711670openalex-snapshot
Towards Sharp Inapproximability for Any 2-CSP
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch127openalex-snapshot
Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
inferred← citeshttps://doi.org/10.1137/110842272openalex-snapshot
Approximation Algorithms for QMA-Complete Problems
inferred← citeshttps://doi.org/10.1137/17m1142922openalex-snapshot
Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program
inferred← citeshttps://doi.org/10.1137/s0895480100380458openalex-snapshot
The Nonapproximability of Non-Boolean Predicates
inferred← citeshttps://doi.org/10.1145/1132516.1132519openalex-snapshot
Gowers uniformity, influence of variables, and PCPs
inferred← citeshttps://doi.org/10.1145/1250790.1250864openalex-snapshot
Low-degree tests at large distances
inferred← citeshttps://doi.org/10.1145/1541885.1541893openalex-snapshot
Near-optimal algorithms for maximum constraint satisfaction problems
inferred← citeshttps://doi.org/10.1145/2746539.2746573openalex-snapshot
Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
inferred← citeshttps://doi.org/10.1145/3459668openalex-snapshot
The Quest for Strong Inapproximability Results with Perfect Completeness
inferred← citeshttps://doi.org/10.1287/opre.2022.2352openalex-snapshot
Black-Box Acceleration of Monotone Convex Program Solvers
inferred← citeshttps://doi.org/10.1609/aaai.v32i1.11778openalex-snapshot
A Parallelizable Acceleration Framework for Packing Linear Programs
inferred← citeshttps://doi.org/10.48550/arxiv.1010.0406openalex-snapshot
Oblivious Algorithms for the Maximum Directed Cut Problem
inferred← citeshttps://doi.org/10.48550/arxiv.1301.2632openalex-snapshot
Approximation, Proof Systems, and Correlations in a Quantum World
inferred← citeshttps://doi.org/10.48550/arxiv.1407.1925openalex-snapshot
Using Optimization to Solve Positive LPs Faster in Parallel
inferred← citeshttps://doi.org/10.48550/arxiv.1511.06558openalex-snapshot
Near-Optimal UGC-hardness of Approximating Max k-CSP_R
inferred← citeshttps://doi.org/10.48550/arxiv.1711.06656openalex-snapshot
A Parallelizable Acceleration Framework for Packing Linear Programs
inferred← citeshttps://doi.org/10.5555/1283383.1283391openalex-snapshot
Near-optimal algorithms for maximum constraint satisfaction problems
inferred← citeshttps://doi.org/10.5555/3039686.3039775openalex-snapshot
LP relaxations of some NP-hard problems are as hard as any LP
inferred← citeshttps://doi.org/10.5555/365411.365412openalex-snapshot
Combinatorial approximation algorithms for the maximum directed cut problem
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.