Conjecture on the complexity of the ranking algorithm
Conjecture on the complexity of the ranking algorithm
Let be the number of labels, and let Algorithm~ be the algorithm described in the paper for checking combinations of pairwise label preferences and finding . Complexity conjecture. Algorithm~ has to perform less than computations, and its outer-complexity is in . This conjecture gives an upper estimate for the time complexity of the algorithm, which is compared with both a naive implementation and the actual number of verifications in the paper. Its resolution is not established in the supplied text.
Sources & referencesView supporting material
Primary source
Yonatan Carlos Carranza Alarcón and Vu-Linh Nguyen, “Skeptical inferences in multi-label ranking with sets of probabilities”, arXiv:2210.08576 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.