Geometry of cuts and metrics

By M. Deza, Monique Laurent. Algorithms and Combinatorics, 2009

1,146 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/088ab372dff19fb8837d0f48d395d1a987251f3f

How researchers see this paper

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

In Computer Graphics and Computer-Aided Design

In Industrial and Manufacturing Engineering

Citations in the corpus

Euclidean quotients of finite metric spaces (2004, background): “Since X is finite, there is an isometric embedding T : G(X) → lp (see [14]).”
Nearest-Neighbor Searching and Metric Space Dimensions (2005, background): “This is sometimes called the Steinhaus transform[DL97].”
The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/ (2005, neutral): “Definition 2.11 (Hyper-contractive Operator).”
Computing geodesics and minimal surfaces via graph cuts (2003, methodology): “However, it is used explicitly in the theory of Finite Metric Spaces [10, 20] that, in particular, studies embeddability of graphs in normed spaces.”
The Convex Geometry of Linear Inverse Problems (2010, background): “We then consider real algebraic varieties [9]: Definition 4.1.”
Threshold Dynamics for Networks with Arbitrary Surface Tensions (2015, methodology): “We turn to the recovery sequence for a given admissible u.”
Non-convex mixed-integer nonlinear programming: A survey (2012, background): “These are surveyed in the book by Deza and Laurent [119].”
A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas (2018, methodology): “1997a Knots and electricity. In: S. Suzuki, ed., Knots ’96 (Proc. Fifth Internat. Research Institute Math. Soc. Japan, Tokyo, 1996), pp. 213–230. World Scientific, Singapore, 1997. §2, “A state summation for classical electrical networks”, uses a form of the parametrized dichromatic polynomial QΓ(B,”
A BIRD'S EYE VIEW OF THE CUT METHOD AND A SURVEY OF ITS APPLICATIONS IN CHEMICAL GRAPH THEORY (2008, background): “See [9, 28] for more information on this embedding as well as for proofs.”
Properties of Classical and Quantum Jensen-Shannon Divergence (2008, background): “The most general measurement with k outcomes is described by k positive matrices A1, . . . , Ak, which satisfy ∑k i=1Ai = I.”
Cut, Glue, & Cut: A Fast, Approximate Solver for Multicut Partitioning (2014, methodology): “The max-cut problem [10] (also known as the weighted 2-coloring problem) is a basic subproblem which has to be solved in the Kerninghan-Lin method [16], Expand-andExplore [7], PlanarCC [23] and also our method.”
Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations (2009, background): “where C is the set of all cycles of G, see for instance [5] or [17].”
Motion Trajectory Segmentation via Minimum Cost Multicuts (2015, methodology): “The minimum cost multicut [10, 12] framework allows to formulate the trajectory segmentation as an unbalanced grouping problem - allowing for very small but reasonable segments to be retrieved.”
Optimization for machine learning (2010, background): “Let us remark that several polynomial algorithms are known to separate intractable families of cutting planes of the max-cut polytope (Deza and Laurent, 1997), closely related to the marginal polytope.”
Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND (2009, background): “Nevertheless, it has been studied extensively in the theory of metric spaces [ DL97 ] under the area of negative-type distances.”
Distance covariance in metric spaces (2011, neutral): “resurgence of interest recently due to its uses in theoretical computer science, where embeddings of metric spaces, such as graphs, play a useful role in algorithms; see, for example, Naor (2010) and Deza and Laurent (1997). The fact that Euclidean space has negative type is behind the following cha”