Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Perturbation of tran ...
Conference paper

Perturbation of transportation polytopes

Fu Liu (1)
(1) Department of Mathematics [Univ California Davis]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2011
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Proceedings
DOI
10.46298/dmtcs.3097
License
https://about.hal.science/hal-authorisation-v1
Indicators
524
Views
578
Downloads

Perturbation of transportation polytopes

Fu Liu (1)
(1) Department of Mathematics [Univ California Davis]
Abstract
English
We describe a perturbation method that can be used to compute the multivariate generating function (MGF) of a non-simple polyhedron, and then construct a perturbation that works for any transportation polytope. Applying this perturbation to the family of central transportation polytopes of order $kn \times n$, we obtain formulas for the MGF of the polytope. The formulas we obtain are enumerated by combinatorial objects. A special case of the formulas recovers the results on Birkhoff polytopes given by the author and De Loera and Yoshida. We also recover the formula for the number of maximum vertices of transportation polytopes of order $kn \times n$.
French
Nous décrivons une méthode de perturbation qui peut être utilisée pour calculer la fonction génératrice multivariée (MGF) d'un polyèdre non-simple, et ensuite construire une perturbation qui fonctionne pour tout polytope de transport. Appliquant cette perturbation à la famille des centraux de transport polytopes de l'ordre $kn \times n$, nous obtenons des formules pour le MGF du polytope. Les formules que nous obtenons sont énumérées par les objets combinatoires. Un cas spécial des formules récupère les résultats sur des polytopes de Birkhoff donnés par l'auteur et De Loera et Yoshida. Nous récupérons également la formule pour le nombre de sommets maximum des de transport polytopes d'ordre $kn \times n$.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • transportation polytope
  • perturbation
  • multivariate generating function
Cited by

Source: OpenCitations

  • Computing with an algebraic-perturbation variant of Barvinok’s algorithm

    Discrete Applied Mathematics

    Authors : Jon Lee ORCID, Daphne Skipper ORCID

    Journal reference : Volume 240, 2015, pp. 63-77

    DOI : 10.1016/j.dam.2015.12.003
  • Plethysm and Lattice Point Counting

    arXiv (Cornell University)

    Authors : Thomas Kahle ORCID, Mateusz Michałek ORCID

    Journal reference : Volume 16, 2015, pp. 1241-1261

    DOI : 10.1007/s10208-015-9275-7
  • Quantum Walk on the Generalized Birkhoff Polytope Graph

    Entropy

    Authors : Rafael Cação, Lucas Cortez, Ismael de Farias, Ernee Kozyreff ORCID, Jalil Khatibi Moqadam ORCID, Renato Portugal ORCID

    Journal reference : Volume 23, 2021, pp. 1239

    DOI : 10.3390/e23101239
  • Polyhedral Omega: a New Algorithm for Solving Linear Diophantine Systems

    Annals of Combinatorics

    Authors : Felix Breuer, Zafeirakis Zafeirakopoulos ORCID

    Journal reference : Volume 21, 2017, pp. 211-280

    DOI : 10.1007/s00026-017-0349-x
Preview
Loading PDF preview...