The Setting
Take a nonnegative integer and an ordered set of vertices equipped with pairwise capacities. The uniform sparsest-cut problem and its Goemans-Linial semidefinite programming (SDP) relaxation compare bipartitions of with negative-type semimetrics on . The question is how small the relaxation value can be relative to the combinatorial optimum.
The Definition
Definition 1. A capacity function on is a real matrix satisfying (1)✦
Given any function , the sum over unordered pairs is the real number (2)✦
For a capacity function satisfying (1) and a nonempty proper subset , the uniform sparsest-cut ratio is the real number (3)✦
The uniform sparsest-cut value of a capacity function on is the real number defined from (3) by (4)✦
In -dimensional Euclidean space with norm , a negative-type semimetric on is a function for which there exist vectors () satisfying (5)✦
A feasible SDP metric on is a negative-type semimetric (5) whose sum (2) satisfies (6)✦
Associated to each capacity function on , the Goemans-Linial relaxation value is the real number defined from (2) and (6) by (7)✦
What Is Checked
The definitions (1) through (7) are stated over a nonnegative integer , real-valued functions on , vertex subsets , capacity matrices in (3), (4), and (7), and vectors in -dimensional Euclidean space .