Minimum-Cost Network Flow with Dual Predictions

• URL: http://arxiv.org/abs/2601.20203v1
• Date: Wed, 28 Jan 2026 03:01:22 GMT
• Title: Minimum-Cost Network Flow with Dual Predictions
• Authors: Zhiyang Chen, Hailong Yao, Xia Yin,
• Abstract summary: We propose the first minimum-cost network flow algorithm augmented with a dual prediction.<n>Our method is based on a classic minimum-cost flow algorithm, namely $varepsilon$-relaxation.<n>We empirically validate our theoretical results on two applications of minimum-cost flow.
• Score: 4.90881413256913
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Recent work has shown that machine-learned predictions can provably improve the performance of classic algorithms. In this work, we propose the first minimum-cost network flow algorithm augmented with a dual prediction. Our method is based on a classic minimum-cost flow algorithm, namely $\varepsilon$-relaxation. We provide time complexity bounds in terms of the infinity norm prediction error, which is both consistent and robust. We also prove sample complexity bounds for PAC-learning the prediction. We empirically validate our theoretical results on two applications of minimum-cost flow, i.e., traffic networks and chip escape routing, in which we learn a fixed prediction, and a feature-based neural network model to infer the prediction, respectively. Experimental results illustrate $12.74\times$ and $1.64\times$ average speedup on two applications.

Related papers

• Generative Modeling with Continuous Flows: Sample Complexity of Flow Matching [60.37045080890305]
  We provide the first analysis of the sample complexity for flow-matching based generative models.<n>We decompose the velocity field estimation error into neural-network approximation error, statistical error due to the finite sample size, and optimization error due to the finite number of optimization steps for estimating the velocity field.
  arXiv  Detail & Related papers  (2025-12-01T05:14:25Z)
• How Reinforcement Learning After Next-Token Prediction Facilitates Learning [36.98696363889831]
  We study learning from mixture distributions of short and long chain-of-thought'' sequences encoding a single task.<n>We show how reinforcement learning after next-token prediction enables autoregressive transformers to generalize.
  arXiv  Detail & Related papers  (2025-10-13T15:04:00Z)
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions [19.537289123577022]
  We consider an online two-stage optimization with long-term constraints over a finite horizon of $T$ periods. We develop online algorithms for the online two-stage problem from adversarial learning algorithms.
  arXiv  Detail & Related papers  (2024-01-02T07:46:33Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Learning-Augmented Maximum Flow [3.0712335337791288]
  We propose a framework for speeding up maximum flow computation by using predictions. We present an algorithm that, given an $m$-edge flow network and a predicted flow, computes a maximum flow in $O(meta)$ time.
  arXiv  Detail & Related papers  (2022-07-26T14:02:41Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
  arXiv  Detail & Related papers  (2021-12-10T10:02:31Z)
• CPNet: Cross-Parallel Network for Efficient Anomaly Detection [20.84973451610082]
  Cross-Parallel Network (CPNet) for efficient anomaly detection is proposed here to minimize computations without performance drops. An inter-network shift module is incorporated to capture temporal relationships among sequential frames to enable more accurate future predictions.
  arXiv  Detail & Related papers  (2021-08-10T05:29:37Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  Modern machine learning models often employ a huge number of parameters and are typically optimized to have zero training loss. We examine how these benign overfitting phenomena occur in a two-layer neural network setting. We show that it is possible for the two-layer ReLU network interpolator to achieve a near minimax-optimal learning rate.
  arXiv  Detail & Related papers  (2021-06-06T19:08:53Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  We study a distributed variable for large-scale AUC for a neural network as with a deep neural network. Our model requires a much less number of communication rounds and still a number of communication rounds in theory. Our experiments on several datasets show the effectiveness of our theory and also confirm our theory.
  arXiv  Detail & Related papers  (2020-05-05T18:08:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.