On the public citation graph

The (parallel) approximability of non-boolean satisfiability problems and restricted integer programming

0 signed · 48 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/inco.1994.1100openalex-snapshot
Logical Definability of NP Optimization Problems
inferredcites →https://doi.org/10.1006/jcss.1995.1031openalex-snapshot
Approximation Properties of NP Minimization Classes
inferredcites →https://doi.org/10.1006/jcss.1995.1087openalex-snapshot
A Dichotomy Theorem for Maximum Generalized Satisfiability Problems
inferredcites →https://doi.org/10.1006/jcss.1997.1532openalex-snapshot
(De)randomized Construction of Small Sample Spaces in NC
inferredcites →https://doi.org/10.1006/jcss.1998.1584openalex-snapshot
Integer Programming as a Framework for Optimization and Approximability
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-61680-2_47openalex-snapshot
Positive linear programming, parallel approximation and PCP's
inferredcites →https://doi.org/10.1007/bf01200757openalex-snapshot
The geometry of graphs and some of its algorithmic applications
inferredcites →https://doi.org/10.1007/bf02579324openalex-snapshot
Randomized rounding: A technique for provably good algorithms and algorithmic proofs
inferredcites →https://doi.org/10.1007/pl00009209openalex-snapshot
Parallel Approximation Algorithms by Positive Linear Programming
inferredcites →https://doi.org/10.1016/0022-0000(91)90023-xopenalex-snapshot
Optimization, approximation, and complexity classes
inferredcites →https://doi.org/10.1016/0304-3975(93)90259-vopenalex-snapshot
Quantifiers and approximation
inferredcites →https://doi.org/10.1017/cbo9780511666407openalex-snapshot
Paradigms for Fast Parallel Approximability
inferredcites →https://doi.org/10.1109/ccc.1996.507687openalex-snapshot
Integer programming as a framework for optimization and approximability
inferredcites →https://doi.org/10.1109/istcs.1993.253462openalex-snapshot
Interactive proofs and approximation: reductions from two provers in one round
inferredcites →https://doi.org/10.1109/sfcs.1994.365689openalex-snapshot
(De)randomized construction of small sample spaces in /spl Nscr//spl Cscr/
inferredcites →https://doi.org/10.1109/sfcs.1994.365712openalex-snapshot
On syntactic versus computational views of approximability
inferredcites →https://doi.org/10.1109/sfcs.1995.492463openalex-snapshot
Divide-and-conquer approximation algorithms via spreading metrics
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
inferredcites →https://doi.org/10.1137/s0097539795286612openalex-snapshot
On Syntactic versus Computational Views of Approximability
inferredcites →https://doi.org/10.1137/s0895480192243516openalex-snapshot
New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
inferredcites →https://doi.org/10.1145/167088.167174openalex-snapshot
Efficient probabilistically checkable proofs and applications to approximations
inferredcites →https://doi.org/10.1145/167088.167211openalex-snapshot
A parallel approximation algorithm for positive linear programming
inferredcites →https://doi.org/10.1145/225058.225181openalex-snapshot
A parallel repetition theorem
inferredcites →https://doi.org/10.1145/237814.237979openalex-snapshot
Towards a syntactic characterization of PTAS
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/258533.258538openalex-snapshot
A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction
inferredcites →https://doi.org/10.1145/258533.258641openalex-snapshot
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
inferredcites →https://doi.org/10.1145/258533.258642openalex-snapshot
Improved low-degree testing and its applications
inferredcites →https://doi.org/10.1145/261342.571216openalex-snapshot
Approximation Algorithms for NP-Hard Problems
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/net.20455openalex-snapshot
Generalized network design polyhedra
inferred← citeshttps://doi.org/10.1002/rsa.20050openalex-snapshot
Three‐query PCPs with perfect completeness over non‐Boolean domains
inferred← citeshttps://doi.org/10.1006/inco.2002.2903openalex-snapshot
Parallel Approximation Schemes for a Class of Planar and Near Planar Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1006/jcss.1998.1584openalex-snapshot
Integer Programming as a Framework for Optimization and Approximability
inferred← citeshttps://doi.org/10.1007/0-387-23830-1_3openalex-snapshot
Probabilistic Verification and Non-Approximability
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-662-47672-7_67openalex-snapshot
Approximating CSPs Using LP Relaxation
inferred← citeshttps://doi.org/10.1016/j.dam.2005.03.003openalex-snapshot
Supermodular functions and the complexity of MAX CSP
inferred← citeshttps://doi.org/10.1016/j.scico.2015.10.013openalex-snapshot
Using graph distances for named-entity linking
inferred← citeshttps://doi.org/10.1016/s0020-0190(02)00435-0openalex-snapshot
A combinatorial algorithm for max csp
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.1109/ccc.2003.1214428openalex-snapshot
Three-query PCPs with perfect completeness over non-Boolean domains
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743425openalex-snapshot
Probabilistically checkable proofs with low amortized query complexity
inferred← citeshttps://doi.org/10.1109/tkde.2004.75openalex-snapshot
Index selection for databases: a hardness study and a principled heuristic solution
inferred← citeshttps://doi.org/10.1137/s009753970444644xopenalex-snapshot
The Approximability of Three-valued MAX CSP
inferred← citeshttps://doi.org/10.1145/335305.335329openalex-snapshot
A PCP characterization of NP with optimal amortized query complexity
inferred← citeshttps://doi.org/10.5555/2884435.2884552openalex-snapshot
Approximation of non-boolean 2CSP
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.