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

ChambersFlow polytopesHyperplane arrangementsIntegral flowsKostant partition functionLattice pointsRational function manipulationResiduesTransportation problems

Mathematics Subject Classification ID

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

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

(27)

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