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
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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Classification and Regression Trees.
Gordon, A. D., Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984) · Biometrics · doi:10.2307/2530946 · Cited by 23,522
Classification and Regression Trees.
Ryzin, J. V., Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1986) · Journal of the American Statistical Association · doi:10.2307/2288003 · Cited by 20,825
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988
Spatial Interaction and the Statistical Analysis of Lattice Systems
Besag, J. (1974) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1974.tb00999.x · Cited by 6,067
On the Statistical Analysis of Dirty Pictures
Besag, J. (1986) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1986.tb01412.x · Cited by 4,191
Some generalized order-disorder transformations
Potts, R. B. (1952) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100027419 · Cited by 2,122
Markov Random Fields and Their Applications
Kindermann, R., & Snell, J. L. (1980) · Contemporary Mathematics · doi:10.1090/conm/001 · Cited by 1,290
Markov Random Field Modeling in Computer Vision
Li, S. Z. (1995) · Computer Science Workbench · doi:10.1007/978-4-431-66933-3 · Cited by 1,276
Exact Maximum A Posteriori Estimation for Binary Images
Greig, D. M., Porteous, B. T., & Seheult, A. H. (1989) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1989.tb01764.x · Cited by 1,055
Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images*
Geman, S., & Geman, D. (1993) · Journal of Applied Statistics · doi:10.1080/02664769300000058 · Cited by 983
Enhanced hypertext categorization using hyperlinks
Chakrabarti, S., Dom, B., & Indyk, P. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276332 · Cited by 769
Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
GEMAN, S., & GEMAN, D. (1987) · Readings in Computer Vision · doi:10.1016/b978-0-08-051581-6.50057-x · Cited by 750
Classification and Regression Trees
Gehrke, J. (2005) · Encyclopedia of Data Warehousing and Mining · doi:10.4018/978-1-59140-557-3.ch027 · Cited by 730
The Complexity of Multiterminal Cuts
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539792225297 · Cited by 662
Probabilistic approximation of metric spaces and its algorithmic applications
Bartal, Y. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548477 · Cited by 635
A maximum-flow formulation of the N-camera stereo correspondence problem
Roy, S., & Cox, I. J. (2002) · Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271) · doi:10.1109/iccv.1998.710763 · Cited by 485
Markov random fields with efficient approximations
Boykov, Y., Veksler, O., & Zabih, R. (2002) · Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231) · doi:10.1109/cvpr.1998.698673 · Cited by 422
Random field models in image analysis
Dubes, R. C., & Jain, A. K. (1989) · Journal of Applied Statistics · doi:10.1080/02664768900000014 · Cited by 418
Two-dimensional discrete Markovian fields
Woods, J. (1972) · IEEE Transactions on Information Theory · doi:10.1109/tit.1972.1054786 · Cited by 381
Segmentation by grouping junctions
Ishikawa, H., & Geiger, D. (2002) · Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231) · doi:10.1109/cvpr.1998.698598 · Cited by 163
Minimum 0-Extensions of Graph Metrics
Karzanov, A. V. (1998) · European Journal of Combinatorics · doi:10.1006/eujc.1997.0154 · Cited by 92
Rounding algorithms for a geometric embedding of minimum multiway cut
Karger, D. R., Klein, P. N., Stein, C., Thorup, M., & Young, N. E. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301430 · Cited by 63
Cited by
Opinion Mining and Sentiment Analysis
Pang, B., & Lee, L. (2008) · now publishers, Inc. eBooks · doi:10.1561/9781601981516 · Cited by 6,720
Opinion mining and sentiment analysis
Pang, B., & Lee, L. (2008) · Foundations and Trends® in Information Retrieval · doi:10.1561/1500000011 · Cited by 6,372
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., & Zemel, R. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090255 · Cited by 3,501
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981851 · Cited by 2,959
Similarity estimation techniques from rounding algorithms
Charikar, M. S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509965 · Cited by 2,220
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
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.