- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies dynamic optimal transport (OT) and proposes a deterministic data structure, called the Bi-resolution Matrix Decomposition Tree (BMD Tree), to accelerate the Network Simplex algorithm. The proposed method aims to reduce the worst-case reduced-cost maintenance time per simplex iteration from O(n^2) to O(n). However, I cannot ensure the correctness of the proof.
Critical strengths
- The proposed method aims to provide a worst-case O(n) bound per simplex iteration, though I do not ensure the correctness of the proof.
- The experiments demonstrate the improvements over existing DOT methods across multiple datasets.
Critical weaknesses
- The worst-case complexity proof requires stronger justification.
- The worst-case scenario in the experiment was not reported.
Questions for authors
- Does the proof of Theorem 3.3 still hold for the dynamically changing block sizes?
- What was the worst case in the experiment?
4 comments
Thank you again for your time and consideration, and we would welcome any further feedback you may wish to share as the discussion period draws to a close.
Thank you for clarifying the proof and adding the timing results. I am still unsure how the required partition alignment is maintained throughout a simplex iteration, so I am keeping my rating.
Additional response to Reviewer Xyqb
Thank you for reading our earlier explanation and the additional timing results so carefully, and for continuing the discussion with us. We appreciate the opportunity to clarify how the partitions remain aligned throughout a simplex iteration.
Proposition 2.1 shows that there always exists an optimal transport plan whose positive-flow edges lie on a spanning tree (p. 3, proof in Appendix D). During a simplex iteration, the rows and columns of the reduced-cost matrix are indexed by the Euler tour sequence of the spanning tree representing the current transport plan. Section 3.1 explains how cutting and linking tree edges translates into splitting and reassembling this matrix (p. 6, lines 286–310). As Figure 1 illustrates, cutting a tree edge separates the tree into and and gives four submatrices of the same . Each row cut passes through all corresponding columns at the same row boundary, and each column cut passes through all corresponding rows at the same column boundary. The resulting submatrices therefore inherit the partition of their shared dimension.
For example, and contain different columns but inherit the same rows from . Suppose rows 1–4 and 5–8 form two adjacent intervals at one level. If a local repair merges them, we make that decision once for the shared row sequence and carry out the same merge in both matrices. Both then have rows 1–8 as a single interval at that level, so their row boundaries still match when they are joined side by side. The same rule preserves column boundaries for a vertical merge (Appendix I, p. 27, lines 1435–1453). A numerical update can change the reduced costs in while leaving those in unchanged. It leaves the hierarchical partitions of both matrices intact (Section 3.1, p. 6, lines 312–318).
The cost of applying the repair to all corresponding blocks is included in the analysis. At each level, only a constant number of intervals change along the dimension being repaired. Along the other dimension, the intervals span a total length of . Combining this fact with the interval-length bounds limits the number of affected blocks at each level. Summing their maintenance costs over all levels gives the bound (Appendix K.1, pp. 29–30, lines 1565–1582).
We hope this clarifies how alignment is preserved at each step. If it addresses your remaining concern, we would be grateful if you would consider revisiting your assessment.
Response to Reviewer Xyqb
We thank you for carefully reviewing our manuscript and for your constructive comments. Below, we clarify the analysis and summarize the additional experimental results.
1. Dynamic block sizes and Theorem 3.3
Theorem 3.3 remains valid when actual block lengths change. The key is that standard block lengths are determined globally by the input size and the hierarchy level, rather than recalculated from an individual parent's actual length. At level ℓ, the standard scale is kℓ=n2−ℓ. Splitting or merging a parent therefore does not change the standard lengths used for its children.
Under the maintained block-size invariants, the number of child blocks within each parent block is bounded by a constant multiple of the corresponding count in the idealized, equal-length decomposition. The same comparison applies to local maintenance work. Thus, unequal actual lengths do not invalidate the standard recurrence as the basis of the analysis. More precisely, we compare total work at each level: O(n/kℓ) affected grand blocks each require O(kℓ2/3) non-recursive work, giving O(nkℓ−1/3) for that level. The comparison constants are independent of depth, so they are not multiplied through recursive calls. Summing over all levels, including the base level, preserves the O(n) worst-case reduced-cost maintenance bound per simplex iteration.
To make the role of fixed standard scales in the complexity analysis explicit, we have added the following explanations to the revised manuscript:
2. Observed maximum update times
We have added measurements of observed maximum update times, P99, and memory usage in Appendix L.4 (Figs. 16–17), comparing BMD Tree with our principal dynamic baseline, the Skip List (Xu and Ding, 2024), on three-dimensional synthetic instances with 1,000–10,000 points per side.
BMD Tree has lower observed maximum update times for both update types at every tested size. At 10,000 points per side, the maximum position-modification time is 51.63 s for BMD Tree versus 136.78 s for Skip List, corresponding to a 2.65-fold speedup. The maximum weight-modification time is 41.11 s versus 97.48 s, a 2.37-fold speedup. P99 denotes the 99th percentile of measured update times for each update type and size: at least 99% of the recorded updates finish within this time. The P99 values show the same advantage: 48.40 s versus 101.96 s for position modifications, and 34.32 s versus 87.03 s for weight modifications.
We also measured peak resident set size (RSS), the maximum amount of physical memory used by the process. The largest peak RSS across the tested sizes is 19.25 GiB for BMD Tree and 56.62 GiB for Skip List, both occurring at 10,000 points per side. BMD Tree therefore uses approximately 66% less peak memory at this scale. These results indicate that its practical advantages extend beyond average runtime to lower observed maximum update times and a smaller peak memory footprint at the largest tested size.
Thank you again for your careful review and helpful suggestions. We hope these explanations and additional results address your concerns, and we would welcome your further feedback.