Approximation algorithms for combinatorial problems

1974/12/01 by David S. Johnson · 32 citations
Computer Science · #Constraint Satisfaction and Optimization #Data Management and Algorithms #Advanced Graph Theory Research

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

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\n 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\n 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\n 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\n Lift-and-Project Methods