Pith. sign in

REVIEW 6 major objections 5 minor 83 references

Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation

T0 review · 6 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Hierarchical forecast reconciliation on general networks is polynomial-time for all ℓ_p>0 losses and strictly convex losses, via a network-flow reformulation, with O(n^2 log n) sparse-network complexity.

desk verdict A network-flow reframing of forecast reconciliation that is undone by unproven and in places false complexity claims. read the letter →

arxiv 2505.03955 v1 pith:T3LWGZYB submitted 2025-05-06 cs.LG cs.SI

Charupriya Sharma , Iñaki Estella Aguerri , Daniel Guimarans This is my paper · ORCID
classification cs.LGcs.SI MSC 68Q1768Q2590B1090C2562M10
keywords hierarchicalforecastingforecastreconciliationnetworkflowoptimizationminimumtrace(MinT)ℓ_pnormlossesdynamicupdatesapproximatecomputationalcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Hierarchical forecasting asks that forecasts at different aggregation levels agree, but standard forecasters produce incoherent numbers; reconciliation fixes this by projecting base forecasts onto a coherent subspace. This paper claims that when the aggregation structure is a network rather than a tree, the reconciliation problem becomes a network flow problem, and that this reformulation is computationally tractable for virtually all practical loss functions. Specifically, reconciliation under the ℓ0 norm is NP-hard, but under any ℓ_p norm with p > 0, and for any strictly convex continuously differentiable loss, it is solvable in polynomial time even with linear constraints. On sparse networks the proposed FlowRec method runs in O($n^{2}$ log n), improving on MinT's O($n^{3}$), and it replaces MinT's error-covariance estimation with direct network structure. If correct, this gives large-scale forecasting systems a faster way to keep forecasts coherent while also enabling local updates when networks or data change.

What carries the argument

The load-bearing object is the flow aggregation matrix S = [V'; E'; I] (Definition 3): n = |P|+|V|+|E| rows, with vertex-path incidence V', edge-path incidence E', and identity on paths. Given a path set P, every coherent flow forecast is a combination of path flows, and S maps path-level forecasts to node, edge, and path values. This matrix is what turns HFR into a convex optimization with flow-conservation structure; it is also what allows the reduction to min-cost flow, the orthogonal-projection computation, the localized update formulas, and the MinT equivalence with W = I.

What would settle it

Take a directed network with a simple cycle, attach supplies and demands that force a nonzero circulation, and form a base forecast that is coherent only with that circulating flow. FlowRec's path-sum representation with acyclic P cannot represent the circulation; if the algorithm still returns a coherent forecast, it must be the wrong one, demonstrating the path-set completeness condition is violated. Alternatively, on a graph with exponentially many simple paths, measure runtime as |P| grows; the O($n^{2}$ log n) sparse-network guarantee should break as soon as |P| dominates n.

Watch

Extended reading notes

Core claim

The core discovery is that hierarchical forecast reconciliation can be re-expressed as a flow optimization over a path set P of the underlying network. The coherent subspace is the range of a flow aggregation matrix S = [V'; E'; I] built from vertex-path and edge-path incidence matrices, and the reconciliation problem is then: minimize L(ˆy, S˜b) subject to S˜b = b and optional box constraints. Because the feasible set is convex and the loss is convex for ℓ_p with p > 0 or strictly convex differentiable f, the minimizer is unique and polynomial-time computable; the ℓ0 case is NP-hard. FlowRec's sparse-network complexity O($n^{2}$ log n) matches a stated lower bound Ω(m log n) up to a log factor, and FlowRec's quadratic objective with identity weight matrix is shown to be a special case of MinT, thereby generalizing MinT from trees to arbitrary graphs and removing the covariance estimation step.

Load-bearing premise

Every forecast that must be reconciled is assumed to be expressible as a sum of flows along a known, complete list of routes; if flows circulate in cycles or there are too many routes to list, the central complexity result does not apply.

Editorial extensions

If this is right

  • For any ℓ_p loss with p > 0, HFR is solvable in polynomial time even with additional linear constraints such as box bounds or weights.
  • On sparse networks, FlowRec's O(n^2 log n) runtime beats MinT's O(n^3), making large-scale reconciliation feasible where covariance-based methods are not.
  • FlowRec generalizes MinT to arbitrary network structures: setting W = I and S to the flow aggregation matrix recovers the MinT solution, but no covariance estimation is needed.
  • When a new edge is added or a single forecast component changes, optimal updates can be computed locally, in O(|P_e*|) or O(1) operations, instead of recomputing from scratch.
  • An ε-relaxed reconciliation can be computed in O(m log(1/ε) log n) with incoherence at most ε on each edge and bounded deviation from the exact solution.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper leaves implicit that the monotonicity result applies to any sequence of single-component improvements, so an online forecaster could skip reconciliation entirely during improving streaks; a natural test is to verify the condition on real data.
  • The flow-conservation structure suggests that network constraints act as a regularizer, which may explain the reported accuracy gains over base forecasts; a controlled experiment with misspecified networks could test whether the effect is robust.
  • If cyclic flows matter in practice, such as inventory loops or recirculating traffic, FlowRec's path-sum representation needs an extension to circulations; a cycle-space augmentation of S would be the obvious next formulation to try.
  • The ε-relaxation trades coherence for speed in a provable way, which could be used as a latency budget in real-time control systems; one could adapt ε online based on current demand for forecast speed.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

