Algorithms for automatic ranking of participants and tasks in an anonymized contest
Algorithms for automatic ranking of participants and tasks in an anonymized contest
复制标题
匿名竞赛中参与者和任务自动排名的算法
DOI：
10.1016/j.tcs.2018.07.014
复制
发表时间：
2018
影响因子：
1.1
通讯作者：
Gatterbauer, Wolfgang
中科院分区：
文献类型：
--
作者：
Jiao, Yang;Ravi, R.;Gatterbauer, Wolfgang
我们引入了一组新的问题的基础上链编辑问题。在我们的Chain Editing版本中，我们有一组参与者和一组任务，每个参与者都要尝试。对于每个参与者-任务对，我们知道参与者是否成功完成了任务。我们假设参与者解决任务的能力各不相同，任务的难度也各不相同。在一个理想的世界里，较强的参与者应该成功完成较弱参与者成功完成的任务的超集。类似地，较容易的任务应该由成功完成较难任务的参与者的超集成功完成。事实上，一个较强的参与者可能会在一个较弱的参与者成功的任务中失败。我们的目标是通过翻转最小数量的参与者-任务关系来找到参与者-任务关系的完美嵌套，这意味着这样一个“最近的完美排序”是最接近参与者优势和任务难度的真实情况。该问题的许多变体都是NP难的，我们提出了六个自然接近的链编辑问题版本，并对它们的复杂性进行了分类。ak-near链编辑问题的输入包括最终解决方案需要“接近”的参与者（或任务）的初始排序，通过将每个参与者（或任务）从初始排序移动到mostk个位置。我们在sixk-near问题的复杂性方面获得了令人惊讶的结果：其中五个问题可以使用动态规划在多项式时间内求解，但其中一个问题是NP难的。
We introduce a new set of problems based on theChain Editing problem. In our version of Chain Editing, we are given a set of participants and a set of tasks that every participant attempts. For each participant-task pair, we know whether the participant has succeeded at the task or not. We assume that participants vary in their ability to solve tasks, and that tasks vary in their difficulty to be solved. In an ideal world, stronger participants should succeed at a superset of tasks that weaker participants succeed at. Similarly, easier tasks should be completed successfully by a superset of participants who succeed at harder tasks. In reality, it can happen that a stronger participant fails at a task that a weaker participant succeeds at. Our goal is to find aperfect nesting of the participant-task relationsby flipping a minimum number of participant-task relations, implying such a “nearest perfect ordering” to be the one that is closest to the truth of participant strengths and task difficulties. Many variants of the problem are known to be NP-hard.We propose six naturalk-near versions of the Chain Editing problem and classify their complexity. The input to ak-near Chain Editing problem includes an initial ordering of the participants (or tasks) that the final solution is required to be “close” to, by moving each participant (or task) at mostkpositions from the initial ordering. We obtain surprising results on the complexity of the sixk-near problems: Five of the problems are polynomial-time solvable using dynamic programming, but one of them is NP-hard.