Conjecture on the complexity of the ranking algorithm

Let mm be the number of labels, and let Algorithm~ be the algorithm described in the paper for checking combinations of pairwise label preferences and finding R^R,PM\hat{\mathbb{R}}^{M}_{\ell_R,{\mathcal{P}}}. Complexity conjecture. Algorithm~ has to perform less than m!1.8m!^{1.8} computations, and its outer-complexity is in O(m!1.8)\mathcal{O}(m!^{1.8}). 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.