论文研究 陷阱选择程序的计算复杂性

在本文中,我们在有限的一组备选方案上定义了两个版本的未陷集(弱和强未陷集)。 这些版本被认为是选择程序,它在更一般的情况下(即,当替代方案不一定具有可比性时)扩展了未陷井集的概念。 我们证明,它们都与比赛的“最佳循环”选择程序一致。 在弱锦标赛中,强势未陷集等同于Getcha选择过程,而弱势未陷集恰好是文献中研究的未陷害集。 我们还提出了用于计算每个集合的多项式时间算法。