- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies the tradeoff between coordination (i.e. the extent to which similar entities are rounded together) and stability (i.e. worst-case variance of linear statistics with bounded coefficients) in randomized rounding. The setup specifies a weighted coordination graph in which high-weight edges correspond to pairs whose roundings should agree, and the coordination level of a rounding scheme is measured by the frequency with which such pairs disagree above the smallest possible baseline, a metric denoted as "excess." Within this framework, the authors (1) characterize the best achievable stability under zero excess for -cycle coordination graphs () up to constant factors, (2) show that when excess is non-zero, optimal stability on a cycle depends on global coordination graph structure, (3) provide a lower bound on zero-excess stability for general graphs via a decomposition into connected components, and (4) give two rounding scheme implementations for which coordination and stability bounds are computable a priori.
Critical strengths
• The paper exactly characterizes optimal zero-excess stability on cycles up to constant factors.
Critical weaknesses
• Positioning. The paper does not clearly distinguish its setup and results from the existing literature on randomized rounding schemes, making it difficult to assess novelty. For example, the discussion of dependent rounding is limited to Yamin et al. (2025) despite extensive prior work on preserving marginals while satisfying combinatorial constraints and/or controlling correlations. Moreover, the design choices/metrics considered (e.g. weighted coordination graph for coordination, variance of bounded linear aggregates for stability) are presented without motivation or relationship to prior work.
• Scope. Per the intro, the goal of the paper is "...to characterize the best attainable trade-off between local coordination and aggregate stability..." in dependent rounding. However, the main results are much narrower in scope: Theorem 1 only characterizes one endpoint of the Pareto frontier (zero excess) for a restricted class of coordination graphs (-cycles), the lower bound for general graphs only applies to zero excess, and Theorem 2 expands the characterization to non-zero excess for only two particular cycle constructions. Without motivation for why zero excess is an important regime in real applications, the significance of these results is unclear.
Questions for authors
• In what sense do these results characterize the general tradeoff between coordination and stability in randomized rounding? Is the goal of this paper to initiate its study rather than characterize the full tradeoff? Beyond its mathematical structure, is the endpoint that is primarily considered (exact zero excess) an interesting regime operationally?
• Which aspects of the setup and results are new relative to prior work on randomized rounding? Do practical settings motivate this particular combination of graph disagreement and worst-case variance as the design objective?