- 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 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 -approximation for every fixed , 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
-
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.
-
The explicit 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
-
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 -approximation algorithm takes time, apart from polynomial factors, so its cost can grow quickly with the budget.
-
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.
-
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 is optimal for unweighted instances with fixed . 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
-
Can the dependence on be improved while retaining an approximation ratio close to ?
-
Integrality gap suggests the proposed LP method won't improve the bound, but is there any generic lower bound for the problem?