On the public citation graph

Approximation Properties of NP Minimization Classes

0 signed · 64 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.1007/3-540-51859-2_17openalex-snapshot
A structural overview of NP optimization problems
inferredcites →https://doi.org/10.1007/3-540-56992-8_19openalex-snapshot
Logical definability of NP-optimisation problems with monadic auxiliary predicates
inferredcites →https://doi.org/10.1016/0020-0190(91)90188-nopenalex-snapshot
On approximating the minimum independent dominating set
inferredcites →https://doi.org/10.1016/0022-0000(82)90012-5openalex-snapshot
Structure and complexity of relational queries
inferredcites →https://doi.org/10.1016/0304-3975(81)90082-7openalex-snapshot
Optimization problems and the polynomial hierarchy
inferredcites →https://doi.org/10.1016/c2009-0-22107-6openalex-snapshot
A Mathematical Introduction to Logic
inferredcites →https://doi.org/10.1016/s0019-9958(86)80029-8openalex-snapshot
Relational queries computable in polynomial time
inferredcites →https://doi.org/10.1016/s0022-0000(74)80044-9openalex-snapshot
Approximation algorithms for combinatorial problems
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.1137/0210021openalex-snapshot
Edge-Deletion Problems
inferredcites →https://doi.org/10.1137/0210022openalex-snapshot
Node-Deletion Problems on Bipartite Graphs
inferredcites →https://doi.org/10.1145/100216.100275openalex-snapshot
Quantifiers and approximation
inferredcites →https://doi.org/10.1145/31846.31852openalex-snapshot
Monotone versus positive
inferredcites →https://doi.org/10.1145/62212.62233openalex-snapshot
Optimization, approximation, and complexity classes

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/9781118600207.ch13openalex-snapshot
Inapproximability of Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1002/9781119005353.biblioopenalex-snapshot
General Bibliography
inferred← citeshttps://doi.org/10.1002/9781119005353.ch13openalex-snapshot
Inapproximability of Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1006/jcss.1997.1490openalex-snapshot
On Fixed-Parameter Tractability and Approximability of NP 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/3-540-28788-4_12openalex-snapshot
Quantifiers and Logical Reductions
inferred← citeshttps://doi.org/10.1007/3-540-45632-5_3openalex-snapshot
Search and Optimization Problems in Datalog
inferred← citeshttps://doi.org/10.1007/3-540-49477-4_12openalex-snapshot
Some Prospects forEfficient Fixed Parameter Algorithms
inferred← citeshttps://doi.org/10.1007/3-540-63172-0_47openalex-snapshot
Optimization problems with approximation schemes
inferred← citeshttps://doi.org/10.1007/978-3-540-79723-4_3openalex-snapshot
Algorithmic Meta-theorems
inferred← citeshttps://doi.org/10.1007/978-3-642-13182-0_12openalex-snapshot
Frameworks for Logically Classifying Polynomial-Time Optimisation Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-28050-4_14openalex-snapshot
Safe Approximation and Its Relation to Kernelization
inferred← citeshttps://doi.org/10.1007/978-3-662-03182-7_11openalex-snapshot
Quantifiers and Logical Reductions
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/s00224-011-9366-zopenalex-snapshot
Structure of Polynomial-Time Approximation
inferred← citeshttps://doi.org/10.1007/s00453-011-9559-5openalex-snapshot
Polynomial Kernelizations for MIN F+Π1 and MAX NP
inferred← citeshttps://doi.org/10.1007/s11390-005-0003-7openalex-snapshot
Parameterized Computation and Complexity: A New Approach Dealing with NP-Hardness
inferred← citeshttps://doi.org/10.1016/j.cosrev.2009.11.001openalex-snapshot
A survey on the structure of approximation classes
inferred← citeshttps://doi.org/10.1016/j.orl.2003.08.004openalex-snapshot
Local approximations for maximum partial subgraph problem
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/s0304-0208(04)80009-4openalex-snapshot
Bibliography
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00200-xopenalex-snapshot
Max NP-completeness made easy
inferred← citeshttps://doi.org/10.1017/s1471068409990251openalex-snapshot
atalog: A logic language for expressing search and optimization problems
inferred← citeshttps://doi.org/10.1080/02331934.2011.625027openalex-snapshot
Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
inferred← citeshttps://doi.org/10.1093/comjnl/bxm036openalex-snapshot
On Parameterized Intractability: Hardness and Completeness
inferred← citeshttps://doi.org/10.1093/ietfec/e89-a.5.1425openalex-snapshot
Inapproximability of the Edge-Contraction Problem
inferred← citeshttps://doi.org/10.1109/ccc.1996.507687openalex-snapshot
Integer programming as a framework for optimization and approximability
inferred← citeshttps://doi.org/10.1109/ccc.1997.612323openalex-snapshot
Constraint satisfaction: the approximability of minimization problems
inferred← citeshttps://doi.org/10.1109/lics.1996.561298openalex-snapshot
A generalization of Fagin's theorem
inferred← citeshttps://doi.org/10.1109/lics.1998.705640openalex-snapshot
Existential second-order logic over strings
inferred← citeshttps://doi.org/10.1109/lics.2006.13openalex-snapshot
Approximation Schemes for First-Order Definable Optimisation Problems
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365712openalex-snapshot
On syntactic versus computational views of approximability
inferred← citeshttps://doi.org/10.1109/sfcs.2002.1181978openalex-snapshot
The parameterized complexity of counting problems
inferred← citeshttps://doi.org/10.1109/sofa.2010.5565610openalex-snapshot
Graph based detection of optic disc and fovea in retinal images
inferred← citeshttps://doi.org/10.1137/140997889openalex-snapshot
Hitting Forbidden Minors: Approximation and Kernelization
inferred← citeshttps://doi.org/10.1137/s0097539703427203openalex-snapshot
The Parameterized Complexity of Counting Problems
inferred← citeshttps://doi.org/10.1137/s0097539795285102openalex-snapshot
Weighted NP Optimization Problems: Logical Definability and Approximation Properties
inferred← citeshttps://doi.org/10.1137/s0097539795286612openalex-snapshot
On Syntactic versus Computational Views of Approximability
inferred← citeshttps://doi.org/10.1137/s0097539799349948openalex-snapshot
The Approximability of Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1137/s0097539799360768openalex-snapshot
Fixed-Parameter Tractability, Definability, and Model-Checking
inferred← citeshttps://doi.org/10.1145/130385.130389openalex-snapshot
Learning hierarchical rule sets
inferred← citeshttps://doi.org/10.1145/185675.306789openalex-snapshot
On the hardness of approximating minimization problems
inferred← citeshttps://doi.org/10.1145/331605.331609openalex-snapshot
Existential second-order logic over strings
inferred← citeshttps://doi.org/10.1145/967900.968045openalex-snapshot
On the semantics and expressive power of Datalog-like languages for NP search and optimization problems
inferred← citeshttps://doi.org/10.11606/t.45.2004.tde-20210729-135334openalex-snapshot
Algoritmos de aproximação para partições conexas em grafos
inferred← citeshttps://doi.org/10.22028/d291-26018openalex-snapshot
Kernelization of generic problems : upper and lower bounds
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2009.1851openalex-snapshot
Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP
inferred← citeshttps://doi.org/10.48550/arxiv.0911.2785openalex-snapshot
NP Datalog: a Logic Language for Expressing NP Search and Optimization Problems
inferred← citeshttps://doi.org/10.48550/arxiv.1711.02889openalex-snapshot
FO and MSO approach to Some Graph Problems: Approximation and Poly time Results
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0106049openalex-snapshot
Recursively Undecidable Properties of NP
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.