acceptodds
Under review as a conference paper at ICLR 2027

Approximation Algorithms for Maximum Non-Clashing Teaching

Abstract

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 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 needed to make every pair of targets non-clashing. However, even deciding whether suffices is NP-hard, indicating the computational difficulty of directly optimizing . 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 . Using linear programming, we develop a technique based on configurations that achieves an approximation ratio of for any fixed , and provides a tradeoff between running time and approximation quality. Consequently, for every fixed , setting yields a -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 . Finally, we give exact polynomial-time algorithms for some special cases.

Primary area:
learning theory
Keywords:
machine teaching, non-clashing teaching, approximation algorithms, linear programming, submodular maximization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_Tw2COpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors study Maximum Non-Clashing Teaching problem. In this problem, each target receives at most kk examples and the objective is to maximize the number of separated target pairs. In this work, they considered both positive as well as unrestricted teaching. They designed an LP based algorithm that gives a 34\frac{3}{4}-approximation for every fixed kk, with a tradeoff between running time and approximation quality. The paper also established an LP integrality gap. They also obtained hardness results, and also obtained exact algorithms for positive teaching on size-two and laminar concept classes.

Critical strengths

The paper has following strong points

  1. The fixed-budget formulation is a natural extension of non-clashing teaching. The paper is clearly written, and I did not find a major technical issue in the proofs. The approximation guarantees apply uniformly to positive and unrestricted teaching and extend to nonnegative pair weights.

  2. The explicit 34\frac{3}{4} integrality-gap construction is useful. I also liked the separation between weighted and unweighted size-two instances, which shows that pair weights can change the computational complexity even for a simple concept class.

Critical weaknesses
  1. It would be nice if the authors include some justifications regarding the applicability of the model and algorithms. The input explicitly lists the entire finite concept class and the labels of all examples under every target. This can be restrictive when the hypothesis class is large or represented implicitly. Moreover, the 34\frac{3}{4}-approximation algorithm takes ∣X∣O(k)|X|^{O(k)} time, apart from polynomial factors, so its cost can grow quickly with the budget.

  2. After configurations are enumerated, the approximation analysis uses independent rounding and a standard coverage inequality. The observation that each pair depends on its two endpoint targets is useful, but it would be helpful if the authors explain more clearly what the approach adds to existing methods for maximum coverage under group budgets.

  3. The approximation threshold for fixed budgets remains unresolved. The general-budget hardness result and the weighted budget-one APX-hardness result do not establish that 34\frac{3}{4} is optimal for unweighted instances with fixed kk. The integrality gap only limits the particular LP. The paper explicitly acknowledges this point. Moreover, it limits how definitive the approximation results are.

Questions for authors
  1. Can the dependence on kk be improved while retaining an approximation ratio close to 34\frac{3}{4}?

  2. Integrality gap suggests the proposed LP method won't improve the bound, but is there any generic lower bound for the problem?

Reviewer_2sQbOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces a fixed-budget counterpart to non-clashing teaching dimension: choose at most k examples per target to maximize the number, or total weight, of separated target pairs. The paper studies both unrestricted MNCT and its positive-only variant.

Critical strengths
  1. A well-motivated optimization formulation with a clean, unified approximation guarantee. Fixing the teaching budget and maximizing separation provides a meaningful alternative when complete separation is infeasible.

  2. The complementary results provide substantive structural insight. The paper goes beyond presenting an approximation algorithm. The size-two results are particularly informative: unweighted positive teaching admits an exact minimum-cost-flow algorithm, whereas allowing even binary pair weights makes the problem NP-hard. These results distinguish limitations arising from the relaxation from those arising from the problem’s combinatorial structure and weighting.

Critical weaknesses
  1. The algorithmic novelty needs sharper positioning against more specialized coverage formulations. The main comparison is with general matroid-constrained submodular maximization. However, after introducing configurations, the rounding analysis appears to depend only on independent slot choices, the fact that each objective term involves two target blocks, and an arithmetic–geometric mean/concavity argument.

  2. The partial-separation objective lacks an established learner-level interpretation. A pair is counted as separated when a distinguishing example occurs in either target’s teaching set. Consequently, the objective alone does not specify what a learner can infer from the examples actually presented for the true target. The paper motivates maximizing separated pairs as reducing ambiguity, but does not establish a decoding model or a relationship to identification error, expected learner performance, or worst-case ambiguity.

