ReLU neural networks of polynomial size for exact maximum flow computation
From MaRDI portal
Publication:6086001
DOI10.1007/978-3-031-32726-1_14zbMath1528.68357arXiv2102.06635OpenAlexW3198815479MaRDI QIDQ6086001
Leon Sering, Christoph Hertrich
Publication date: 9 November 2023
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2102.06635
minimum spanning tree problemmaximum flow problemstrongly polynomial algorithmsneural network expressivity
Programming involving graphs or networks (90C35) Artificial neural networks and deep learning (68T07) Deterministic network models in operations research (90B10)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A capable neural network model for solving the maximum flow problem
- Lower bounds for tropical circuits and dynamic programs
- ``Neural computation of decisions in optimization problems
- The maximum flow problem is log space complete for P
- Greedy can beat pure dynamic programming
- Machine learning for combinatorial optimization: a methodological tour d'horizon
- The modern mathematics of deep learning
- Neural networks with linear threshold activations: structure and algorithms
- Error bounds for approximations with deep ReLU networks
- On learning and branching: a survey
- Arithmetic Circuits: A survey of recent results and open questions
- A new approach to the maximum-flow problem
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research
- The Matching Polytope has Exponential Extension Complexity
- Neural Network Learning
- The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
- Network Flow Algorithms
- Max flows in O(nm) time, or better
- Approximation by superpositions of a sigmoidal function
- Combinatorial optimization. Theory and algorithms.
- Subtraction-free complexity, cluster transformations, and spanning trees
This page was built for publication: ReLU neural networks of polynomial size for exact maximum flow computation
