Relaxed triangle inequality ratio of the Sorensen-Dice and Tversky indexes

In this work, we calculate a tight relaxed triangle inequality ratio for some of the most well-known indexes used in finding dissimilarities between two finite sets known as the Sorensen-Dice and Tversky indexes. This relaxed triangle inequality ratio affects efficiency and approximation ratios of recent algorithms for many combinatorial problems such as traveling salesman and nearest neighbor search. Because of that, there are many works providing ratios for several other indexes. In this work, we focus on the Tversky index, which is a generalization of many dissimilarity indexes commonly used in practice. We provide the tight ratio of the Tversky index in this paper. Because the Sorensen-Dice index is a special case of the Tversky index, we know from the results that the tight ratio for the Sorensen-Dice index is equal to 1.5. (C) 2017 Elsevier B.V. All rights reserved.