Approximation Algorithms for Maximum Non-Clashing Teaching

Non-clashing teaching is a canonical theoretical setting in machine teaching, and its fundamental problem is to compute the Non-Clashing Teaching Dimension (NCTD). Given a collection of candidate targets, a teacher selects at most $k$ labeled examples for each target. If two targets can be distinguished by one of the selected examples, we call the pair non-clashing. NCTD asks for the minimum budget $k$ needed to make every pair of targets non-clashing. However, even deciding whether $k=1$ suffices is NP-hard, indicating the computational difficulty of directly optimizing $k$. Motivated by fixed budgets that may not permit complete separation, we study Maximum Non-Clashing Teaching (MNCT), which maximizes the number of non-clashing target pairs for a given $k$. Using linear programming, we develop a technique based on configurations that achieves an approximation ratio of $1-(1-\frac{1}{2\lceil k/r\rceil }{)}^{2\lceil k/r\rceil }$ for any fixed $1\le r\le k$, and provides a tradeoff between running time and approximation quality. Consequently, for every fixed $k$, setting $r=k$ yields a $3/4$-approximation. These approximation guarantees extend naturally to the weighted setting in which target pairs carry nonnegative weights. We also establish several complexity results, including APX-hardness for weighted MNCT even when $k=1$. Finally, we give exact polynomial-time algorithms for some special cases.