The k-Allocation Problem and Its Variants
The k-Allocation Problem and Its Variants
复制标题
k-分配问题及其变体
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Asaf Levin
中科院分区：
文献类型：
--
作者：
D. Hochbaum;Asaf Levin
在由一组评审员对项目进行评审和排序的过程中，假设每个评审员评审一部分项目列表，最多可评审k个项目。然后，每个评审员对所有k个项目进行排名和比较。k-分配问题是在评审员的专业知识集中确定最多k个项目分配给每个评审员，使得所产生的被评审项目的联合具有某些期望的属性。k分配的一个属性是让所有项目对至少由一个审阅者进行比较。我们称之为k-完全问题。
在不能实现k-完全性质的情况下，人们可能会满足于其他性质。一个这样的基本要求是，每对项目通过一个排序路径是可比较的，该排序路径是项目的成对排序序列，意味着路径上所有对的比较。由于相对比较的鲁棒性随着排名路径的长度而恶化，另一个属性是在每对项目之间将存在至少一个排名路径，该排名路径具有至多两个跳或对于固定值q的q跳。增加排名的鲁棒性的另一个属性是找到k分配，使得每对之间至少有p个不相交的排名路径。
我们将所有这些问题建模为图问题，并证明了连通性-k-aloc问题是多项式可解的，除非k = 2，否则k-完全问题是NP-困难的，并且所有其他考虑的k-分配性质问题的变体对于k ≥2的所有值都是NP-完全的。我们提供近似算法的k-完全问题的相关的优化问题。
In the process of reviewing and ranking projects by a group of reviewers, each reviewer is assumed to review a partial list of projects, up to k projects. Each individual reviewer then ranks and compares all pairs of k projects. The k-allocation problem is to determine the allocation of up to k projects to each reviewer within the expertise set of the reviewer so that the resulting union of reviewed projects has certain desirable properties. One property of the k-allocation is to have all pairs of projects compared by at least one reviewer. This we call the k-complete problem.
In cases when the property of k-complete cannot be achieved, one might settle for other properties. One such basic requirement is that each pair of projects is comparable via a ranking path which is a sequence of pairwise rankings of projects implying a comparison of all pairs on the path. A k-allocation with a ranking path between each pair is the connectivity-k-aloc. Since the robustness of relative comparisons deteriorates with the length of the ranking path, another property is that between each pair of projects there will be at least one ranking path that has at most two hops or q hops for fixed values of q. Another property that increases robustness of the ranking is to find a k-allocation so there are at least p disjoint ranking paths between each pair.
We model all these problems as graph problems and show that the connectivity-k-aloc problem is polynomially solvable using matroid intersection, the k-complete problem is NP-hard unless k = 2, and all other considered variants of the k-allocation properties problem are NP-complete for all values of k ≥2. We provide approximation algorithms for an optimization problem related to the k-complete problem.