The Design of Approximation Algorithms

By David P. Williamson, David B. Shmoys. 2011

1,358 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/148ce39ea28dd92bc32eec90000358f393db06d2

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Near optimal placement of virtual network functions (2015, methodology): “Clearly, an optimal solution to (GAP-LP) is a lower bound on the optimal integral solution.”
Exactly Computing the Local Lipschitz Constant of ReLU Networks (2020, background): “We will gloss over some formalisms where we can, though a more formal discussion can be found here (Williamson & Shmoys, 2011; Hromkoviˇc, 2013; Demaine, 2014).”
Globally-Consistent Rule-Based Summary-Explanations for Machine Learning Models: Application to Credit-Risk Evaluation (2019, positive): “We show that OptConsistentRule generalizes the Minimum Set Cover Problem (MinSetCover), which can be stated as follows (Williamson and Shmoys 2011): there is a ground set of elements E = {1, . . . , n}, a collection of subsets S1, . . . , Sρ ⊆ E, and the goal is to find the smallest collection of…”
Assortment Optimization Under Variants of the Nested Logit Model (2014, background): “It is well-known that one can construct a solution to the knapsack problem in (9) by using its continuous relaxation in (11) and the objective value of this solution would deviate from the optimal objective value of the knapsack problem by no more than a factor of two; see Williamson and Shmoys (201”
Rounding Methods for Discrete Linear Classification (2013, methodology): “Despite its relative weak guarantees, the randomized rounding procedure can be used as a building block Algorithm 2 Greedy Rounding (GR) Parameters: A set of m examples, an integer k ≤ n 1.”
Geometric Approximation Algorithms (2011, methodology): “A more general treatment of approximation algorithms is provided by Williamson and Shmoys [ WS11 ] and Vazirani [ Vaz01 ].”
Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search (2018, background): “Approximation algorithms provide theoretical guarantees, but their scalability may be limited and algorithms with satisfactory bounds may not exist [3, 38].”
Optimal order placement in limit order markets (2012, methodology): “rity of orders and optimize over X2RK+1 + , then round to number of shares in the last step. This procedure, which corresponds to the convex relaxation of the underlying integer optimization problem (Williamson and Shmoys 2011), is indeed the standard approach used in the optimal execution literatur”