acceptodds
Under review as a conference paper at ICLR 2027

Beating the Worst-Case Per-Iteration Update Time: A Novel Dynamic Network Simplex Method for Optimal Transport

Abstract

Optimal Transport is widely applied in fields such as computer vision, machine learning, and operations research. It seeks a minimum-cost transport plan from source to target domain under supply and demand constraints. However, optimal transport problems in dynamic scenarios face the challenge of high complexity in real-time adjustments to transport plans. To overcome this computational barrier, we aim to develop an efficient dynamic algorithm for the seminal Network Simplex method. We find the primary difficulty lies in the rapid and effective maintenance of the reduced cost matrix, with up to entries (”” is the number of input points). To address this, we propose a novel “Bi-resolution Matrix Decomposition Tree” technique for maintaining matrix operations. By indexing the reduced cost matrix with Euler tour sequences and maintaining a hierarchical bi-resolution block decomposition, it reduces the worst-case time per simplex iteration to . Finally, we demonstrate our method's effectiveness through experiments on synthetic and real-world datasets.

Primary area:
optimization
Keywords:
Optimal Transport, Dynamic Optimal Transport, Network Simplex, Dynamic Data Structures

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_XyqbOpenReview ↗
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
  1. 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.
  2. The experiments demonstrate the improvements over existing DOT methods across multiple datasets.
Critical weaknesses
  1. The worst-case complexity proof requires stronger justification.
  2. The worst-case scenario in the experiment was not reported.
Questions for authors
  1. Does the proof of Theorem 3.3 still hold for the dynamically changing block sizes?
  2. What was the worst case in the experiment?
