file.pdf (131.38 kB)
A constant factor approximation algorithm for a class of classification problems
journal contribution
posted on 1988-01-01, 00:00 authored by Anupam Gupta, Eva TardosIn a traditional classification problem, we wish to assign labels
from a set L to each of n objects so that the labeling is
consistent with some observed data that includes pairwise relationships
among the objects. Kleinberg and Tardos recently
formulated a general classification problem of this type, the
“metric labeling problem”, and gave an O(logjLlogjL)
approximation algorithm for it. The algorithm is based on
solving a linear programming relaxation of a natural integer
program and then randomized rounding.