Multiple-Winners Randomized Tournaments with Consensus for Optimization Problems in Generic Metric Spaces

摘要

Extensions of the randomized tournaments techniques introduced in [6, 7] to approximate solutions of 1-median and diameter computation of finite subsets of general metric spaces are proposed. In the linear algorithms proposed in [6] (resp. [7]) randomized tournaments are played among the elements of an input subset S of a metric space. At each turn the residual set of winners is randomly partitioned in nonempty disjoint subsets of fixed size. The 1-median (resp. diameter) of each subset goes to the next turn whereas the residual elements are discarded. The algorithm proceeds recursively until a residual set of cardinality less than a given threshold is generated. The 1-median (resp. diameter) of such residual set is the approximate 1-median (resp. diameter) of the input set S. The O(n log n) extensions proposed in this paper replace local single-winner tournaments by multiple-winners ones. Moreover consensus is introduced as multiple runs of the same tournament. Experiments on both synthetic and real data show that these new proposed versions give significantly better approximations of the exact solutions of the corresponding optimization problems.