Student or educator? Sign up with your school email and get 6 months of Pro free.
Cited by 400

The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.

Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields

Kleinberg, Jon, Tardos, Éva·2002·Journal of the ACM

Abstract

In a traditional classification problem, we wish to assign one of k labels (or classes) to each of n objects , in a way that is consistent with some observed data that we have about the problem. An active line of research in this area is concerned with classification when one has information about pairwise relationships among the objects to be classified; this issue is one of the principal motivations for the framework of Markov random fields, and it arises in areas such as image processing, biometry, and document analysis. In its most basic form, this style of analysis seeks to find a classification that optimizes a combinatorial function consisting of assignment costs ---based on the individual choice of label we make for each object---and separation costs ---based on the pair of choices we make for two "related" objects.We formulate a general classification problem of this type, the metric labeling problem ; we show that it contains as special cases a number of standard classification frameworks, including several arising from the theory of Markov random fields. From the perspective of combinatorial optimization, our problem can be viewed as a substantial generalization of the multiway cut problem, and equivalent to a type of uncapacitated quadratic assignment problem .We provide the first nontrivial polynomial-time approximation algorithms for a general family of classification problems of this type. Our main result is an O (log k log log k )-approximation algorithm for the metric labeling problem, with respect to an arbitrary metric on a set of k labels, and an arbitrary weighted graph of relationships on a set of objects. For the special case in which the labels are endowed with the uniform metric ---all distances are the same---our methods provide a 2-approximation algorithm.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/585265.585268

Cites

23 of 23 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 23 references

Cited by

See all 400

Metadata

Authors
Kleinberg, J., & Tardos, É.
Venue
Journal of the ACM
Published
2002-09
Volume
49
Issue
5
Pages
616-639
ISSN
  • 0004-5411 (ISSN-L)
  • 1557-735X
OpenAlex
W2061130579
Cited by
400
References
23
FWCI
17.45
Type
journal article
Language
en
Open access
closed

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. https://app.cochat.ai/papers/10.1145/585265.585268
The paper
Kleinberg, J., & Tardos, É. (2002). Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. Journal of the ACM. https://doi.org/10.1145/585265.585268

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.