6 major / 5 minor

Summary. The paper proposes FlowRec, a reformulation of hierarchical forecast reconciliation as a network-flow optimization over paths, with claims of polynomial-time solvability for all ℓ_p norms with p>0 and for general strictly convex, continuously differentiable losses; an Ω(m log n) lower bound; a generalization of MinT to networks; localized dynamic updates with optimality guarantees; and experiments reporting 3–40× speedups and 5–7× memory reductions. The technical formulation represents forecasts on a network by a flow aggregation matrix S=[V';E';I] over vertex-, edge-, and path-level variables, and solves the resulting constrained optimization.

Significance. If the main theoretical claims were correct, the paper would provide a useful complexity characterization and a practical algorithm for network-structured reconciliation, with dynamic-update guarantees. The paper makes a conceptually appealing connection between reconciliation and path flows and reports systematic experiments across simulated and real benchmarks. However, several load-bearing theorems are false or unproven: the ℓ_p claim ignores non-convexity for 0<p<1, the lower-bound proof is invalid, the complexity bounds do not account for exponential path sets, and the dynamic-update theorems fail on simple examples. These are not presentation issues; they undercut the central contributions advertised in the abstract.

major comments (6)
  1. [§4.1 (Theorem 2) and Appendix A.1 (Theorems 13–14)] The polynomial-time claim for all ℓ_p with p>0 is not supported. For 0<p<1 the objective ∑|x_i|^p is non-convex, so the statement that HFR can be solved via convex optimization does not apply; the proof explicitly treats only p=1 and p=2. The companion result for general strictly convex f (Theorem 3/14) is also false as stated: f(|x|) need not be convex when f is strictly convex (e.g., f(t)=(t−1)^2 gives (|x|−1)^2, which is not convex on R). A related problem appears in Theorem 6, where orthogonal projection is claimed to be equivalent to the minimum reconciling flow for general losses; that equivalence holds only for the ℓ2 objective. These theorems underlie the abstract's complexity and computation-method claims, so the gaps are load-bearing.
  2. [Appendix A.1, Theorem 15] The Ω(m log n) lower bound is not established. In the constructed graph, flow conservation imposes only that the sum of path flows equals the source/sink forecast and that each edge flow equals its path flow; it does not force any ordering of path values. The assertion that 'to satisfy flow conservation, we must have ˜y_{P1}≤...≤˜y_{Pn}' is false, and the optimal ℓ2 reconciliation does not require sorting. A correct lower-bound proof would need a genuinely different construction.
  3. [Definition 3 and Corollary 1] The complexity statements depend on n=|V|+|E|+|P|, but no polynomial bound on |P| is given. In a sparse layered graph with two parallel edges between consecutive layers, |V|,|E|=O(k) while |P|=2^{Ω(k)}, so forming S and even writing the flow variables requires Ω(|P|) time and memory. Section 6 itself notes that path counts can grow as O(|N|^k) for paths of length k. Absent a bound on |P| or a compact edge-flow formulation, the advertised O(n^2 log n) complexity for sparse networks does not follow.
  4. [Theorem 1 and Appendix A.1, Theorem 12] The NP-hardness reduction from Exact-1-in-3-SAT is invalid. With coefficients +1 for positive literals and −1 for negative literals, a clause whose unique true literal is negative has signed sum −1, not +1, so a satisfying assignment does not satisfy the constructed equation. The proof also does not specify the role of σ_j as a forecast variable; if σ_j is free, zero ℓ0 loss does not by itself force σ_j=0 unless its base forecast is fixed to 0, which is not stated. The ℓ0 hardness claim therefore lacks a valid proof.
  5. [§4.4 (Theorem 7) and §4.2 (Theorem 5)] The claimed equivalence with MinT is a definitional special case, not a generalization. Formula (P1) is the standard weighted projection formula for any symmetric positive definite W; setting W=I and S to a flow incidence matrix is an instance of that formula, not a new derived generalization. Similarly, Theorem 5 restates that S is a summing matrix: any vector Sx lies in the column space of S and satisfies the incidence relations. These observations do not substantiate the abstract's claim that FlowRec extends MinT to general networks.
  6. [§5.1–5.2 (Theorems 8 and 9)] The dynamic-update theorems are not correct as stated. In Theorem 8, the ℓ1 objective is not strictly convex, so the equal-split update is not the unique minimal adjustment; any nonnegative split of Δ summing to the required total is optimal. Theorem 9 and Corollary 2 are falsified by a simple example: take coherent subspace {(a,a)}, old base forecast (10,0) with optimal reconciliation (5,5), and new base forecast (9,0). The condition |5−9|<|5−10| holds, yet the optimal reconciliation becomes (4.5,4.5). Hence the claimed monotonicity property does not hold.
minor comments (5)
  1. [Abstract and Table 3] The abstract claims 3–40× speedups and 5–7× memory reductions, but Table 3 shows 0.172/0.063≈2.7× and 5.6/1.2≈4.7×; please reconcile the numbers.
  2. [§4.3 and Appendix A.3] Main text Theorem 6 says there are two computation methods, while Appendix A.3 Theorem 17 says there are three; the numbering, content, and statements should be harmonized.
  3. [Appendix A.2, Theorem 16] The proof contains malformed notation such as 'e=(,v)' and 'P∈P', and the flow-conservation equation uses b_v without a clear definition for all node types; please fix the notation.
  4. [References] The reference list is duplicated in full (pages 16–21 and 19–24), and entries [33] and [45] each appear twice; deduplicate and consolidate the bibliography.
  5. [§6.1, Figure 4] The text for Figure 4 says performance degrades as density increases, but the x-axis is maximum path length; the wording appears copied from the discussion of Figure 3.

