论文标题
认识何时偏好系统接近录取主列表
Recognizing when a preference system is close to admitting a master list
论文作者
论文摘要
优先系统$ \ MATHCAL {I} $是一个无方向的图表，顶点在其邻居中具有首选项，而$ \ Mathcal {i} $如果所有首选项都可以从与所有顶点的单个订购中得出，则允许主列表。我们研究了确定给定优先系统$ \ Mathcal {i} $是否接近基于三个不同距离测量的主列表的问题。我们确定以下问题的计算复杂性：$ \ MATHCAL {i} $可以通过（I）$ K $交换在偏好中修改，（ii）$ k $ edge删除，或（iii）$ k $ vertex删除删除，以便所产生的实例允许公认的实例？我们从参数化复杂性和近似的角度详细研究了这些问题。我们还提出了两个与稳定且受欢迎的比赛有关的应用程序。
A preference system $\mathcal{I}$ is an undirected graph where vertices have preferences over their neighbors, and $\mathcal{I}$ admits a master list if all preferences can be derived from a single ordering over all vertices. We study the problem of deciding whether a given preference system $\mathcal{I}$ is close to admitting a master list based on three different distance measures. We determine the computational complexity of the following questions: can $\mathcal{I}$ be modified by (i) $k$ swaps in the preferences, (ii) $k$ edge deletions, or (iii) $k$ vertex deletions so that the resulting instance admits a master list? We investigate these problems in detail from the viewpoint of parameterized complexity and of approximation. We also present two applications related to stable and popular matchings.
