Random Shadows of Fixed Polytopes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909221049597952 |
|---|---|
| author | Black, Alexander E. Criado, Francisco |
| author_facet | Black, Alexander E. Criado, Francisco |
| contents | Estimating the number of vertices of a two dimensional projection, called a shadow, of a polytope is a fundamental tool for understanding the performance of the shadow simplex method for linear programming among other applications. We prove multiple upper bounds on the expected number of vertices of a random shadow of a fixed polytope. Our bounds are in terms of various parameters in the literature including geometric diameter and edge lengths, minimal and maximal slack, maximal coordinates for lattice polytopes, and maximum absolute values of subdeterminants. For the case of geometric diameter and edge lengths, we prove lower bounds and argue that our upper and lower bounds are both tight for zonotopes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_06936 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Random Shadows of Fixed Polytopes Black, Alexander E. Criado, Francisco Combinatorics Optimization and Control 52B12, 52B55, 52A22 Estimating the number of vertices of a two dimensional projection, called a shadow, of a polytope is a fundamental tool for understanding the performance of the shadow simplex method for linear programming among other applications. We prove multiple upper bounds on the expected number of vertices of a random shadow of a fixed polytope. Our bounds are in terms of various parameters in the literature including geometric diameter and edge lengths, minimal and maximal slack, maximal coordinates for lattice polytopes, and maximum absolute values of subdeterminants. For the case of geometric diameter and edge lengths, we prove lower bounds and argue that our upper and lower bounds are both tight for zonotopes. |
| title | Random Shadows of Fixed Polytopes |
| topic | Combinatorics Optimization and Control 52B12, 52B55, 52A22 |
| url | https://arxiv.org/abs/2406.06936 |