Editing 2-satisfiability (section)

===Data clustering===
One way of [[data clustering|clustering a set of data points]] in a [[metric space]] into two clusters is to choose the clusters in such a way as to minimize the sum of the [[diameter]]s of the clusters, where the diameter of any single cluster is the largest distance between any two of its points. This is preferable to minimizing the maximum cluster size, which may lead to very similar points being assigned to different clusters. If the target diameters of the two clusters are known, a clustering that achieves those targets may be found by solving a 2-satisfiability instance. The instance has one variable per point, indicating whether that point belongs to the first cluster or the second cluster. Whenever any two points are too far apart from each other for both to belong to the same cluster, a clause is added to the instance that prevents this assignment.

The same method also can be used as a subroutine when the individual cluster diameters are unknown. To test whether a given sum of diameters can be achieved without knowing the individual cluster diameters, one may try all maximal pairs of target diameters that add up to at most the given sum, representing each pair of diameters as a 2-satisfiability instance and using a 2-satisfiability algorithm to determine whether that pair can be realized by a clustering. To find the optimal sum of diameters one may perform a binary search in which each step is a feasibility test of this type. The same approach also works to find clusterings that optimize other combinations than sums of the cluster diameters, and that use arbitrary dissimilarity numbers (rather than distances in a metric space) to measure the size of a cluster.<ref>{{citation|first1=P.|last1=Hansen|first2=B.|last2=Jaumard|author2-link= Brigitte Jaumard |title=Minimum sum of diameters clustering|journal=Journal of Classification|volume=4|issue=2|year=1987|pages=215–226|doi=10.1007/BF01896987|s2cid=120583429}}.</ref> The time bound for this algorithm is dominated by the time to solve a sequence of 2-satisfiability instances that are closely related to each other, and {{harvtxt|Ramnath|2004}} shows how to solve these related instances more quickly than if they were solved independently from each other, leading to a total time bound of {{math|''O''(''n''<sup>3</sup>)}} for the sum-of-diameters clustering problem.<ref>{{citation|first1=Sarnath|last1=Ramnath|title=Dynamic digraph connectivity hastens minimum sum-of-diameters clustering|journal=[[SIAM Journal on Discrete Mathematics]]|volume=18|issue=2|pages=272–286|year=2004|doi=10.1137/S0895480102396099}}.</ref>