Circularity Check

2 steps flagged · score 4.0 of 10

FlowRec's flow-conservation theorem restates its path-incidence definition, and its 'MinT extension' is the W=I special case of the standard projection formula; the central ℓ2 projection is independently grounded.

  1. self definitional [Section 3, Definition 3 and Section 4.2, Theorem 5]
    "Flow aggregation constraints are given by: S = (V′; E′; I_|P|) ∈ R^{n×|P|} where V′ is the vertex-path incidence matrix defined by v′_ij = 1 if vertex i appears in path j, 0 otherwise and E′ is the edge-path incidence matrix defined by e′_ij = 1 if edge i appears in path j, 0 otherwise. ... The edge values ỹ_e,T+h|T of ỹ_T+h|T = S ŷ_T+h|T form a flow in G=(V,E) satisfying supplies and demands: b_v = Σ_{P∈P:O(P)=v} ỹ_P,T+h|T − Σ_{P∈P:D(P)=v} ỹ_P,T+h|T, ∀v∈V."

    Definition 1 already defines a coherent forecast as y = S b, and Definition 3 builds S as vertex/edge-path incidence. Therefore ỹ = S ŷ is coherent by definition, and the balance equation in Theorem 5 is exactly the incidence identity encoded in S. Theorem 5 is a restatement of the definitions, not a derived property. The paper later cites it as 'predicted by our flow conservation principles (Theorem 5)' to explain empirical accuracy gains, making a definitional identity load-bearing as if it were a predictive result.

  2. renaming known result [Section 4.4, Theorem 7 and Abstract]
    "the following optimization problems: (P1): min_ỹ (ỹ−ŷ)^T W (ỹ−ŷ) subject to Sỹ = b; (P2): min_ỹ (ỹ−ŷ)^T Σ^{−1}(ỹ−ŷ) subject to Sỹ = b ... 2. When W = Σ^{−1}, the problems (P1) and (P2) are equivalent. 3. FlowRec is a special case where W = I and S = (V; E; I) with V as vertex-path incidence matrix, E as edge-path incidence matrix, and I as identity matrix for paths."

    Setting W = Σ^{−1} makes (P2) literally (P1) with W renamed, so property 2 is substitution rather than a derived equivalence. The abstract's claim that 'FlowRec extends MinT beyond tree structures ... replacing MinT's error-covariance estimation step with direct network structural information' is not proved by Theorem 7: the 'extension' is the special case W = I of the same weighted projection formula, not a derived generalization. The claimed novelty reduces to the identity W = I plus a standard closed-form projection.

full rationale

The central ℓ2 reconciliation algorithm is independently grounded in classical orthogonal projection onto the range of S, and the polynomial-time claims for convex losses rest on standard convex optimization rather than on circular input-output equivalence. There is no load-bearing self-citation chain: the paper's citations to MinT and geometric reconciliation are external and the algebra in Theorem 7 is self-contained. The unbounded-path-size issue raised by the skeptic is a correctness gap in Corollary 1 (the complexity bound uses n = |V| while Definition 3 sets the problem dimension to |P|+|V|+|E|), but that is a missing assumption, not a circular reduction, and I do not count it toward the score. The two flagged steps are definitional/renaming: Theorem 5 unpacks what S already means, and Theorem 7's 'MinT extension' is the special case W=I of a textbook projection formula. These moderate the paper's novelty claims but do not collapse the main derivation, so a score of 4 reflects partial circularity in supporting claims while the core projection method retains independent content.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on the linear-aggregation model, a path-decomposable flow representation, the convexity of the loss, and the contested premise that MinT is tree-only. Complexity bounds additionally require the path set to be small enough to enumerate and store.

assumptions (4)
  • domain assumption Aggregation constraints are linear and time-invariant: y_t = S b_t (Definition 1).
    Standard in hierarchical forecasting; the paper extends it to flow aggregation matrices. Not proven from data.
  • ad hoc to paper Any network flow can be decomposed over a known path set P, and the path set is available and not exponentially large (Definition 3, Theorem 6).
    Needed for S = [V'; E'; I] to be a valid representation and for the O(n^2 log n) complexity; excludes circulations and presumes path enumeration is tractable.
  • standard math Loss separates as L(x, y) = sum_i f(|x_i - y_i|) with f strictly convex, continuously differentiable, f(0) = 0 (Theorem 3).
    Standard assumption for convex optimization; the paper's uniqueness and polynomial-time claims come from this.
  • domain assumption MinT is limited to tree structures (Introduction, Section 4.4).
    Factual premise used to motivate FlowRec; the original MinT paper handles grouped hierarchies beyond trees, so the premise is contestable.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation." pith.science (2026). https://pith.science/paper/T3LWGZYB

@misc{pith2026250503955,
  author       = {Pith},
  title        = {Pith review of: Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T3LWGZYB}},
  note         = {Machine review of arXiv:2505.03955}
}
abstract

