Approximation Algorithms

By Mohit Singh, K. Talwar. 1997

Increasing global competition, rapidly changing markets, and greater consumer awareness have altered the way in which corporations do business. To become more efficient, many industries have sought to model some operational aspects by gigantic optimization problems. It is not atypical to encounter models that capture 10(6) separate "yes" or "no" decisions to be made. Although one could, in principle, try all 2(10(6)) possible solutions to find the optimal one, such a method would be impractically slow. Unfortunately, for most of these models, no algorithms are known that find optimal solutions with reasonable computation times. Typically, industry must rely on solutions of unguaranteed quality that are constructed in an ad hoc manner. Fortunately, for some of these models there are good approximation algorithms: algorithms that produce solutions quickly that are provably close to optimal. Over the past 6 years, there has been a sequence of major breakthroughs in our understanding of the design of approximation algorithms and of limits to obtaining such performance guarantees; this area has been one of the most flourishing areas of discrete mathematics and theoretical computer science.

Subfields: Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Polyjuice: Generating Counterfactuals for Explaining, Evaluating, and Improving Models (2021, methodology): “We use a classic greedy algorithm (Vazirani, 2013) to select a subset of T ∗ ⊂ T , such that the aggregated coverage is maximized, and the weight is minimized.”
Compressed data aggregation for energy efficient wireless sensor networks (2011, methodology): “So we have ρ = 2 [21] in our implementation of the randomized algorithm.”
The communication requirements of efficient allocations and supporting prices (2006, methodology): “For this purpose, we use the following three concepts, listed from weaker to stronger, which are standard in the computer science literature on approximation algorithms [46]:”
Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints (2013, methodology): “et cover [47] and hence the guarantee follows from Theorem 1 in [47]. The surrogate problem in this instance is a simple knapsack problem that can be solved nearly optimally using dynamic programming [44]. As stated in the proof, the greedy algorithm for the submodular set cover problem [47] is in f”
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms (2014, methodology): “r µas input, and outputs a super arm S ∈S, such that Pr[rµ(S) ≥α·optµ] ≥ β. Here β is the success probability of the oracle. Many computationally hard problems do admit eﬃcient approximation oracles (Vazirani, 2004). With an (α,β)-approximation oracle, it is no longer fair to compare the performance”
Market equilibrium via a primal-dual-type algorithm (2002, unknown): “At the heart of the primal-dual schema lies the following powerful paradigm: the algorithm starts with trivial solutions to the primal and dual LP’s corresponding to the given problem and alternately improves these solutions until a termination criterion is met (see [15] for a detailed discussion); ”
Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems (2014, unknown): “As such, it has been applied to many NP-hard combinatorial problems up to now, including set-cover, Ste iner-network, scheduling, Steiner tree, feedback vertex set, facility location, to mention only a few [17], [18].”
What Color Is Your Jacobian? Graph Coloring for Computing Derivatives (2005, unknown): “Graph and hypergraph coloring have been used in a wide collection of application areas in addition to optimization: register allocation in compilers [24], radio and wireless networks [44, 84], scientific computing [51, 73, 74, 111], data movement in distributed and parallel computing [58], facility ”
Clustering of database sequences for fast homology search using upper bounds on alignment score. (2004, methodology): “Here, we employed a greedy algorithm for large databases [19, 23] .”
Weighted coloring based channel assignment for WLANs (2005, unknown): “Since the unweighted graph coloring problem is known to be NP-Hard, a number of techniques have been proposed in the literature to approximately solve the unweighted graph coloring problem [5].”
The Design of Approximation Algorithms (2011, methodology): “We bent this rule somewhat in order to cover the recent, exciting work by Arora, Rao, and Vazirani [22] applying semidefinite programming to the uniform sparsest cut problem.”