Polytope volume by descent in the face lattice and applications in social choice

We describe the computation of polytope volumes by descent in the face lattice, its implementation in Normaliz, and the connection to reverse-lexicographic triangulations. The efficiency of the algorithm is demonstrated by several high dimensional polytopes of different characteristics. Finally, we...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming computation 2021-06, Vol.13 (2), p.415-442
Main Authors: Bruns, Winfried, Ichim, Bogdan
Format: Article
Language:English
Subjects:
Algorithms
Full Length Paper
Mathematics
Mathematics and Statistics
Mathematics of Computing
Operations Research/Decision Theory
Optimization
Polytopes
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe the computation of polytope volumes by descent in the face lattice, its implementation in Normaliz, and the connection to reverse-lexicographic triangulations. The efficiency of the algorithm is demonstrated by several high dimensional polytopes of different characteristics. Finally, we present an application to voting theory where polytope volumes appear as probabilities of certain paradoxa.
ISSN:1867-2949
1867-2957
DOI:10.1007/s12532-020-00198-z