Questions for authors

My first question would be how this paper is related to existing approximation framework. Can MNCT be explicitly formulated as coverage under a partition constraint where each covered element depends on only two target blocks? Which parts of the configuration algorithm and its guarantee require new arguments beyond that abstraction?

I am also concerned about the approximation optimality. What hardness evidence constrains the achievable ratio for the central unweighted, fixed-budget problems?

In addition, does Theorem 6.5 extend immediately to arbitrary nonnegative pair weights?

Reviewer_7sjvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper presents approximation algorithms for Non-Clashing Teaching. In this problem, one is given a set X of examples and a set C⊆X\mathcal{C}\subseteq X of concepts. Now, the goal is to find a teaching set T(C)T(C) for each concept C∈CC\in\mathcal{C}. This set T(C)T(C) can include examples from CC and also from X∖CX\setminus C. Two concepts CC and C′C' are separated by TT if T(C)T(C) or T(C′)T(C') contains an example which is contained in exactly one of CC or C′C'. The goal is to minimize the maximal teaching set size in order to separate each pair of concepts. The classic and parameterized complexity of the problem is well-understood. This paper is the first which initiates the study of approximation algorithms for this problem. To this end, a maximization variant is introduced: With a given value kk, for each concept CC compute a teaching set T(C)T(C) of CC of size at most kk such that the number of separated concept classes is maximized. The corresponding problem is MNCT. Moreover, a variant with T(C)⊆CT(C)\subseteq C, MNCT^+, is studied as well (which aligns with existing works on parameterized complexity). The main results are (1) polynomial a polynomial time (tight) 3/4 approximation algorithm for both problems if kk is a constant, (2) APX-hardness for MNCT^+ for k=1k=1, (3) a sharp distinction of the weighted and unweighted case, and (4) polynomial time solvable special cases.

Judgement.

Due to receiving the review invitation quite late I didn't check all proofs in detail but I believe that the results are correct. The results are interesting, for example the tight 3/4 approximation for MNCT^+. My main issue is the practical relevance of the problem which is not clear to me. Thus, I recommend a weak reject.

Critical strengths
  • initializing the study of approximation algorithm for this problem in algorithmically interesting

  • the results are interesting and show provide a clear border what is possible and what is not, for example: For MNCT^+ with general k, the picture is asymptotically tight.

Critical weaknesses
  • the motivation of the problem is quite vague and i don't think the developed algorithms will be of direct practical help

  • the results are not too interesting from a technical point of view

  • I believe the randomized rounding is quite similar to existing problems where randomized rounding was useful, so a citation could be used

Questions for authors

Q1: You considered the number of separated pairs as a measure which gets approximated. What about the dual: the number of non-separated pairs? I guess this is not possible due to the existing NP-hardness for k=1k=1? What about special cases?

Q2: In line 262: why do you choose sets of size at most κj\kappa_j here and not sets of size exactly κj\kappa_j? This also concerns line 285 where the slot capacities do not sum up to kk, if the formulation 'at most' is intended.

Q3: What is the (practical) motivation for the results presented in Section 6? What are application in which these algorithms might be helpful?

Q4: Is there any hope that the positive results presented in Section 6 also transfer to MNCT?

Q5: Can Theorem 6.4 also be adapted to the case where each weight is strictly positive?

Q6: in line 660: I don't understand why now the statement of the lemma follows. Please explain this.

Q7: From a practical motivation: The initial goal was to separate all concepts. In this maximization setting, a pair of concepts might not be separated. How would the learner deal with this case? It could also be that the number of concepts which can be correctly identifed is a better measure.

Q8: Is unweighted MNCT or MNCT^+ APX-hard for fixed kk (for example k=1k = 1)? If not, can you rule out a PTAS?

