Constant-Time Approximation Algorithms via Local Improvements

We present a technique for transforming classical approximation algorithms into constant-time algorithms that approximate the size of the optimal solution. Our technique is applicable to a certain subclass of algorithms that compute a solution in a constant number of phases. The technique is based on greedily considering local improvements in random order. The problems amenable to our technique include Vertex Cover, Maximum Matching, Maximum Weight Matching, Set Cover, and Minimum Dominating Set. For example, for Maximum Matching, we give the first constant-time algorithm that for the class of graphs of degree bounded by $d$, computes the maximum matching size to within $\eps n$, for any $\eps ≫ 0$, where $n$ is the number of nodes in the graph. The running time of the algorithm is independent of $n$, and only depends on $d$ and $\eps$.

Authors

• Huy N. Nguyen
• Krzysztof Onak

Keywords

• Approximation algorithms
• Distributed algorithms
• Computer science
• Random number generation
• Computational modeling
• Estimation Algorithm
• Running Time
• Random Order
• Maximum Size
• Set Of Covariates
• Maximum Matching
• Vertex Cover
• Random Number
• Minimum Size
• Size Estimation
• Reachable
• Perfect Match
• Constant Factor
• Size Time
• Minimum Coverage
• Maximum Degree
• Sequential Algorithm
• Recursive Algorithm
• Distributed Algorithm
• Constant Approximation
• Phase Of The Algorithm
• Query Point
• Set Cover Problem
• Graph Matching
• Constant Probability