Hierarchical forecasting with reconciliation requires forecasting values of a hierarchy (e.g.~customer demand in a state and district), such that forecast values are linked (e.g.~ district forecasts should add up to the state forecast). Basic forecasting provides no guarantee for these desired structural relationships. Reconciliation addresses this problem, which is crucial for organizations requiring coherent predictions across multiple aggregation levels. Current methods like minimum trace (MinT) are mostly limited to tree structures and are computationally expensive. We introduce FlowRec, which reformulates hierarchical forecast reconciliation as a network flow optimization, enabling forecasting on generalized network structures. While reconciliation under the $\ell_0$ norm is NP-hard, we prove polynomial-time solvability for all $\ell_{p > 0}$ norms and , for any strictly convex and continuously differentiable loss function. For sparse networks, FlowRec achieves $O(n^2\log n)$ complexity, significantly improving upon MinT's $O(n^3)$. Furthermore, we prove that FlowRec extends MinT to handle general networks, replacing MinT's error-covariance estimation step with direct network structural information. A key novelty of our approach is its handling of dynamic scenarios: while traditional methods recompute both base forecasts and reconciliation, FlowRec provides efficient localised updates with optimality guarantees. Monotonicity ensures that when forecasts improve incrementally, the initial reconciliation remains optimal. We also establish efficient, error-bounded approximate reconciliation, enabling fast updates in time-critical applications. Experiments on both simulated and real benchmarks demonstrate that FlowRec improves accuracy, runtime by 3-40x and memory usage by 5-7x. These results establish FlowRec as a powerful tool for large-scale hierarchical forecasting applications.

Figures

Figures reproduced from arXiv: 2505.03955 by the authors.

