Approximation algorithms for combinatorial problems

1974/12/01 by David S. Johnson · 2,232 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Bounded function #Clique #Clique problem #Combinatorial optimization #Combinatorics #Computer science #Constant (computer programming) #Constraint Satisfaction and Optimization #Data Management and Algorithms #Graph #Heuristic #Independent set #Line graph #Mathematical optimization #Mathematics #Pathwidth #Polynomial-time approximation scheme #SIMPLE algorithm #Satisfiability #Simple (philosophy) #Time complexity

paper · pdf · doi:10.1016/s0022-0000(74)80044-9

published in Journal of Computer and System Sciences 9(3), 256-278 (Elsevier BV)

openalex publication_date 1974/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Cited by

• A Branch-and-Cut Algorithm for the Dial-a-Ride Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation Algorithms for Several Graph Augmentation Problems
• Sparse Approximate Solutions to Linear Systems
• Greedy bi-criteria approximations for k-medians and k-means
• Adaptive Greedy Algorithms for Stochastic Set Cover Problems
• Graph2Seq: Scalable Learning Dynamics for Graphs
• Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-dimension
• Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach
• Lower and upper bounds for the Bin Packing Problem with Fragile Objects
• Geometry based heuristics for unit disk graphs
• Design of Dynamic Algorithms via Primal-Dual Method
• Upper and Lower Bounds on Approximating Weighted Mixed Domination
• Constructive Relationships Between Algebraic Thickness and Normality
• Near-Linear Query Complexity for Graph Inference
• Differentially Private Combinatorial Optimization
• An O(log n)-approximation for the Set Cover Problem with Set Ownership
• Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem
• Capacitated Dominating Set on Planar Graphs
• A new proof of the Larman–Rogers upper bound for the chromatic number of the Euclidean space
• Hitting Sets Online and Unique-Max Coloring
• Domination in graphs with bounded propagation: algorithms, formulations and hardness results
• On the Computational Complexities of Three Privacy Measures for Large Networks Under Active Attack
• CNF Encodings of Cardinality Constraints Based on Comparator Networks
• Leveraging Side Observations in Stochastic Bandits
• Improved Approximation Algorithms for Geometric Set Cover
• Online Multi-Facility Location
• A-priori Upper Bounds for the Set Covering Problem
• Approximate Computation for Big Data Analytics
• On the hardness of approximating minimization problems
• Algorithms for Constructing Overlay Networks For Live Streaming
• Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods
• (1, k)-Swap Local Search for Maximum Clique Problem
• Active Screening for Recurrent Diseases: A Reinforcement Learning Approach
• Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover
• A Survey on The Expressive Power of Graph Neural Networks
• A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
• Uniform unweighted set cover: The power of non-oblivious local search
• Applications of Discrepancy Theory in Multiobjective Approximation
• New Greedy Heuristics For Set Cover and Set Packing
• Approximation algorithms and hardness for domination with propagation
• borealis - A generalized global update algorithm for Boolean optimization problems
• On the robust hardness of Gröbner basis computation
• Proof verification and hardness of approximation problems
• Polynomial Time Data Reduction for Dominating Set
• The Constant Inapproximability of the Parameterized Dominating Set Problem
• A tight analysis of the greedy algorithm for set cover
• Hotspot-aware DSA Grouping and Mask Assignment
• Balanced Combinations of Solutions in Multi-Objective Optimization
• Approximation Algorithms for Some Routing Problems
• On the Parameterized Complexity of Approximating Dominating Set
• Algorithms for Scheduling Independent Tasks
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• Load adjustment in adaptive real-time systems
• Node-and edge-deletion NP-complete problems
• On the independent set problem in random graphs
• Some simplified NP-complete graph problems
• Heuristics for Maximum Clique and Independent Set
• Clique is hard to approximate within n1−ε
• Proof verification and the hardness of approximation problems
• Learnability and the Vapnik-Chervonenkis dimension
• How to find the best approximation results
• Some simplified NP-complete problems
• Approximating minimum cocolorings
• Solving Hard Computational Problems Efficiently: Asymptotic Parametric Complexity 3-Coloring Algorithm
• A General Approximation Technique for Constrained Forest Problems
• Almost optimal set covers in finite VC-dimension
• Inapproximability Results for Guarding Polygons and Terrains
• Landmarks in graphs
• Polynomial-time data reduction for dominating set
• Analysis of a greedy heuristic for finding small dominating sets in graphs
• Structure preserving reductions among convex optimization problems
• Optimization, approximation, and complexity classes
• FPT Algorithms for Domination in Biclique-Free Graphs
• Sparsification and subexponential approximation
• On the complexity of approximating the independent set problem
• Clique is hard to approximate within n/sup 1-ε/
• Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
• Domination When the Stars Are Out
• On Approximate Solutions for Combinatorial Optimization Problems
• Design of microarray probes for virus identification and detection of emerging viruses at the genus level. [europepmc]
• An efficient RNA interference screening strategy for gene functional analysis. [europepmc]
• KnowLife: a versatile approach for constructing a large knowledge graph for biomedical sciences. [europepmc]
• On Efficient Deployment of Wireless Sensors for Coverage and Connectivity in Constrained 3D Space. [europepmc]
• Critical controllability analysis of directed biological networks using efficient graph reduction. [europepmc]
• Identification of Differentially Expressed Genes between Original Breast Cancer and Xenograft Using Machine Learning Algorithms. [europepmc]
• Identifying Patients with Atrioventricular Septal Defect in Down Syndrome Populations by Using Self-Normalizing Neural Networks and Feature Selection. [europepmc]
• Automatic identification of optimal marker genes for phenotypic and taxonomic groups of microorganisms. [europepmc]
• High-throughput in vivo mapping of RNA accessible interfaces to identify functional sRNA binding sites. [europepmc]
• Capturing sequence diversity in metagenomes with comprehensive and scalable probe design. [europepmc]
• Analysis of Expression Pattern of snoRNAs in Different Cancer Types with Machine Learning Algorithms. [europepmc]
• Immunosignature Screening for Multiple Cancer Subtypes Based on Expression Rule. [europepmc]
• R.ROSETTA: an interpretable machine learning framework. [europepmc]
• Optimization of Cavity-Based Negative Images to Boost Docking Enrichment in Virtual Screening. [europepmc]
• Algorithmic Study of Online Multi-Facility Location Problems. [europepmc]
• Identification of Type 2 Diabetes Biomarkers From Mixed Single-Cell Sequencing Data With Feature Selection Methods. [europepmc]
• Multiset multicover methods for discriminative marker selection. [europepmc]
• A deep reinforcement learning algorithm for the rectangular strip packing problem. [europepmc]
• Computational complexity drives sustained deliberation. [europepmc]
• Near-optimal distributed dominating set in bounded arboricity graphs. [europepmc]
• On the fundamental resource for exponential advantage in quantum channel learning. [europepmc]
• Connectivity Labeling in Faulty Colored Graphs. [europepmc]