Approximation Algorithms

By Vijay V. Vazirani. Springer Berlin Heidelberg, 2001

448 citations recorded by the source corpus.

How researchers see this paper

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

A statistical approach to rule learning (2006, background): “It is well known that the greedy algorithm is a 1 + lnn approximation algorithm, that is, if the smallest consistent rule set contains s rules, then it generates at most s ∑n i=1 1 n ≤ s(1 + lnn) rules, where n is the number of positive instances (Vazirani, 2003; Haussler, 1988).”
An Approximate, Efficient LP Solver for LP Rounding (2013, unknown): “N”
Online team formation in social networks (2012, background): “lem, which has additional logarithmic lower-bound factors even in the offline case [22].”
Group testing: an information theory perspective (2019, unknown): “To make this intuition more precise, we describe a connection to the set cover problem (see [191]).”