More Like this

1. Spherical convex hull of random points on a wedge

   https://doi.org/10.1007/s00208-023-02704-9  

   Besau, Florian ; Gusakova, Anna ; Reitzner, Matthias ; Schütt, Carsten ; Thäle, Christoph ; Werner, Elisabeth_M ( August 2023 , Mathematische Annalen)

   Consider two half-spaces$$H_1^+$$$H_1^{+}$and$$H_2^+$$$H_2^{+}$in$${\mathbb {R}}^{d+1}$$$R^{d+1}$whose bounding hyperplanes$$H_1$$$H_1$and$$H_2$$$H_2$are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$$S_{2,+}^d:=S^d\cap H_1^{+}\cap H_2^{+}$is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$$S^d$, which contains a great subsphere of dimension$$d-2$$$d-2$and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$$S_{2,+}^d$and consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$$logn$. A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$$S_{2,+}^d$. The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere.

    

   more » « less
2. From approximate to exact integer programming

   https://doi.org/10.1007/s10107-024-02084-1  

   Dadush, Daniel ; Eisenbrand, Friedrich ; Rothvoss, Thomas ( April 2024 , Mathematical Programming)

   Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$$K\subseteq R^n$, either determine whether$$K \cap {\mathbb {Z}}^n$$$K\cap Z^n$is empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$$2·(K-c)+c$which isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$$2^{O\left(n\right)}$while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$$2^{O\left(n\right)}·n^n$. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$x^* \in (K \cap {\mathbb {Z}}^n)$$$x^{\ast }\in (K\cap Z^n)$can be found in time$$2^{O(n)}$$$2^{O\left(n\right)}$, provided that theremaindersof each component$$x_i^* \mod \ell $$$x_i^{\ast }mod\ell$for some arbitrarily fixed$$\ell \ge 5(n+1)$$$\ell \ge 5(n+1)$of$$x^*$$$x^{\ast }$are given. The algorithm is based on acutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$$2^{O\left(n\right)}{n}^n$algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$$Ax=b,0\le x\le u,x\in Z^n$. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$${\prod }_{i}O(log{u}_i+1)$approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$$0\le x_i\le p\left(n\right)$can be solved in time$$(\log n)^{O(n)}$$${(logn)}^{O\left(n\right)}$. For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$$n^n·2^{O\left(n\right)}$.

    

   more » « less
3. $$\mathbf {2\times 2}$$-Convexifications for convex quadratic optimization with indicator variables

   https://doi.org/10.1007/s10107-023-01924-w  

   Han, Shaoning ; Gómez, Andrés ; Atamtürk, Alper ( January 2023 , Mathematical Programming)

   In this paper, we study the convex quadratic optimization problem with indicator variables. For the$${2\times 2}$$$2\times 2$case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the$${2\times 2}$$$2\times 2$case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including the optimal perspective relaxation and the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems.

    

   more » « less
4. Totally Symmetric Self-Complementary Plane Partition Matrices and Related Polytopes

   https://doi.org/10.1007/s00026-024-00723-0  

   Holmlund, Vincent ; Striker, Jessica ( November 2024 , Annals of Combinatorics)

   Plane partitions in the totally symmetric self-complementary symmetry class (TSSCPPs) are known to be equinumerous with$$n\times n$$$n\times n$alternating sign matrices, but no explicit bijection is known. In this paper, we give a bijection from these plane partitions to$$\{0,1,-1\}$$$\{0,1,-1\}$-matrices we call magog matrices, some of which are alternating sign matrices. We explore enumerative properties of these matrices related to natural statistics such as inversion number and number of negative ones. We then investigate the polytope defined as their convex hull. We show that all the magog matrices are extreme and give a partial inequality description. Finally, we define another TSSCPP polytope as the convex hull of TSSCPP boolean triangles and determine its dimension, inequalities, vertices, and facets.

    

   more » « less
5. Generalized Parking Function Polytopes

   https://doi.org/10.1007/s00026-023-00671-1  

   Hanada, Mitsuki ; Lentfer, John ; Vindas-Meléndez, Andrés_R ( November 2023 , Annals of Combinatorics)

   A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$$(a_1,a_2,\dots ,a_n)$whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$$b_1\le b_2\le \cdots \le b_n$satisfies$$b_i \le i$$$b_i\le i$. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$$R^n$, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$$x$-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$$x=(a,b,\cdots ,b)$, which we refer to as$${\textbf{x}}$$$x$-parking function polytopes. We explore connections between these$${\textbf{x}}$$$x$-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$$x$-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

    

   more » « less