Fast approximation algorithms for fractional packing and covering problems

By Serge A. Plotkin, David B. Shmoys, É. Tardos. 1991

How researchers see this paper

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

Citations in the corpus

Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer (2019, methodology): “Multiplicative weight update ( MWU ) technique lies at the core of many learning algorithms [8], [19], [45], [20], [34].”
Introduction to Online Convex Optimization (2016, methodology): “Approximation algorithms that arise via simple Lagrangian relaxation techniques were pioneered by Plotkin, Schmoys and Tardos (84).”
Expander flows, geometric embeddings and graph partitioning (2009, unknown): “, [26, 12]), which may be useful in practice.”
Tight Bounds for Approximate Carathéodory and Beyond (2015, methodology): “One remarkable feature of our problem is that it connects three ways in which sparsification has been done: via Mirror Descent (or more commonly, via multiplicative weight update) as in (Plotkin et al., 1991; Arora et al., 2012; Juditsky et al., 2013), via Frank-Wolfe methods (Garber & Hazan, 2013; ”
Tight approximation algorithms for maximum general assignment problems (2006, background): “2) can also be obtained via Lagrangian LP algorithms [11, 25, 33, 34].”
Expander flows, geometric embeddings and graph partitioning (2004, unknown): “, [26, 12]), which may be useful in practice.”
Bandits with Knapsacks (2013, methodology): “Borrowing an idea from [5, 20, 38], we will use the multiplica tives weights update method to learn the optimal dual vector.”
A combinatorial, primal-dual approach to semidefinite programs (2007, methodology): “For general SDPs the computation of the feedback function amounts to solving a very simple LP (see Section 3), but the convergence time of the algorithm depends upon the “width” of the problem as in the corresponding LP algorithms [24].”
Fair Allocation of Indivisible Public Goods (2018, background): “is in contrast to matroid and matching constraints, for which single-agent problems are polynomial time solvable. A classic measure of how easy it is to satisfy the packing constraints is the width ρ [31]: ρ = max k∈[K] P j∈[m] akj bk . (1) Packing constraints capture the general Knapsack setting, i”
Optimal hierarchical decompositions for congestion minimization in networks (2008, methodology): “There exists methods ([31], [26], [29], [18], [23]) for efficiently computing approximate solutions to such problems.”
Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent (2014, unknown): “It can be generalized to solve the matrix version of MWU [8, 33], as well as to incorporate the widthreduction technique [8, 34].”