On the public citation graph

Structure in Approximation Classes

https://doi.org/10.1007/bfb0030875
0 signed · 65 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/jagm.1994.1045openalex-snapshot
On the Approximation of Maximum Satisfiability
inferredcites →https://doi.org/10.1007/3-540-56939-1_60openalex-snapshot
The approximation of maximum subgraph problems
inferredcites →https://doi.org/10.1007/3-540-56939-1_61openalex-snapshot
Polynomially bounded minimization problems which are hard to approximate
inferredcites →https://doi.org/10.1007/3-540-58715-2_135openalex-snapshot
On approximation scheme preserving reductibility and its applications
inferredcites →https://doi.org/10.1007/3-540-60246-1_129openalex-snapshot
Strong lower bounds on the approximability of some NPO PB-complete maximization problems
inferredcites →https://doi.org/10.1007/3-540-63248-4_10openalex-snapshot
Approximation on the web: A compendium of NP optimization problems
inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot
Structural Complexity I
inferredcites →https://doi.org/10.1007/bf00289161openalex-snapshot
Continuous reductions among combinatorial optimization problems
inferredcites →https://doi.org/10.1007/bfb0039599openalex-snapshot
Graph isomorphism is in the low hierarchy
inferredcites →https://doi.org/10.1016/0020-0190(90)90188-4openalex-snapshot
Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems
inferredcites →https://doi.org/10.1016/0022-0000(88)90010-4openalex-snapshot
Graph isomorphism is in the low hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(88)90039-6openalex-snapshot
The complexity of optimization problems
inferredcites →https://doi.org/10.1016/0022-0000(91)90023-xopenalex-snapshot
Optimization, approximation, and complexity classes
inferredcites →https://doi.org/10.1016/0167-6377(82)90046-3openalex-snapshot
Assembly line balancing as generalized bin packing
inferredcites →https://doi.org/10.1016/0304-3975(81)90007-4openalex-snapshot
On γ-reducibility versus polynomial time many-one reducibility
inferredcites →https://doi.org/10.1016/0304-3975(91)90160-4openalex-snapshot
Bounded queries to SAT and the Boolean hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(93)90259-vopenalex-snapshot
Quantifiers and approximation
inferredcites →https://doi.org/10.1016/0890-5401(91)90025-wopenalex-snapshot
Completeness in approximation classes
inferredcites →https://doi.org/10.1016/0890-5401(92)90056-lopenalex-snapshot
On the complexity of approximating the independent set problem
inferredcites →https://doi.org/10.1016/s0022-0000(74)80044-9openalex-snapshot
Approximation algorithms for combinatorial problems
inferredcites →https://doi.org/10.1109/ccc.1997.612321openalex-snapshot
A short guide to approximation preserving reductions
inferredcites →https://doi.org/10.1109/sct.1988.5260openalex-snapshot
Decision trees and downward closures
inferredcites →https://doi.org/10.1109/sct.1988.5286openalex-snapshot
Bounded query computations
inferredcites →https://doi.org/10.1109/sct.1991.160280openalex-snapshot
Approximation properties of NP minimization classes
inferredcites →https://doi.org/10.1109/sct.1994.315820openalex-snapshot
On the query complexity of clique size and maximum satisfiability
inferredcites →https://doi.org/10.1109/sfcs.1982.61openalex-snapshot
An efficient approximation scheme for the one-dimensional bin-packing problem
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.1109/sfcs.1994.365712openalex-snapshot
On syntactic versus computational views of approximability
inferredcites →https://doi.org/10.1137/0210055openalex-snapshot
The NP-Completeness of Edge-Coloring
inferredcites →https://doi.org/10.1137/0217080openalex-snapshot
The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
inferredcites →https://doi.org/10.1137/0220025openalex-snapshot
Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
inferredcites →https://doi.org/10.1137/s0097539794266481openalex-snapshot
On Bounded Queries and Approximation
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/185675.306789openalex-snapshot
On the hardness of approximating minimization problems
inferredcites →https://doi.org/10.1145/321864.321877openalex-snapshot
On the Structure of Polynomial Time Reducibility
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
inferredcites →https://doi.org/10.1287/opre.33.6.1353openalex-snapshot
Bounds for Assembly Line Balancing Heuristics
inferredcites →https://doi.org/10.1542/peds.98.5.931openalex-snapshot
Outcomes of Extremely Low Birth Weight Infants
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/9781118595091.refsopenalex-snapshot
References
inferred← citeshttps://doi.org/10.1006/inco.2000.3011openalex-snapshot
On Weighted vs Unweighted Versions of Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1006/jcss.1996.0070openalex-snapshot
On the Query Complexity of Clique Size and Maximum Satisfiability
inferred← citeshttps://doi.org/10.1007/3-540-44450-5_9openalex-snapshot
On Approximability of the Independent/Connected Edge Dominating Set Problems
inferred← citeshttps://doi.org/10.1007/3-540-44929-9_15openalex-snapshot
On the Hardness of Approximating Some NP-Optimization Problems Related to Minimum Linear Ordering Problem
inferred← citeshttps://doi.org/10.1007/3-540-46784-x_7openalex-snapshot
Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2
inferred← citeshttps://doi.org/10.1007/3-540-60246-1_129openalex-snapshot
Strong lower bounds on the approximability of some NPO PB-complete maximization problems
inferred← citeshttps://doi.org/10.1007/3-540-62592-5_80openalex-snapshot
Hardness of approximating problems on cubic graphs
inferred← citeshttps://doi.org/10.1007/3-540-63248-4_10openalex-snapshot
Approximation on the web: A compendium of NP optimization problems
inferred← citeshttps://doi.org/10.1007/bfb0027116openalex-snapshot
Parallel approximation of optimization problems
inferred← citeshttps://doi.org/10.1016/0020-0190(96)00046-4openalex-snapshot
Approximability of maximum splitting of k-sets and some other Apx-complete problems
inferred← citeshttps://doi.org/10.1016/s0020-0190(01)00138-7openalex-snapshot
On approximability of the independent/connected edge dominating set problems
inferred← citeshttps://doi.org/10.1016/s0166-218x(03)00444-xopenalex-snapshot
On approximability of linear ordering and related NP-optimization problems on graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(98)00069-9openalex-snapshot
On the approximability of the Steiner tree problem in phylogeny
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00115-1openalex-snapshot
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00158-3openalex-snapshot
Some APX-completeness results for cubic graphs
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00121-8openalex-snapshot
Structural properties of bounded relations with an application to NP optimization problems
inferred← citeshttps://doi.org/10.1016/s0893-6080(96)00065-2openalex-snapshot
A Neural Algorithm for MAX-2SAT: Performance Analysis and Circuit Implementation
inferred← citeshttps://doi.org/10.1051/ita:2001121openalex-snapshot
On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
inferred← citeshttps://doi.org/10.1051/ro:2003009openalex-snapshot
Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
inferred← citeshttps://doi.org/10.1109/ccc.1997.612321openalex-snapshot
A short guide to approximation preserving reductions
inferred← citeshttps://doi.org/10.1109/ccc.1997.612323openalex-snapshot
Constraint satisfaction: the approximability of minimization problems
inferred← citeshttps://doi.org/10.1145/258533.258541openalex-snapshot
When Hamming meets Euclid
inferred← citeshttps://doi.org/10.1145/276698.276784openalex-snapshot
The approximability of NP-hard problems
inferred← citeshttps://doi.org/10.1145/306198.306210openalex-snapshot
How to find the best approximation results
inferred← citeshttps://doi.org/10.4086/cjtcs.1997.002openalex-snapshot
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.