TY - GEN

T1 - A constant factor approximation algorithm for a class of classification problems

AU - Gupta, Anupam

AU - Tardos, Éva

PY - 2000

Y1 - 2000

N2 - 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(log |L| log log |L|) approximation algorithm for it. The algorithm is based on solving a linear programming relaxation of a natural integer program and then randomized rounding. In this paper we consider an important case of the metric labeling problem, in which the metric is the truncated linear mettic. This is a natural non-uniform and robust metric, and it arises in a number of applications. We give a combinatorial 4-approximation algorithm for this metric. Our algorithm is a natural local search method, where the local steps are based on minimum cut computations in an appropriately constructed graph. Our method extends previous work by Boykov, Veksler and Zabih on more restricted classes of metrics.

AB - 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(log |L| log log |L|) approximation algorithm for it. The algorithm is based on solving a linear programming relaxation of a natural integer program and then randomized rounding. In this paper we consider an important case of the metric labeling problem, in which the metric is the truncated linear mettic. This is a natural non-uniform and robust metric, and it arises in a number of applications. We give a combinatorial 4-approximation algorithm for this metric. Our algorithm is a natural local search method, where the local steps are based on minimum cut computations in an appropriately constructed graph. Our method extends previous work by Boykov, Veksler and Zabih on more restricted classes of metrics.

UR - http://www.scopus.com/inward/record.url?scp=0033687759&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033687759&partnerID=8YFLogxK

U2 - 10.1145/335305.335397

DO - 10.1145/335305.335397

M3 - Conference contribution

AN - SCOPUS:0033687759

SN - 1581131844

SN - 9781581131840

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 652

EP - 658

BT - Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000

T2 - 32nd Annual ACM Symposium on Theory of Computing, STOC 2000

Y2 - 21 May 2000 through 23 May 2000

ER -