4 comments
AuthorsOpenReview ↗

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 ℓ\ell, the standard scale is kℓ=n2−ℓk_\ell=n^{2^{-\ell}}. 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ℓ)O(n/k_\ell) affected grand blocks each require O(kℓ2/3)O(k_\ell^{2/3}) non-recursive work, giving O(nkℓ−1/3)O(nk_\ell^{-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)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:

  • Section 3.3, p. 9, lines 432–449: We have distinguished standard scales from actual block lengths and explained the uniform per-level comparison.
  • Appendix H.2, pp. 24–25, lines 1259–1302: We have defined the fixed global scales and derived block-count bounds under the maintained interval conditions.
  • Appendix J, p. 29, lines 1525–1531 and 1543–1546: We have explained why unequal block lengths preserve the local counting bounds and how repair scans, tag propagation, and minimum recomputation are charged.
  • Appendix K.1, pp. 29–30, lines 1552–1582: We have distinguished the standard-model recurrence from the accounting for the actual structure and established a per-level comparison with depth-independent constants.

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.

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.

AuthorsOpenReview ↗

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 Γ\Gamma 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 T1T_1 and T2T_2 and gives four submatrices of the same Γ\Gamma. 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, Γ11\Gamma_{11} and Γ12\Gamma_{12} contain different columns but inherit the same rows from T1T_1. 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 Γ12\Gamma_{12} while leaving those in Γ11\Gamma_{11} 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 O(n)O(n). 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 O(n)O(n) 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.

Reviewer_12GXOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper introduces a Bi-resolution Matrix Decomposition Tree for dynamic optimal transport. It combines Euler-tour indexing with hierarchical block maintenance and claims a deterministic O(n)O(n) worst-case cost per network simplex iteration. Experiments compare it with static and dynamic solvers on synthetic data, MNIST, and CIFAR-10.

Critical strengths

The intermediate block level is a useful design for reducing maintenance costs. A deterministic linear bound would improve on the expected-time guarantee of the previous randomized approach. The experiments include the closely related Skip Orthogonal Lists baseline and show consistent runtime gains over the exact solvers tested.

Critical weaknesses

The connection between the complexity analysis and the dynamically maintained structure needs clarification. Section 3.3 explains the bound using an idealized decomposition, whereas the algorithm also adjusts block sizes during updates. I would like a clearer explanation of how these adjustments fit within the claimed worst-case bound, since this guarantee is the main contribution.

The experiments show faster updates, but provide limited evidence about where the gains come from. Figure 12 reports iteration counts for the proposed method; corresponding counts and per-pivot timings for Skip Orthogonal Lists would make the comparison more informative. The update magnitudes and timing boundaries also need clearer reporting. Lower runtime variance alone does not establish that randomization explains the difference.

Questions for authors

How are dynamic block-size adjustments accounted for in the worst-case complexity analysis? For position modifications, how are changes to the affected cost-matrix row or column handled, and is this work included in the reported runtime? Can you provide per-pivot timings and pivot counts for both dynamic methods on identical update sequences, along with peak memory usage?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 12GX(Part1)

We thank you for your careful review and constructive comments. We appreciate your recognition of the intermediate block layer and the value of a deterministic complexity guarantee. We address your questions below.

1. Dynamic block-size maintenance

The O(n)O(n) bound includes block-size maintenance. Standard lengths are determined globally by the input size and hierarchy level; changing a parent's actual length does not change its children's standard lengths. Under the maintained invariants, each parent's child-block count is bounded by a constant multiple of the corresponding count in the equal-length decomposition. Repairs regroup intact children within a constant number of neighboring intervals at each scale, reusing their internal structures. Child scans, tag propagation, and minimum recomputation are charged at the level where they occur.

At level ℓ\ell, the standard scale is kℓ=n2−ℓk_\ell=n^{2^{-\ell}}. The total non-recursive work is O((n/kℓ)kℓ2/3)=O(nkℓ−1/3)O((n/k_\ell)k_\ell^{2/3})=O(nk_\ell^{-1/3}). The constants are independent of depth, so summing the costs over all levels, including the base level, gives O(n)O(n) without multiplying repair constants recursively.

To show how dynamic repairs are included in the complexity bound, we have clarified the accounting in the following passages:

  • Section 3.3, p. 9, lines 432–449: We have clarified the fixed standard scales and compared the work of the actual structure with that of the standard model.
  • Lemma H.4 and the following accounting, pp. 25–27, lines 1313–1423: We have explained how repairs reuse intact children, remain local, and incur the stated maintenance costs.
  • Appendix J, p. 29, lines 1516–1546: We have provided the local block-count analysis and explained how repair scans, tag propagation, and minimum recomputation are charged.
  • Appendix K.1, pp. 29–30, lines 1565–1582: We have presented the level-wise accounting and shown that its comparison constants are independent of depth.

2. Position modifications and timing

Moving a source point changes one cost row; moving a sink point changes one cost column. We recompute the affected distances and maintain the corresponding reduced-cost entries. Throughout the experiments reported in the paper, position-modification timings include both distance recomputation and the corresponding reduced-cost maintenance.

To make the scope of the reported timings clear, we have specified the inclusion of cost refreshes in the following caption:

  • Appendix L.4, Figure 17 caption, p. 38, lines 2030–2036: We have specified that update timings include cost refreshes and clarified the timing boundaries.
AuthorsOpenReview ↗

Response to Reviewer 12GX(Part2)

3. Paired profiling and peak memory

We have added measurements in Appendix L.4 (Figs. 16–17), comparing BMD Tree with our principal dynamic baseline, the Skip List (Xu and Ding, 2024), on identical inputs and update sequences with 1,000–10,000 points per side.

We measured peak resident set size (RSS), the maximum amount of physical memory used by the process. At 10,000 points per side, peak RSS is 19.25 GiB for BMD Tree versus 56.62 GiB for Skip List, approximately 66% lower. Maximum position-modification times are 51.63 s versus 136.78 s, a 2.65-fold speedup; maximum weight-modification times are 41.11 s versus 97.48 s, a 2.37-fold speedup. P99 denotes the 99th percentile: at least 99% of recorded updates of the given type and size finish within this time. Position-modification P99 is 48.40 s versus 101.96 s; weight-modification P99 is 34.32 s versus 87.03 s. These results show lower observed maximum update times and lower peak memory usage at this scale. Peak RSS covers the full process, including initialization and the initial and final solution checks.

We have also clarified which stages are covered by the peak-memory measurement in the figure caption:

  • Appendix L.4, Figure 16 caption, p. 37, lines 1970–1974: We have clarified which stages are included in the peak-RSS measurement.

The pivots referred to in your review correspond to the simplex iterations in our manuscript. Both methods build on the same network simplex framework. BMD Tree changes reduced-cost maintenance within each simplex iteration rather than introducing a new strategy to reduce the number of iterations. With the same initial basis, entering- and leaving-arc rules, and tie-breaking convention, replacing the maintenance data structure preserves the iteration sequence and hence the iteration count. Our theoretical improvement concerns the maintenance cost of each iteration.

4. Runtime variance

To address this point, we would like to clarify that both methods use the same network simplex framework and update procedures. The difference addressed in our work is reduced-cost maintenance: Skip List uses a randomized structure with expected O(n)O(n) maintenance time per iteration, but its worst-case time is O(n2)O(n^2). In contrast, BMD Tree uses a deterministic structure and guarantees O(n)O(n) reduced-cost maintenance time per iteration even in the worst case.

Although the number of simplex iterations can vary across updates and affect their total running times, BMD Tree still shows lower runtime variance in our experiments. This result provides empirical support for a stability benefit from derandomizing reduced-cost maintenance on the tested instances.

Thank you again for your helpful suggestions. We hope these explanations and additional results address your concerns, and we welcome your further feedback.

Thanks for the clear explanation and the new results, which address my main concerns, so I will raise my score.

Thank you for your positive reassessment and for acknowledging our efforts to address your concerns through the clarifications and additional results.

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

This paper aims to solve the high per-iteration cost of maintaining exact optimal transport solutions after changes to point positions or marginal weights. Specifically, the authors propose a Bi-resolution Matrix Decomposition Tree that combines Euler-tour indexing with hierarchical block maintenance to support efficient matrix splitting and merging, and lazy additive updates with cached minima to achieve a claimed linear worst-case maintenance cost per simplex iteration. Experiments on Gaussian point sets, MNIST, CIFAR-10, and dynamic bichromatic matching report lower average update runtimes than static exact solvers and the dynamic Skip Orthogonal List baseline, with competitive performance against approximate methods in several settings.

Critical strengths
  1. I think the problem studied in this paper is interesting and valuable.

  2. The proposed algorithm can ensure good performance in terms of computational cost in the worst case. By combining with Euler-tour indexing and lazy propagation, it provides a concrete data-structure contribution.

Critical weaknesses
  1. Algorithm 3 details splitting, while merging is described as analogous.

  2. The authors should consider maintenance, such as position changes and distance computation, in timings.

  3. The authors assume evenly sized blocks in their proof, which should be clearly illustrated.

Questions for authors

see above

3 comments
AuthorsOpenReview ↗

Response to Reviewer GQV4(Part1)

We sincerely thank you for your careful review, your recognition of our contribution, and your constructive suggestions. We appreciate your positive assessment of the value of deterministic guarantees for dynamic exact OT.

1. MERGE alignment and maintenance

The key is that the two input matrices share the same hierarchical partition along their common dimension. For a horizontal MERGE, both inputs have the same row sequence and identical row partitions at every level. For example, a row interval covering rows 1–4 in one input also covers rows 1–4 in the other. Vertical MERGE is symmetric. Subsequent changes to a shared partition follow one coordinated plan across the corresponding matrix blocks. Thus, the partitions along the shared dimension remain aligned throughout these operations.

The inputs retain separate lazy tags and recorded minima. Before reassigning children, each parent's tag is propagated to all its direct children. Intact subtrees retain their internal tags. A new parent's tag is set to zero, and its minimum is recomputed from its children's recorded minima plus their tags. This preserves entry values and an attaining index pair.

Seam repair regroups intact children along existing child boundaries and affects only a constant number of neighboring intervals at each scale. Scans, tag propagation, and minimum recomputation are included in the maintenance accounting. At the standard scale kℓ=n2−ℓk_\ell=n^{2^{-\ell}}, the level-wise cost is O(nkℓ−1/3)O(nk_\ell^{-1/3}), with depth-independent constants; summing the costs over all levels, including the base level, gives O(n)O(n) per structural operation.

To make the input requirements and their maintenance explicit, we have clarified the MERGE definition and detailed the procedure in the following locations:

  • Section 3.1, p. 6, line 323 (MERGE definition): We have made the shared-partition requirement explicit in the MERGE definition.
  • Appendix I, pp. 27–29, lines 1435–1457 and 1500–1513: We have provided the MERGE steps and their correctness and cost analyses.
  • Lemma H.4 and the following accounting, pp. 25–27, lines 1313–1423: We have described local repair and the reuse of intact children.
  • Appendices J and K.1, pp. 29–30, lines 1516–1546 and 1565–1582: We have detailed the local costs and the level-wise charging argument.

2. Space complexity and peak memory

The data structure uses O(n2)O(n^2) words of storage, including the dense matrix entries, hierarchy nodes, lazy tags, recorded minima, and parent–child references.

In response to your question about storage requirements, we have added an explicit space bound and its proof:

  • Theorem 3.4, p. 9, lines 450–453: We have stated the space bound for the data structure.
  • Appendix K.2, pp. 31–32, lines 1653–1683: We have provided a proof of the space bound.

We have also added peak-memory measurements in Appendix L.4, Fig. 16, comparing BMD Tree with our principal dynamic baseline, the Skip List (Xu and Ding, 2024). We measured peak resident set size (RSS), the maximum amount of physical memory used by the process. At 10,000 points per side, their peak RSS values are 19.25 GiB and 56.62 GiB, respectively: approximately 66% less for BMD Tree. These measurements show a smaller peak memory footprint at this scale despite the same asymptotic space order.

AuthorsOpenReview ↗

Response to Reviewer GQV4(Part2)

3. Structure initialization and timing

Structure initialization means constructing the Euler-tour indexing, block hierarchy, lazy tags, and recorded minima from a given initial transportation plan and its tree basis. Computing that initial plan is a separate preprocessing task and can use an existing OT solver; it is not part of the structure-building task itself.

For clarity, Fig. 16 reports initialization times, including initial optimization and structure construction: 52.80 s for BMD Tree and 145.58 s for Skip List at 10,000 points per side. These are not isolated structure-building times.

To distinguish structure building from the initialization time reported in Fig. 16, we have stated the timing scope in the following caption:

  • Appendix L.4, Figure 16 caption, p. 37, lines 1970–1974: We have specified the measurement scopes for initialization time and peak RSS.

4. Distance computation and cost maintenance

Yes. Distances define the entries of the cost matrix. Moving a source point requires refreshing one cost row; moving a sink point requires refreshing one cost column. Position-modification timings throughout the paper include recomputing these distances and maintaining the corresponding reduced costs. Distance evaluation depends on the metric and dimension; the BMD Tree maintenance analysis concerns the resulting numerical entries.

The caption for the update-time measurements also specifies that refreshing the affected cost entries is included in the reported times:

  • Appendix L.4, Figure 17 caption, p. 38, lines 2030–2036: We have clarified that update timings include cost refreshes and have specified the timing boundaries.

Thank you again for your thoughtful suggestions and recognition of our work. We hope these explanations and additions address your concerns, and we would welcome your further feedback.

AuthorsOpenReview ↗

Additional response to Reviewer GQV4(W3)

Thank you for raising the equal-block-size issue in the third point of your updated review. We would like to clarify that the equal-length decomposition is used to introduce the recurrence, while the dynamically maintained blocks may have unequal actual lengths. The revised analysis explicitly accounts for this difference.

The key is that standard block lengths are determined by the fixed global input size and the hierarchy level. At level ℓ\ell, the standard scale is kℓ=n2−ℓk_\ell=n^{2^{-\ell}}. Splitting or merging a parent does not redefine the standard lengths of its children. Under the maintained interval-length conditions, each parent's child-block count is bounded by a constant multiple of the corresponding count in the equal-length decomposition.

To obtain the total complexity bound, we compare the work at each entire level. At level ℓ\ell, at most O(n/kℓ)O(n/k_\ell) grand blocks are processed, each requiring O(kℓ2/3)O(k_\ell^{2/3}) non-recursive work, giving O(nkℓ−1/3)O(nk_\ell^{-1/3}) in total. The comparison constants are independent of recursion depth, so they are not multiplied through recursive calls. Summing the costs over all levels, including the base level, preserves the O(n)O(n) worst-case reduced-cost maintenance bound per simplex iteration.

We have made these points explicit in the revised manuscript:

  • Section 3.3, p. 9, lines 432–449: We distinguish standard block lengths from actual lengths and explain how the equal-length model is related to the actual structure.
  • Appendix H.2, pp. 24–25, lines 1259–1302: We state the interval-length conditions and derive the block-count bounds allowing unequal actual lengths.
  • Appendix K.1, pp. 29–30, lines 1552–1582: We present the standard-model recurrence and the level-by-level comparison with depth-independent constants.

Thank you again for the opportunity to clarify this part of the analysis.

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

The paper presents a focused technical design for the matrix-maintenance bottleneck in dynamic exact OT. Figures 1 and 2 clearly connect tree cuts to matrix blocks and illustrate how the intermediate resolution balances maintenance costs, providing an intuitive complexity rationale for ρ=2/3\rho=2/3. The experiments include relevant baselines, particularly the closely related Skip Orthogonal List and ICML 20252025 EUCLMATCH, and reach 4000040000 points on synthetic data and 2000020000 on MNIST/CIFAR-10. Each size includes 1010 instances, with absolute runtimes, standard deviations, and iteration counts reported in the appendix. The discussion of applicability is also measured: Figures 13 to 15 show that EUCLMATCH is faster for low-dimensional approximate matching, while BMD is more favorable in high-dimensional settings requiring exact solutions. The authors acknowledge that degenerate iterations and overall iteration bounds remain unresolved.

Critical strengths

The paper presents a focused technical design for the matrix-maintenance bottleneck in dynamic exact OT. Figures 1 and 2 clearly connect tree cuts to matrix blocks and illustrate how the intermediate resolution balances maintenance costs, providing an intuitive complexity rationale for ρ=2/3\rho=2/3. The experiments include relevant baselines, particularly the closely related Skip Orthogonal List and ICML 20252025 EUCLMATCH [2], and reach 40,00040{,}000 points on synthetic data and 20,00020{,}000 on MNIST/CIFAR-10. Each size includes 1010 instances, with absolute runtimes, standard deviations, and iteration counts reported in the appendix. The discussion of applicability is also measured: Figures 13 to 15 show that EUCLMATCH is faster for low-dimensional approximate matching, while BMD is more favorable in high-dimensional settings requiring exact solutions. The authors acknowledge that degenerate iterations and overall iteration bounds remain unresolved.

Critical weaknesses

The main concern is that the claimed worst-case O(n)O(n) maintenance bound is not fully justified for unequal blocks and local repairs. Appendix H.2's O(k)O(\sqrt{k}) block-count bound does not directly establish the idealized recurrence in Appendix K; recursive constants may accumulate across levels, requiring a complete charging argument. MERGE also needs clearer specification of partition alignment, tag propagation, and additional splits. These are substantial proof gaps, although they do not establish that the algorithm is incorrect. Experimentally, average speedups and latency standard deviations do not establish worst-case update latency when iteration counts vary. The Sinkhorn comparison needs objective errors, marginal residuals, and stopping criteria to support evaluation at matched accuracy. Unreported space, initialization, cost-matrix update, and placeholder-pool expansion costs further limit assessment of end-to-end efficiency and scalability.

Questions for authors

There is some minor concerns:

  • Could you provide a complete linear charging argument covering unequal rectangular blocks, local repairs, and arbitrary valid MERGE sequences, with explicit recursive-call counts and maintenance invariants?
  • How is the strongly feasible tree in Appendix G initialized with zero-mass placeholders? Under the stated residual-network definition, every reverse capacity of a zero-mass target is zero. How can multiple such targets satisfy the requirement to send positive infinitesimal flow toward a single root?
  • Under identical update sequences and pivot/tie-breaking rules, how do BMD and Skip Orthogonal List compare in maximum per-iteration latency, P99 latency, visited-node counts, and total update time? Could you include update sequences designed to trigger boundary repairs?
  • Please report the space bound, peak memory, initialization and cost-matrix update costs, and runtimes at matched accuracy. Which baseline, problem size, and accuracy settings underlie the approximately 200×200\times speedup discussed around Figure 14?
3 comments
AuthorsOpenReview ↗

Response to Reviewer aZfd(Part1)

We thank you for your careful review and constructive comments, and for recognizing the intermediate-resolution design and practical relevance of dynamic exact OT.

1. Unequal blocks, local repair, and MERGE

The standard scale kℓ=n2−ℓk_\ell=n^{2^{-\ell}} is globally fixed; changing a parent's actual length does not change its children's standard lengths. Each parent's child-block count is bounded by a constant multiple of the corresponding count in the equal-length decomposition. The interval bound q≤2L/S+1q\le2L/S+1, applied separately in both dimensions, also covers rectangular blocks. Here, qq is the number of intervals in a sequence of total length LL, and SS is the standard interval length at the scale under consideration.

At level ℓ\ell, at most C0n/kℓC_0n/k_\ell grand blocks are processed, with total non-recursive work at most C1nkℓ−1/3C_1nk_\ell^{-1/3}. The constants are independent of depth and prior legal operations. Local repairs regroup intact children within a constant number of neighboring intervals, without additional downward splitting except constant-size reconstruction. Scans, tags, and minimum recomputation are included in the accounting. Summing the costs over all levels, including the base level, gives O(n)O(n) without recursively multiplying constants.

During MERGE, the inputs share the hierarchical partition of their common dimension, and subsequent partition changes are coordinated to preserve alignment. Each input retains its own lazy tags; before children are reassigned, the parent's tag is propagated to all direct children so that existing offsets are preserved.

We then repair the seam by regrouping intact children along existing boundaries and recompute the affected minima from bottom to top. Only a constant number of neighboring intervals are affected at each scale, and intact child structures are reused. Repeated requests for the same task are processed once, with all scans and numerical maintenance included in the level-wise cost.

We have clarified the charging argument in the following passages:

  • Section 3.3, p. 9, lines 432–449: We have clarified the fixed standard scales and explained the level-wise comparison.
  • Appendix H.2 and Lemma H.4, pp. 24–27, lines 1259–1423: We have derived the block-count bounds and explained the local repair procedure.
  • Appendix I, pp. 27–29, lines 1435–1457 and 1500–1513: We have described the MERGE procedure and explained how its maintenance costs are accounted for.
  • Appendices J and K.1, pp. 29–30, lines 1516–1582: We have provided the local cost analysis and the level-wise charging argument.

2. Zero-mass placeholders and the initial basis

The zero-mass placeholders mentioned in your review are the zero-weight auxiliary nodes described in our manuscript. Our algorithm builds on the classical network simplex framework studied by Cunningham (1976) and Orlin (1997); our contribution accelerates reduced-cost maintenance.

We have revised Appendix G to define a main tree that excludes the zero-supply source leaves. Basic arcs are the edges of the current spanning tree; within the main tree, those carrying zero flow point away from a fixed positive-supply root. We retain the positive-flow forest, connect the other positive-flow components by zero-flow arcs from the root to their sinks, and attach zero-demand sinks as outward leaves. Multiple zero-demand sinks therefore satisfy the same orientation condition; no positive reverse flow from them is required. Zero-supply sources are attached as leaves, and Appendix G separately establishes finite termination for iterations that change their attachment. Appendix G specifies the leaving-arc rule and explains preservation of the original masses and costs.

We have detailed these revisions here:

  • Appendix G, pp. 22–23, lines 1169–1210: We have explained the basis initialization and the treatment of zero-mass nodes.
AuthorsOpenReview ↗

Response to Reviewer aZfd(Part2)

3. Space, initialization costs, and empirical profiles

Theorem 3.4 and Appendix K.2 establish an O(n2)O(n^2)-word storage bound, including entries, hierarchy nodes, and references.

We have provided the bound and proof here:

  • Theorem 3.4, p. 9, lines 450–453: We have stated the space bound.
  • Appendix K.2, pp. 31–32, lines 1653–1683: We have provided a proof of this bound.

We have added paired three-dimensional experiments in Figures 16–17, using identical inputs and update sequences with 1,000–10,000 points per side. We measured peak resident set size (RSS), the maximum amount of physical memory used by the process. At 10,000 points per side, full-process peak RSS is 19.25 GiB for BMD Tree and 56.62 GiB for Skip List (Xu and Ding, 2024), approximately 66% lower for BMD Tree. For BMD Tree and Skip List, respectively, position-modification maxima are 51.63 and 136.78 s, and weight-modification maxima are 41.11 and 97.48 s. P99 is the 99th percentile within each update type and size: position-modification P99 is 48.40 versus 101.96 s, and weight-modification P99 is 34.32 versus 87.03 s. The 400 updates total 4,836.12 and 12,363.77 s, respectively, supporting a complete-update advantage.

Structure initialization assumes a given transportation plan and tree basis; initial-plan optimization is a separate task. Figure 16 reports initialization times, including optimization and construction: 52.80 s for BMD Tree and 145.58 s for Skip List. Position-modification timings throughout the paper include distance recomputation and reduced-cost maintenance.

The pivots referred to in your review correspond to the simplex iterations in our manuscript. These profiles measure complete updates. Per-iteration timings, node visits, and targeted repair/expansion tests are not included. The maintenance bound applies to the fixed global size in our problem setting and does not include pool expansion.

4. Accuracy settings and the nearly 200×200\times speedup

The Sinkhorn results are runtime comparisons under the stated regularization settings, not matched-accuracy comparisons; the latter would require aligned stopping criteria, objective gaps, and marginal residuals.

The nearly 200×200\times speedup refers to BMD Tree relative to the static Kuhn–Munkres (KM) algorithm at n=20,000n=20{,}000. Both methods compute exact matchings.

Thank you again. We hope these explanations and additions address your concerns, and we welcome further feedback.

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.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the reviewers and the Area Chair for their careful reading and constructive suggestions. The reviewers recognize the value of deterministic guarantees (12GX, GQV4) and the intermediate block design (12GX, aZfd). Below, we summarize their main concerns and how we have addressed them.

1. Unequal block lengths and the linear maintenance bound. Xyqb (Q1) and 12GX (Q1) ask whether the complexity analysis remains valid when block lengths change, and GQV4 (W3) asks us to clarify the role of equal block lengths in the proof. aZfd (Q1) asks how recursive constants are controlled. We have clarified that standard block lengths are fixed by the global input size and hierarchy level, so changing a parent's actual length does not change its children's standard lengths. Section 3.3 and Appendix K.1 now explicitly compare the total work at each level with the equal-length model using depth-independent constants. These constants are not multiplied through recursive calls, so summing the per-level costs preserves the O(n)O(n) reduced-cost maintenance bound per simplex iteration.

2. Dynamic repairs and MERGE. 12GX (Q1) and aZfd (Q1) ask how block-size repairs are included in the maintenance bound. We have expanded the proof of Lemma H.4 to explain that repairs affect only a constant number of neighboring intervals at each scale and reuse intact child structures, with reconstruction confined to constant-size cases. GQV4 (W1) asks for a fuller description of MERGE. In a follow-up, Xyqb asked how the partitions remain aligned throughout a simplex iteration. Section 3.1 and Figure 1 show how the submatrices inherit common row or column boundaries when the tree is cut. Appendix I explains how each subsequent change to a shared boundary is chosen once and applied to all corresponding blocks. The costs of tag propagation, scans, and minimum recomputation are accounted for in Appendices J and K.1 (aZfd Q1).

3. Initialization with zero-mass nodes. aZfd (Q2) asks how multiple zero-mass placeholders can satisfy the initialization requirements. In response, we have revised Appendix G to describe how zero-demand sinks are attached as outward leaves of a fixed-root main tree, while zero-supply sources are attached as additional leaves and treated separately in the termination argument. This handles multiple zero-mass nodes without perturbing the original weights or costs.

4. Experimental evidence and reported costs. Xyqb (Q2) asks about worst-case experimental behavior, and 12GX (Q3) and aZfd (Q3) request comparisons of the two dynamic methods. We have added paired comparisons with Skip List (Xu and Ding, 2024) in Appendix L.4. Figure 17 reports complete-update times, including observed maxima and P99 (the 99th percentile). At 10,000 points per side, BMD Tree and Skip List have observed maximum position-modification times of 51.63 s and 136.78 s, respectively (2.65-fold speedup); their observed maximum weight-modification times are 41.11 s and 97.48 s, respectively (2.37-fold speedup).

12GX (Q3) and aZfd (Q4) also ask about memory usage. Figure 16 now reports peak resident set size (RSS), the maximum physical memory used by the process: 19.25 GiB for BMD Tree versus 56.62 GiB for Skip List at 10,000 points per side, approximately 66% less. To address aZfd's question about the storage bound (Q4), we have added the O(n2)O(n^2) total space bound in Theorem 3.4 and its proof in Appendix K.2.

aZfd (Q4) also asks about the costs of initialization and cost-matrix updates. We have specified in the Fig. 16 caption that initialization times include initial optimization and structure construction. For the distance-computation questions raised by 12GX (Q2), GQV4 (W2), and aZfd (Q4), we have clarified that position-modification timings include distance recomputation and reduced-cost maintenance; the Fig. 17 caption explicitly includes cost refreshes.

Changes are marked in red in the revised manuscript; the individual responses provide detailed explanations and page and line references. Thank you again for your time and consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.