file.pdf (131.38 kB)
Download file

A constant factor approximation algorithm for a class of classification problems

Download (131.38 kB)
journal contribution
posted on 01.01.1988, 00:00 by Anupam Gupta, Eva Tardos
In 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.

History

Publisher Statement

All Rights Reserved

Date

01/01/1988

Usage metrics

Exports