- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies offline interval scheduling, where each request belongs to a group, occupies a fixed time window, and competes with overlapping requests for exclusive access to a resource. This paper characterizes the optimal worst-case trade-off between fairness and throughput and establishes a matching lower bound, proving that this trade-off is optimal. This paper also develops deterministic algorithms that guarantee each group a proportional share of its standalone optimum, rounded down to an integer, and algorithms were evaluated on workload-derived instances.
Critical strengths
The motivation is clear, the theoretical results are strong, and the empirical evaluation is good.
Critical weaknesses
-
This is a classical scheduling/operations-research paper. It does not study representation learning, deep learning, or core machine learning. While ICLR accepts theory, the topic and techniques are far from the typical ICLR audience.
-
For ex post result, although the bound is tight for , there exist a gap for general number of groups.
-
The claim on the difference with Bhore et al. (2021) is unclear. They study the independent set in interval graphs, with color, which is the same as the setting in this paper. The main difference should be the fairness concept, however, the paper does not clarify this well in related work.
Monor:
The conclusion section is missing.
Questions for authors
How is this paper related to representation learning, deep learning, or core machine learning?
3 comments
Thank you for the response. I am raising my score, even though I am not sure whether this paper is within the scope of ICLR.
Dear Reviewer,
Thank you for reconsidering your evaluation in light of our response. We are pleased that our clarifications have been helpful and appreciate your willingness to increase your score.
Thank you again for your constructive feedback and positive assessment of our work.
Response to Reviewer NWFY on Relevance to ICLR, Deterministic Guarantees, and Relation to Bhore et al.
Thank you for the careful review and for highlighting the motivation, theoretical results, and empirical evaluation. We appreciate the opportunity to clarify the connection to ICLR and to explain how our fairness criterion relates to prior work.
W1/Q1. Relevance to ICLR. Our connection to deep learning is through the shared infrastructure used to train models. When several teams request fixed windows on a shared GPU server, the scheduler must decide which reservations to admit and how much access to guarantee each team. Systems such as Themis and Gavel motivate this question by studying fairness and efficiency in scheduling ML workloads (Section 1). Our paper isolates the fixed-reservation admission problem and gives a tight bound on how much throughput can be retained while guaranteeing each group an expected share of its standalone service (in a randomized setting). This connects to fairness, optimization, and infrastructure, all listed in the ICLR 2027 Call for Papers. Section 2 also discusses related fair-scheduling work at ICLR (Zhao et al., 2025) and NeurIPS (Li et al., 2021).
W2. Deterministic guarantees for more than two groups. We agree that the optimal guarantee for rounded quotas remains open for general k. Theorem 5.1 gives the tight result for two groups. For k≥3 and α=k, BPA achieves an approximation ratio of at most min(Δ,(3k−3)/2), and Appendix A.5 gives lower bounds that can leave a gap. In our workload experiments at k=10, BPA's and GPSA's mean approximation ratios are within 0.01 under each of the three original assignments (Table 7). For fairness in expectation, Theorem 4.1 gives matching worst-case bounds for every k.
W3. Relation to Bhore et al. (2021). We agree that the two papers share the same interval-selection structure and that the distinction is in the fairness criterion. Bhore et al. ask whether an independent set can contain a prescribed, equal number of intervals from each color. The main difference is that we set each group's target using its standalone optimum, OPTg. The target is OPTg/α in expectation or ⌊OPTg/α⌋ in every output. This formulation lets us ask how much of the unrestricted throughput can be retained while meeting those targets (Sections 2, 4, and 5). Appendix A.7 adapts their dynamic program to maximize throughput subject to unequal quotas.
The missing Conclusion section. Thank you for pointing out the missing conclusion. We added Section 7 to summarize the main results and identify the remaining open questions.