An official website of the United States government
In the Euclidean Steiner Tree problem, we are given as input a set of points (called terminals) in the $$\ell_2$$-metric space and the goal is to find the minimum-cost tree connecting them. Additional points (called Steiner points) from the space can be introduced as nodes in the solution. The seminal works of Arora [JACM'98] and Mitchell [SICOMP'99] provide a Polynomial Time Approximation Scheme (PTAS) for solving the Euclidean Steiner Tree problem in fixed dimensions. However, the problem remains poorly understood in higher dimensions (such as when the dimension is logarithmic in the number of terminals) and ruling out a PTAS for the problem in high dimensions is a notoriously long standing open problem (for example, see Trevisan [SICOMP'00]). Moreover, the explicit construction of optimal Steiner trees remains unknown for almost all well-studied high-dimensional point configurations. Furthermore, a vast majority the state-of-the-art structural results on (high-dimensional) Euclidean Steiner trees were established in the 1960s, with no noteworthy update in over half a century. In this paper, we revisit high-dimensional Euclidean Steiner trees, proving new structural results. We also establish a link between the computational hardness of the Euclidean Steiner Tree problem and understanding the optimal Steiner trees of regular simplices (and simplicial complexes), proposing several conjectures and showing that some of them suffice to resolve the status of the inapproximability of the Euclidean Steiner Tree problem. Motivated by this connection, we investigate optimal Steiner trees of regular simplices, proving new structural properties of their optimal Steiner trees, revisiting an old conjecture of Smith [Algorithmica'92] about their optimal topology, and providing the first explicit, general construction of candidate optimal Steiner trees for that topology.
more »
« less
General Affine Invariances Related to Mahler Volume
Abstract General affine invariances related to Mahler volume are introduced. We establish their affine isoperimetric inequalities by using a symmetrization scheme that involves a total of $2n$ elaborately chosen Steiner symmetrizations at a time. The necessity of this scheme, as opposed to the usual Steiner symmetrization, is demonstrated with an example (see the Appendix).
more »
« less
- Award ID(s):
- 2002778
- PAR ID:
- 10372228
- Publisher / Repository:
- Oxford University Press
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- Volume:
- 2022
- Issue:
- 18
- ISSN:
- 1073-7928
- Page Range / eLocation ID:
- p. 14151-14180
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We analyze the question of which motivic homotopy types admit smooth schemes as representatives. We show that given a pointed smooth affine scheme $$X$$ and an embedding into affine space, the affine deformation space of the embedding gives a model for the $${\mathbb P}^{1}$$ suspension of $$X$$; we also analyze a host of variations on this observation. Our approach yields many examples of $${\mathbb A}^{1}$$-$$(n-1)$-connected smooth affine $2n$-folds and strictly quasi-affine $${\mathbb A}^{1}$$-contractible smooth schemes.more » « less
-
Abstract We focus on the ferric end-member of phase H: ε-FeOOH using density functional theory at the PBEsol+U level. At 300 K, we find that ε-FeOOH undergoes a hydrogen bond symmetrization at 37 GPa and a sharp high-spin to low-spin transition at 45 GPa. We find excellent agreement with experimental measurements of the equation of state, lattice parameters, atomic positions, vibrational frequencies, and optical properties as related to the band gap, which we find to be finite and small, decreasing with pressure. The hydrogen bond symmetrization transition is neither first-nor second-order, with no discontinuity in volume or any of the elastic moduli. Computed IR and Raman frequencies and intensities show that vibrational spectroscopy may provide the best opportunity for locating the hydrogen bond symmetrization transition experimentally. We find that ε-FeOOH is highly anisotropic in both longitudinal- and shear-wave velocities at all pressures, with the shear wave velocity varying with propagation and polarization direction by as much as 24% at zero pressure and 43% at 46 GPa. The shear and bulk elastic moduli increase by 18% across the high-spin to low-spin transition.more » « less
-
Abstract The maximum independence number of Steiner triple systems of order is well‐known. Motivated by questions of access balancing in storage systems, we determine the maximum total cardinality of a pair of disjoint independent sets of Steiner triple systems of order for all admissible orders.more » « less
-
We prove the test function conjecture of Kottwitz and the first named author for local models of Shimura varieties with parahoric level structure attached to Weil-restricted groups, as defined by B. Levin. Our result covers the (modified) local models attached to all connected reductive groups over $$p$$ -adic local fields with $$p\geqslant 5$$ . In addition, we give a self-contained study of relative affine Grassmannians and loop groups formed using general relative effective Cartier divisors in a relative curve over an arbitrary Noetherian affine scheme.more » « less
