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

By Jon M. Kleinberg, É. Tardos. 1999

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “Starting with [25] and [47] where the problem of generating shared randomness from correlated randomness and vice-versa, respectively, were considered, several important variants have been studied such as correlated sampling [11], [16], [34], [38] and noninteractive simulation [20], [27], [36].”
The Design of Approximation Algorithms (2011, background): “10 is due to Kleinberg and Tardos [197]; the uniform labeling problem models a problem arising in image processing.”
Learning associative Markov networks (2004, methodology): “For K > 2, the MAP problem is NP-hard, but a procedure based on a relaxed linear program guarantees a factor 2 approximation of the optimal solution (Boykov et al., 1999b; Kleinberg & Tardos, 1999).”
Semi-supervised graph clustering: a kernel approach (2005, background): “Choosing squared Euclidean distance as the cluster distortion measure and the generalized Potts potential (Kleinberg and Tardos 1999) as the constraint violation potential, the semi-supervised clustering objective can be expressed as: where M is the set of must-link constraints, C is the set of…”
Classification in Networked Data: A Toolkit and a Univariate Case Study (2007, unknown): “Following this idea and subsequent work connecting classiﬁcation to the problem of computing minimum cuts (Kleinberg and Tardos, 1999), Blum and Chawla (2001) investigate how to deﬁne weighted edges for a transductive classiﬁcation problem such that polynomial-time mincut algorithms give optimal…”
Fast Approximate Energy Minimization with Label Costs (2010, methodology): “If each Vpq defines a metric, then minimizing (2) is known as the metric labeling problem (Boykov et al. 2001; Kleinberg and Tardos 2002 ) and can be optimized effectively with the α-expansion algorithm.”
Regularization and Semi-supervised Learning on Large Graphs (2004, result): “We also note closely related work on metric labeling [ 10 ].”
Parallel repetition: simplifications and the no-signaling case (2006, result): “However, later a counterexample to this conjecture was given [For89].”
Fast approximate energy minimization via graph cuts (2001, background): “Note that Kleinberg and Tardos [ 27 ] develop an algorithm for minimizing E which also has optimality properties.”
Seeing Stars: Exploiting Class Relationships for Sentiment Categorization with Respect to Rating Scales (2005, background): “But we can also think of our task as a metric labeling problem (Kleinberg and Tardos, 2002), a special case of the maximum a posteriori estimation problem for Markov random fields, to explicitly encode our desideratum.”
A Study of Global Inference Algorithms in Multi-document Summarization (2007, methodology): “The formulation presented in Equation 1 is very similar to the classification with pairwise similarities problem studied by Kleinberg and Tardos [14].”
A probabilistic framework for semi-supervised clustering (2004, background): “, iterated conditional modes (ICM) [9, 40], belief propagation [34, 36], and linear programming relaxation [28].”
A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems (2014, background): “A well known class of such models, are models with metric regularizers [18, 45, 19].”