  We introduce a new set of problems based on the Chain Editing problem. In our
version of Chain Editing, we are given a set of anonymous participants and a
set of undisclosed 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 participants succeeds at. Our goal is to find a perfect nesting of the
participant-task relations by 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 natural $k$-near versions of the Chain Editing problem and
classify their complexity. The input to a $k$-near Chain Editing problem
includes an initial ordering of the participants (or tasks) that we are
required to respect by moving each participant (or task) at most $k$ positions
from the initial ordering. We obtain surprising results on the complexity of
the six $k$-near problems: Five of the problems are polynomial-time solvable
using dynamic programming, but one of them is NP-hard.

Data Structures and Algorithms