Figure 1
Figure 1. Comparison of Tree and Network Reconciliation. Base forecasts deviate from true [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Total RMSE for forecasting and reconciliation for simulated data, shown across [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. RMSE for AutoARIMA, plotted against density ( node degree, 1 means fully [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (29 more)
Figure 4
Figure 4. Figure 4: RMSE for AutoARIMA, plotted against the maximum path length [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]
Figure 5
Figure 5. Figure 5: RMSE results for forecasting and reconciliation models across all hierarchies. [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: RMSE results for forecasting and reconciliation models across paths for simulated [PITH_FULL_IMAGE:figures/full_fig_p035_6.png]
Figure 7
Figure 7. Figure 7: RMSE results for forecasting and reconciliation models across edges for simulated [PITH_FULL_IMAGE:figures/full_fig_p035_7.png]
Figure 8
Figure 8. Figure 8: RMSE results for forecasting and reconciliation models across all nodes for simulated [PITH_FULL_IMAGE:figures/full_fig_p036_8.png]
Figure 9
Figure 9. Figure 9: MAE results for forecasting and reconciliation models across all hierarchies for [PITH_FULL_IMAGE:figures/full_fig_p036_9.png]
Figure 10
Figure 10. Figure 10: MAE results for forecasting and reconciliation models across paths for simulated [PITH_FULL_IMAGE:figures/full_fig_p037_10.png]
Figure 11
Figure 11. Figure 11: MAE results for forecasting and reconciliation models across edges for simulated [PITH_FULL_IMAGE:figures/full_fig_p037_11.png]
Figure 12
Figure 12. Figure 12: MAE results for forecasting and reconciliation models across nodes for simulated [PITH_FULL_IMAGE:figures/full_fig_p038_12.png]
Figure 13
Figure 13. Figure 13: MAE results for ARIMA, plotted against the density (degree of nodes, where 1 [PITH_FULL_IMAGE:figures/full_fig_p038_13.png]
Figure 14
Figure 14. Figure 14: MAE results for ARIMA, plotted against the maximum path length of the simulated [PITH_FULL_IMAGE:figures/full_fig_p039_14.png]
Figure 15
Figure 15. Figure 15: RMSE results for ARIMA, plotted against the density (degree of nodes, where 1 [PITH_FULL_IMAGE:figures/full_fig_p039_15.png]
Figure 16
Figure 16. Figure 16: RMSE results for ARIMA for paths, plotted against the maximum path length of [PITH_FULL_IMAGE:figures/full_fig_p040_16.png]
Figure 17
Figure 17. Figure 17: RMSE results for ARIMA for edges, plotted against the density (degree of nodes, [PITH_FULL_IMAGE:figures/full_fig_p040_17.png]
Figure 18
Figure 18. Figure 18: RMSE results for ARIMA for edges, plotted against the maximum path length of [PITH_FULL_IMAGE:figures/full_fig_p041_18.png]
Figure 19
Figure 19. Figure 19: RMSE results for ARIMA for nodes, plotted against the density (degree of nodes, [PITH_FULL_IMAGE:figures/full_fig_p041_19.png]
Figure 20
Figure 20. Figure 20: RMSE results for ARIMA for nodes, plotted against the maximum path length of [PITH_FULL_IMAGE:figures/full_fig_p042_20.png]
Figure 21
Figure 21. Figure 21: MAE results for ARIMA, plotted against the density (degree of nodes, where 1 [PITH_FULL_IMAGE:figures/full_fig_p042_21.png]
Figure 22
Figure 22. Figure 22: MAE results for ARIMA for paths, plotted against the maximum path length of [PITH_FULL_IMAGE:figures/full_fig_p043_22.png]
Figure 23
Figure 23. Figure 23: MAE results for ARIMA for edges, plotted against the density (degree of nodes, [PITH_FULL_IMAGE:figures/full_fig_p043_23.png]
Figure 24
Figure 24. Figure 24: MAE results for ARIMA for edges, plotted against the maximum path length of [PITH_FULL_IMAGE:figures/full_fig_p044_24.png]
Figure 25
Figure 25. Figure 25: MAE results for ARIMA for nodes, plotted against the density (degree of nodes, [PITH_FULL_IMAGE:figures/full_fig_p044_25.png]
Figure 26
Figure 26. Figure 26: MAE results for ARIMA for nodes, plotted against the maximum path length of [PITH_FULL_IMAGE:figures/full_fig_p045_26.png]
Figure 27
Figure 27. Figure 27: RMSE results for forecasting and reconciliation models across all hierarchies. [PITH_FULL_IMAGE:figures/full_fig_p045_27.png]
Figure 28
Figure 28. Figure 28: RMSE results for forecasting and reconciliation models across all hierarchies. [PITH_FULL_IMAGE:figures/full_fig_p046_28.png]
Figure 29
Figure 29. Figure 29: RMSE results for forecasting and reconciliation models across all hierarchies. [PITH_FULL_IMAGE:figures/full_fig_p046_29.png]
Figure 30
Figure 30. Figure 30: RMSE results for forecasting and reconciliation models across all hierarchies. [PITH_FULL_IMAGE:figures/full_fig_p047_30.png]
Figure 31
Figure 31. Figure 31: RMSE results for forecasting and reconciliation models across all hierarchies. [PITH_FULL_IMAGE:figures/full_fig_p047_31.png]
Figure 32
Figure 32. Figure 32: RMSE results for forecasting and reconciliation models across all hierarchies. [PITH_FULL_IMAGE:figures/full_fig_p048_32.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

83 extracted references · 74 canonical work pages

  1. [1]

    New algorithms and lower bounds for all-pairs max-flow in undirected graphs

    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. “New algorithms and lower bounds for all-pairs max-flow in undirected graphs”. In:Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 2020, pp. 48–61

    2020

  2. [2]

    Ravindra K Ahuja, Thomas L Magnanti, James B Orlin, et al.Network flows: theory, algorithms, and applications. Vol. 1. Prentice hall Englewood Cliffs, NJ, 1993

    1993

  3. [3]

    “Approximating st minimum cuts in Õ (n

    András A Benczúr and David R Karger. “Approximating st minimum cuts in Õ (n

  4. [4]

    In:Proceedings of the twenty-eighth annual ACM symposium on Theory of computing

    time”. In:Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996, pp. 47–55

    work page 1996

  5. [5]

    George EP Box et al.Time Series Analysis: Forecasting and Control. 5th ed. John Wiley & Sons, 2015.isbn: 978-1-118-67502-1

    work page 2015

  6. [6]

    Faster high accuracy multi-commodity flow from single-commodity techniques

    Jan van den Brand and Daniel Zhang. “Faster high accuracy multi-commodity flow from single-commodity techniques”. In:2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2023

    work page 2023

  7. [7]

    Bipartite matching in nearly-linear time on moderately dense graphs

    Jan van den Brand et al. “Bipartite matching in nearly-linear time on moderately dense graphs”. In:2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2020, pp. 919–930

    work page 2020

  8. [8]

    Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

    Jan van den Brand et al. “Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time”. In:Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2024, pp. 2980–2998

    work page 2024

Show all 83 references
  1. [9]

    Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, st Shortest Path, and Minimum-Cost Flow

    Li Chen et al. “Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, st Shortest Path, and Minimum-Cost Flow”. In:Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024, pp. 1165–1173

    2024

  2. [10]

    Maximum flow and minimum-cost flow in almost-linear time

    Li Chen et al. “Maximum flow and minimum-cost flow in almost-linear time”. In:2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2022, pp. 612–623

    2022

  3. [11]

    Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

    Paul Christiano et al. “Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs”. In:Proceedings of the forty-third annual ACM symposium on Theory of computing. 2011, pp. 273–282

    2011

  4. [12]

    Dirichlet proportions model for hierarchically coherent prob- abilistic forecasting

    Abhimanyu Das et al. “Dirichlet proportions model for hierarchically coherent prob- abilistic forecasting”. In:Uncertainty in Artificial Intelligence. PMLR. 2023, pp. 518– 528

    2023

  5. [13]

    Warm-starting Push-Relabel

    Sami Davies, Sergei Vassilvitskii, and Yuyan Wang. “Warm-starting Push-Relabel”. In: arXiv preprint arXiv:2405.18568(2024)

    2024 arXiv

  6. [14]

    Predictiveflowsforfasterford-fulkerson

    SamiDaviesetal. “Predictiveflowsforfasterford-fulkerson”.In: International Conference on Machine Learning. PMLR. 2023, pp. 7231–7248

    2023

  7. [15]

    Nested dissection meets ipms: Planar min-cost flow in nearly-linear time

    Sally Dong et al. “Nested dissection meets ipms: Planar min-cost flow in nearly-linear time”. In:Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2022, pp. 124–153

    2022

  8. [16]

    Theoretical improvements in algorithmic efficiency for network flow problems

    Jack Edmonds and Richard M Karp. “Theoretical improvements in algorithmic efficiency for network flow problems”. In:Journal of the ACM (JACM)19.2 (1972), pp. 248–264

    1972

  9. [17]

    Approximating fractional multicommodity flow independent of the number of commodities

    Lisa K Fleischer. “Approximating fractional multicommodity flow independent of the number of commodities”. In: SIAM Journal on Discrete Mathematics 13.4 (2000), pp. 505–520

    2000

  10. [18]

    Constructing maximal dynamic flows from static flows

    Lester R Ford Jr and Delbert R Fulkerson. “Constructing maximal dynamic flows from static flows”. In:Operations research6.3 (1958), pp. 419–433. 19

    1958

  11. [19]

    Maximal flow through a network

    Lester R Ford Jr and Delbert R Fulkerson. “Maximal flow through a network”. In: Canadian journal of Mathematics8 (1956), pp. 399–404

    1956

  12. [20]

    A network flow computation for project cost curves

    Delbert R Fulkerson. “A network flow computation for project cost curves”. In:Manage- ment science7.2 (1961), pp. 167–178

    1961

  13. [21]

    Transient flows in networks

    David Gale. “Transient flows in networks”. In:Michigan Mathematical Journal6.1 (1959), pp. 59–63

    1959

  14. [22]

    Faster and simpler algorithms for multicommodity flow and other fractional packing problems

    Naveen Garg and Jochen Könemann. “Faster and simpler algorithms for multicommodity flow and other fractional packing problems”. In:SIAM Journal on Computing37.2 (2007), pp. 630–652

    2007

  15. [23]

    Clarabel: An interior-point solver for conic programs with quadratic objectives

    Paul J Goulart and Yuwen Chen. “Clarabel: An interior-point solver for conic programs with quadratic objectives”. In:arXiv preprint arXiv:2405.12762(2024)

    2024 arXiv

  16. [24]

    Recent Advances in Fully Dynamic Graph Algorithms - A Quick Reference Guide

    Kathrin Hanauer, Monika Henzinger, and Christian Schulz. “Recent Advances in Fully Dynamic Graph Algorithms - A Quick Reference Guide”. In:ACM J. Exp. Algorithmics 27 (2022), 1.11:1–1.11:45.doi: 10.1145/3555806. url: https://doi.org/10.1145/ 3555806

    2022 doi

  17. [25]

    Improvedalgorithms for decremental single-source reachability on directed graphs

    MonikaHenzinger,SebastianKrinninger,andDanuponNanongkai.“Improvedalgorithms for decremental single-source reachability on directed graphs”. In:Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 42...

    2015

  18. [26]

    Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

    Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs”. In:Proceedings of the forty-sixth annual ACM symposium on Theory of com- puting. 2014, pp. 674–683

    2014

  19. [27]

    Springer, 2008

    Rob J Hyndman et al.Forecasting with exponential smoothing: the state space approach. Springer, 2008. isbn: 978-3-540-71916-8

    2008

  20. [28]

    Optimal combination forecasts for hierarchical time series

    Rob J Hyndman et al. “Optimal combination forecasts for hierarchical time series”. In: Computational statistics & data analysis55.9 (2011), pp. 2579–2589

    2011

  21. [29]

    Profhit: Probabilistic robust forecasting for hierarchical time-series

    Harshavardhan Kamarthi et al. “Profhit: Probabilistic robust forecasting for hierarchical time-series”. In:arXiv preprint arXiv:2206.07940(2022)

    2022 arXiv

  22. [30]

    On the translocation of masses

    Leonid V Kantorovich. “On the translocation of masses”. In:Doklady Akademii Nauk SSSR 37.7-8 (1942), pp. 227–229

    1942

  23. [31]

    Faster approximation schemes for fractional multicommodity flow problems

    George Karakostas. “Faster approximation schemes for fractional multicommodity flow problems”. In:ACM Transactions on Algorithms (TALG)4.1 (2008), pp. 1–17

    2008

  24. [32]

    A faster deterministic maximum flow algorithm

    Valerie King, Satish Rao, and Rorbert Tarjan. “A faster deterministic maximum flow algorithm”. In:Journal of Algorithms17.3 (1994), pp. 447–474

    1994

  25. [33]

    Single source–All sinks max flows in planar digraphs

    Jakub Lacki et al. “Single source–All sinks max flows in planar digraphs”. In:2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE. 2012, pp. 599–608

    2012

  26. [35]

    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

    Tom Leighton and Satish Rao. “Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms”. In:Journal of the ACM (JACM)46.6 (1999), pp. 787–832

    1999

  27. [36]

    Computing maximum flow with augmenting electrical flows

    Aleksander Madry. “Computing maximum flow with augmenting electrical flows”. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2016, pp. 593–602. 20

    2016

  28. [37]

    Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

    Aleksander Madry. “Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms”. In:Proceedings of the forty-second ACM symposium on Theory of computing. 2010, pp. 121–130

    2010

  29. [38]

    Navigating central path with electrical flows: From flows to match- ings, and back

    Aleksander Madry. “Navigating central path with electrical flows: From flows to match- ings, and back”. In:2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE. 2013, pp. 253–262

    2013

  30. [39]

    Probabilistic hierarchical forecasting with deep poisson mixtures

    Kin G Olivares et al. “Probabilistic hierarchical forecasting with deep poisson mixtures”. In: International Journal of Forecasting40.2 (2024), pp. 470–489

    2024

  31. [40]

    A simpler and faster strongly polynomial algorithm for generalized flow maximization

    Neil Olver and László A Végh. “A simpler and faster strongly polynomial algorithm for generalized flow maximization”. In:Journal of the ACM (JACM)67.2 (2020), pp. 1–26

    2020

  32. [41]

    N-BEATS: Neural basis expansion analysis for interpretable time series forecasting

    Boris N Oreshkin et al. “N-BEATS: Neural basis expansion analysis for interpretable time series forecasting”. In:arXiv preprint arXiv:1905.10437(2019)

    2019 arXiv

  33. [42]

    Forecastreconciliation:Ageometricviewwithnewinsights on bias correction

    AnastasiosPanagiotelisetal.“Forecastreconciliation:Ageometricviewwithnewinsights on bias correction”. In:International Journal of Forecasting37.1 (2021), pp. 343–359

    2021

  34. [43]

    Learning-augmented maximum flow

    Adam Polak and Maksym Zub. “Learning-augmented maximum flow”. In:Information Processing Letters186 (2024), p. 106487

    2024

  35. [44]

    Deep state space models for time series forecasting

    Syama Sundar Rangapuram et al. “Deep state space models for time series forecasting”. In: Advances in neural information processing systems31 (2018)

    2018

  36. [45]

    End-to-end learning of coherent probabilistic forecasts for hierarchical time series

    Syama Sundar Rangapuram et al. “End-to-end learning of coherent probabilistic forecasts for hierarchical time series”. In:International Conference on Machine Learning. PMLR. 2021, pp. 8832–8842

    2021

  37. [46]

    Demand forecasting and inventory control: A simulation study on automotive spare parts

    José Roberto do Rego and Marco Aurélio De Mesquita. “Demand forecasting and inventory control: A simulation study on automotive spare parts”. In:International Journal of Production Economics161 (2015), pp. 1–16

    2015

  38. [47]

    Long short-term memory based recurrent neural network architectures for large vocabulary speech recognition

    H Sak. “Long short-term memory based recurrent neural network architectures for large vocabulary speech recognition”. In:arXiv preprint arXiv:1402.1128(2014)

    2014 arXiv

  39. [48]

    DeepAR: Probabilistic forecasting with autoregressive recurrent networks

    David Salinas et al. “DeepAR: Probabilistic forecasting with autoregressive recurrent networks”. In:International Journal of Forecasting36.3 (2020), pp. 1181–1191

    2020

  40. [49]

    Bayesian intermittent demand forecasting for large inventories

    Matthias W Seeger, David Salinas, and Valentin Flunkert. “Bayesian intermittent demand forecasting for large inventories”. In:Advances in Neural Information Processing Systems 29 (2016), pp. 4646–4654

    2016

  41. [50]

    The maximum concurrent flow problem

    Farhad Shahrokhi and David W Matula. “The maximum concurrent flow problem”. In: Journal of the ACM (JACM)37.2 (1990), pp. 318–334

    1990

  42. [51]

    An introduction to network flows over time

    Martin Skutella. “An introduction to network flows over time”. In:Research Trends in Combinatorial Optimization: Bonn 2008(2009), pp. 451–482

    2009

  43. [52]

    A deterministic almost-linear time algorithm for minimum- cost flow

    Jan Van Den Brand et al. “A deterministic almost-linear time algorithm for minimum- cost flow”. In:2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2023, pp. 503–514

    2023

  44. [53]

    Optimal fore- cast reconciliation for hierarchical and grouped time series through trace minimization

    Shanika L Wickramasuriya, George Athanasopoulos, and Rob J Hyndman. “Optimal fore- cast reconciliation for hierarchical and grouped time series through trace minimization”. In: Journal of the American Statistical Association114.526 (2019), pp. 804–819

    2019

  45. [54]

    Cambridge university press, 2011

    David P Williamson and David B Shmoys.The design of approximation algorithms. Cambridge university press, 2011

    2011

  46. [55]

    Are transformers effective for time series forecasting?

    Ailing Zeng et al. “Are transformers effective for time series forecasting?” In:Proceedings of the AAAI conference on artificial intelligence. Vol. 37. 2023, pp. 11121–11128. 21 A Properties of the HFR Formulation and the FlowRec Frame- work A.1 Hardness of HFR Theorem 12(NP-H...

    2023

  47. [56]

    Forp = 1 (MAE), HFR reduces to linear programming

  48. [57]

    Forp = 2 (MSE), HFR reduces to quadratic programming

  49. [58]

    For generalp> 0, HFR can be solved via convex optimization This holds even with additional linear constraints such as upper/lower bounds or weighted objectives. Proof. For MSE and RMSE, we can find an optimal solution in polynomial time by quadratic programming – note that the...

  50. [59]

    The FlowRec optimization problem has a unique solution

  51. [60]

    This solution can be computed in polynomial time via interior point methods

  52. [61]

    The optimization problem becomes: min ˜y nX i=1 f(|˜yi− ˆyi|) subject to S˜y = b The objective is strictly convex as a sum of strictly convex functions composed with norms

    The solution preserves flow conservation Proof. The optimization problem becomes: min ˜y nX i=1 f(|˜yi− ˆyi|) subject to S˜y = b The objective is strictly convex as a sum of strictly convex functions composed with norms. The constraints form a polyhedral set. Therefore: • Uniq...

  53. [62]

    VerticesV ={s,t}∪{ v1,...,v n}, wheres is a source andt is a sink

  54. [63]

    Edges E ={(s,vi), (vi,t ) :i∈{ 1,...,n }}

  55. [64]

    Therefore, computing the exact reconciled forecasts implicitly requires sorting the values x1,...,x n

    For eachi∈{ 1,...,n }, define a pathPi = (s,vi,t ) Now, set the base forecasts as follows: • ˆyPi,T +h|T =xi for i∈{ 1,...,n } • ˆys,T +h|T =Pn i=1xi • ˆyt,T +h|T =Pn i=1xi • ˆyvi,T +h|T =xi for i∈{ 1,...,n } Consider the flow conservation constraints in this network: ˜ys,T +h...

  56. [65]

    S is a reconciling mapping

  57. [66]

    The edge values˜ye,T +h|T of ˜yT +h|T = SˆyT +h|T form a flow inG = (V,E ) satisfying supplies and demands: bv = X P∈P:O(P )=v ˜yP,T +h|T− X P∈P:D(P )=v ˜yP,T +h|T, ∀v∈V where ˜yP,T +h|T is the reconciled value for pathP, andO(P ),D (P )∈V refer to the origin and destination n...

  58. [67]

    Orthogonal projection ofˆyT +h|T to s: • Compute an orthonormal basisE ={e1,..., e|P|} of s • Project ˆyT +h|T onto s: ˜yT +h|T = |P|X i=1 ⟨ˆyT +h|T, ei⟩ei

  59. [68]

    We prove each method yields the optimal reconciled forecasts: Step 1: Orthogonal projection correctness

    Minimum Reconciling Flow: min sP,sE,sV f(sP, sE, sV ) subject to: sP≥ ˆyP− ˜yP ∀P∈P sP≥ ˜yP− ˆyP ∀P∈P sE≥ ˆyE− ˜yE ∀e∈E sE≥ ˜yE− ˆyE ∀e∈E sV≥ ˆyV− ˜yV ∀v∈V sV≥ ˜yV− ˆyV ∀v∈V X P∈P:e∈P ˜yP = ˜ye ∀e∈E X P∈P:v∈P ˜yP = ˜yv ∀v∈V Proof. We prove each method yields the optimal reconc...

  60. [69]

    Both problems have a unique solution of the form: ˜y = ˆy− W−1ST (SW−1ST )−1(Sˆy− b)

  61. [70]

    When W = Σ−1, the problems(P1) and (P2) are equivalent

  62. [71]

    We prove this in four steps: Step 1: First, we show that(P1) has a unique solution

    FlowRec is a special case whereW = I and S =   V E I   with V as vertex-path incidence matrix, E as edge-path incidence matrix, andI as identity matrix for paths Proof. We prove this in four steps: Step 1: First, we show that(P1) has a unique solution. LetL(˜y,λ) be the La...

  63. [72]

    For sparse networks wherem =O(n): • FlowRec requiresO(n2 logn) operations • MinT requiresO(n3) operations

  64. [73]

    For dense networks wherem =O(n2): • FlowRec requiresO(n4) operations • MinT requiresO(n4) operations Moreover, FlowRec preserves network flow properties without requiring explicit path enumera- tion. Proof. We prove this in five steps: Step 1: Transform to minimum cost flow. T...

  65. [74]

    Initialize residual network:O(m)

  66. [75]

    While required flow not satisfied: 28 • Find shortest path using Fibonacci heap:O(m +n logn) • Augment flow along path:O(m) • Update residual network:O(m)

  67. [76]

    Maximum number of iterations:O(m) Total complexity forFlowRec: O(m2 +mn logn) Step 3: Analysis of MinT operations:

  68. [77]

    Computing SΣ−1ST: • Matrix multiplication cost:O(n2m) • For dense graphs(m =O(n2)): O(n4) • For sparse graphs(m =O(n)): O(n3)

  69. [78]

    B Fast Updates and Approximations Hierarchical forecasting applications face three key challenges that traditional reconciliation methods like MinT handle inefficiently

    Matrix inversion:O(n3) operations Total complexity for MinT dominated by matrix multiplication in dense case:O(n4) Step 4: Complexity analysis for network density cases: For FlowRec: • Sparse networks(m =O(n)): O(m2 +mn logn) =O(n2 +n2 logn) =O(n2 logn) • Dense networks(m =O(n...

  70. [79]

    Finding an alternative path requires one Dijkstra computation:O(m +n logn)

  71. [80]

    Storing the alternative path requiresO(d) space

  72. [81]

    B.4 Efficient Approximate Reconciliation Real-timeforecastingapplicationsoftenprioritizecomputationalefficiencyoverexactcoherence

    Updating flow values requiresO(d) operations The total complexity follows from performing these operations for each affected path. B.4 Efficient Approximate Reconciliation Real-timeforecastingapplicationsoftenprioritizecomputationalefficiencyoverexactcoherence. Consider a reta...

  73. [82]

    Gradient computation:O(m)

  74. [83]

    Projection onto box constraints:O(m)

  75. [84]

    Memory requirements areO(m) to store the current solution and gradient

    Line search:O(logn) using binary search The total complexity follows. Memory requirements areO(m) to store the current solution and gradient. This result provides practitioners with a principled way to trade off computational efficiency against forecast coherence. The error bo...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.