Counting integer flows in networks

DOI10.1007/S10208-003-0088-8MaRDI QIDQ1767489zbMATH OpenOpenAlexFDO

Authors Michèle Vergne, Velleda Baldoni, Jesús A. De Loera

Publication date 11 March 2005

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0303228

zbMATH Keywords

Hyperplane arrangementsLattice pointsKostant partition functionTransportation problemsResiduesChambersFlow polytopesIntegral flowsRational function manipulation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Nonnumerical algorithms (68W05) Transportation, logistics and supply chain management (90B06) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Abstract: This paper discusses new analytic algorithms and software for the enumeration of all integer flows inside a network. Concrete applications abound in graph theory cite{Jaeger}, representation theory cite{kirillov}, and statistics cite{persi}. Our methods clearly surpass traditional exhaustive enumeration and other algorithms and can even yield formulas when the input data contains some parameters. These methods are based on the study of rational functions with poles on arrangements of hyperplanes.

Recommendations

• Approximately counting integral flows and cell-bounded contingency tables
• Effective lattice point counting in rational convex polytopes
• Réseaux et polynômes de dénombrement. (Networks and enumeration polynomials)
• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• scientific article; zbMATH DE number 5238759

Cited in

(24)

• Volumes and Ehrhart polynomials of flow polytopes
• A generating function for all semi-magic squares and the volume of the Birkhoff polytope
• Integer equal flows
• On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
• Computing Optimized Path Integrals for Knapsack Feasibility
• Paradan's wall crossing formula for partition functions and Khovanski-Pukhlikov differential operator
• Random sampling of contingency tables via probabilistic divide-and-conquer
• Quadratic Gröbner bases for smooth \(3\times 3\) transportation polytopes
• Brunn--Minkowski inequalities for contingency tables and integer flows
• Counting integer points of flow polytopes
• From generalized permutahedra to Grothendieck polynomials via flow polytopes
• Root cones and the resonance arrangement
• The number of nowhere-zero flows on graphs and signed graphs
• Chopped and sliced cones and representations of Kac-Moody algebras
• NUMBERS OF PRIMAL AND DUAL BASES OF NETWORK FLOW AND UNIMODULAR INTEGER PROGRAMS
• The many aspects of counting lattice points in polytopes
• Quasi-polynomials, linear Diophantine equations and semi-linear sets
• Enumerating Contingency Tables via Random Permanents
• An approximation algorithm for counting contingency tables
• Flow-oriented perturbation theory
• Low dimensional flow polytopes and their toric ideals
• Lower bounds for contingency tables via Lorentzian polynomials
• Computation of dilated Kronecker coefficients
• Kostant partitions functions and flow polytopes

This page was built for publication: Counting integer flows in networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1767489)