Q9: Can Theorem 6.4 be strengthened to APX-hardness via Maximum Independent Set on bounded-degree graphs?

Further Comments:

  • in the appendix: specify what rr is (also l132)

  • l46: here already refer to the figure with the example

  • l48: here, already provide an informal description

  • l48: initially I wondered whether T(C)⊆CT(C)\subseteq C has to hold; this was only specified later

  • l70: separate the refs

  • l72: give a concrete ref for NP-hardness

  • l134: which guarantee?

  • l150: strange sentence: The input explicitly specifies which examples belong to each target.

  • l153: what does this mean? positive if contained in TT, and negative otherwise?

  • l170: I think it should be k<∣X∣k<|X| and k≥∣X∣k\geq |X|

  • l236: notation clash of a and b with the statement of Lemma 3.3. Moreover the notation [0,k] is not defined and leads to confusion with [0,1]

  • l341: provide a bit more details

  • l354: make it more clear that you use Max k Cover to obtain the result and also state the approx lower bound for it here

  • l358: currently, only the construction is presented. I think some intuition for it would be helpful and why the two problems are 'related'. Moreover, some intuition on the correctness would be helpful

  • l369: bring this sentence after the next paragraph: without any introduction the reader does not know what this figure is about

  • l416: add a short intuition on the correctness

  • l429: the term 'adding a positive example' is quite vague: it becomes only clear in the proof. Restate this

  • l438: here, a figure would be helpful

  • l648: here, a figure would be helpful

  • l772: here, a figure would be helpful

Reviewer_7qtcOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

Given a finite set of examples and a collection of target concepts (where an example may belong to multiple concepts), the paper studies the problem of selecting at most kk teaching examples per target so as to maximize the number of separated pairs of target concepts. Here, two targets are considered separated if at least one example selected for either target belongs to one concept but not the other. The authors study two variants, MNCT and MNCT+, depending on whether both positive and negative examples can be selected for a target, or only positive examples.

The authors observe that the problem is closely related to Maximum Coverage under a partition matroid constraint, immediately giving a 1−1/e1-1/e approximation using standard techniques. Their main contribution is showing an improved approximation by exploiting additional structure, namely that each pair of targets can only be separated by examples selected for one of the two targets in that pair.

They build up to this as follows. First, they construct a coverage-style LP relaxation and show that standard randomized rounding gives a 3/43/4-approximation for budget k=1k=1, with the approximation ratio gradually approaching 1−1/e1-1/e as kk increases. They next show that a configuration-based rounding strategy can improve the approximation ratio for larger kk. This comes at the cost of a blowup in the LP size of ∣X∣O(r)|X|^{O(r)}, where XX is the set of examples and rr is the configuration size. Setting r=kr=k yields a 3/43/4-approximation for every fixed kk, while smaller values of rr give a tradeoff between running time and approximation quality.

The authors also present several other results, including derandomization of their algorithms and extension of the guarantees to weighted versions. They further give hardness results, including a 1−1/e1-1/e inapproximability threshold for MNCT+ when kk is part of the input, as well as exact polynomial-time algorithms for some special cases, including size-two targets and laminar concept classes.

Critical strengths
  1. The paper is quite well-written.

  2. The general problem of choosing the most informative subset of training examples within a given budget is highly relevant.

Critical weaknesses
  1. Limited Technical Novelty: The connection to Maximum Coverage and the initial LP-rounding approach are fairly straightforward. The main technical novelty is exploiting the observation that each pair of targets can only be separated by examples selected for one of its two targets, but this seems relatively modest, as the resulting analysis closely resembles standard MAX-2-SAT rounding arguments.

  2. Limited Significance: Their main algorithmic result, giving a 3/43/4 approximation, requires treating kk as a constant; otherwise, the running time has an exponential dependence on kk. While smaller configuration sizes give polynomial-time algorithms, their approximation guarantees approach the standard 1−1/e1-1/e bound as kk increases. In this setting, assuming kk to be a small constant seems somewhat restrictive, since the teaching budget is itself an important input parameter.

Questions for authors

Please address W1 and W2.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.