Approximate integer programming is the following: For a given convex body
Consider two halfspaces
 NSFPAR ID:
 10446945
 Publisher / Repository:
 Springer Science + Business Media
 Date Published:
 Journal Name:
 Mathematische Annalen
 Volume:
 389
 Issue:
 3
 ISSN:
 00255831
 Format(s):
 Medium: X Size: p. 22892316
 Size(s):
 ["p. 22892316"]
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract , either determine whether$$K \subseteq {\mathbb {R}}^n$$ $K\subseteq {R}^{n}$ is empty, or find an integer point in the convex body$$K \cap {\mathbb {Z}}^n$$ $K\cap {Z}^{n}$ which is$$2\cdot (K  c) +c$$ $2\xb7(Kc)+c$K , scaled by 2 from its center of gravityc . Approximate integer programming can be solved in time while the fastest known methods for exact integer programming run in time$$2^{O(n)}$$ ${2}^{O\left(n\right)}$ . 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$$2^{O(n)} \cdot n^n$$ ${2}^{O\left(n\right)}\xb7{n}^{n}$ can be found in time$$x^* \in (K \cap {\mathbb {Z}}^n)$$ ${x}^{\ast}\in (K\cap {Z}^{n})$ , provided that the$$2^{O(n)}$$ ${2}^{O\left(n\right)}$remainders of each component for some arbitrarily fixed$$x_i^* \mod \ell $$ ${x}_{i}^{\ast}\phantom{\rule{0ex}{0ex}}mod\phantom{\rule{0ex}{0ex}}\ell $ of$$\ell \ge 5(n+1)$$ $\ell \ge 5(n+1)$ are given. The algorithm is based on a$$x^*$$ ${x}^{\ast}$cuttingplane 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 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 new$$2^{O(n)}n^n$$ ${2}^{O\left(n\right)}{n}^{n}$asymmetric approximate Carathéodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equationstandard form . Such a problem can be reduced to the solution of$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$ $Ax=b,0\le x\le u,\phantom{\rule{0ex}{0ex}}x\in {Z}^{n}$ approximate integer programming problems. This implies, for example that$$\prod _i O(\log u_i +1)$$ ${\prod}_{i}O(log{u}_{i}+1)$knapsack orsubsetsum problems withpolynomial variable range can be solved in time$$0 \le x_i \le p(n)$$ $0\le {x}_{i}\le p\left(n\right)$ . For these problems, the best running time so far was$$(\log n)^{O(n)}$$ ${(logn)}^{O\left(n\right)}$ .$$n^n \cdot 2^{O(n)}$$ ${n}^{n}\xb7{2}^{O\left(n\right)}$ 
Abstract Let
denote the standard Haar system on [0, 1], indexed by$$(h_I)$$ $\left({h}_{I}\right)$ , the set of dyadic intervals and$$I\in \mathcal {D}$$ $I\in D$ denote the tensor product$$h_I\otimes h_J$$ ${h}_{I}\otimes {h}_{J}$ ,$$(s,t)\mapsto h_I(s) h_J(t)$$ $(s,t)\mapsto {h}_{I}\left(s\right){h}_{J}\left(t\right)$ . We consider a class of twoparameter function spaces which are completions of the linear span$$I,J\in \mathcal {D}$$ $I,J\in D$ of$$\mathcal {V}(\delta ^2)$$ $V\left({\delta}^{2}\right)$ ,$$h_I\otimes h_J$$ ${h}_{I}\otimes {h}_{J}$ . This class contains all the spaces of the form$$I,J\in \mathcal {D}$$ $I,J\in D$X (Y ), whereX andY are either the Lebesgue spaces or the Hardy spaces$$L^p[0,1]$$ ${L}^{p}[0,1]$ ,$$H^p[0,1]$$ ${H}^{p}[0,1]$ . We say that$$1\le p < \infty $$ $1\le p<\infty $ is a Haar multiplier if$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$ , where$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$ $D({h}_{I}\otimes {h}_{J})={d}_{I,J}{h}_{I}\otimes {h}_{J}$ , and ask which more elementary operators factor through$$d_{I,J}\in \mathbb {R}$$ ${d}_{I,J}\in R$D . A decisive role is played by theCapon projection given by$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$ $C:V\left({\delta}^{2}\right)\to V\left({\delta}^{2}\right)$ if$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ $C{h}_{I}\otimes {h}_{J}={h}_{I}\otimes {h}_{J}$ , and$$I\le J$$ $\leftI\right\le \leftJ\right$ if$$\mathcal {C} h_I\otimes h_J = 0$$ $C{h}_{I}\otimes {h}_{J}=0$ , as our main result highlights: Given any bounded Haar multiplier$$I > J$$ $\leftI\right>\leftJ\right$ , there exist$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$ such that$$\lambda ,\mu \in \mathbb {R}$$ $\lambda ,\mu \in R$ i.e., for all$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}\mathcal {C})\text { approximately 1projectionally factors through }D, \end{aligned}$$ $\begin{array}{c}\lambda C+\mu (\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}C)\phantom{\rule{0ex}{0ex}}\text{approximately 1projectionally factors through}\phantom{\rule{0ex}{0ex}}D,\end{array}$ , there exist bounded operators$$\eta > 0$$ $\eta >0$A ,B so thatAB is the identity operator ,$${{\,\textrm{Id}\,}}$$ $\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}$ and$$\Vert A\Vert \cdot \Vert B\Vert = 1$$ $\Vert A\Vert \xb7\Vert B\Vert =1$ . Additionally, if$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}\mathcal {C})  ADB\Vert < \eta $$ $\Vert \lambda C+\mu (\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}C)ADB\Vert <\eta $ is unbounded on$$\mathcal {C}$$ $C$X (Y ), then and then$$\lambda = \mu $$ $\lambda =\mu $ either factors through$${{\,\textrm{Id}\,}}$$ $\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}$D or .$${{\,\textrm{Id}\,}}D$$ $\phantom{\rule{0ex}{0ex}}\text{Id}\phantom{\rule{0ex}{0ex}}D$ 
Abstract The repeating fast radio burst FRB 20190520B is localized to a galaxy at
z = 0.241, much closer than expected given its dispersion measure DM = 1205 ± 4 pc cm^{−3}. Here we assess implications of the large DM and scattering observed from FRB 20190520B for the host galaxy’s plasma properties. A sample of 75 bursts detected with the Fivehundredmeter Aperture Spherical radio Telescope shows scattering on two scales: a mean temporal delayτ (1.41 GHz) = 10.9 ± 1.5 ms, which is attributed to the host galaxy, and a mean scintillation bandwidth Δν _{d}(1.41 GHz) = 0.21 ± 0.01 MHz, which is attributed to the Milky Way. Balmer line measurements for the host imply an Hα emission measure (galaxy frame) EM_{s}= 620 pc cm^{−6}× (T /10^{4}K)^{0.9}, implying DM_{Hα}of order the value inferred from the FRB DM budget, pc cm^{−3}for plasma temperatures greater than the typical value 10^{4}K. Combining ${\mathrm{DM}}_{\mathrm{h}}={1121}_{138}^{+89}$τ and DM_{h}yields a nominal constraint on the scattering amplification from the host galaxy , where $\tilde{F}G\phantom{\rule{0.50em}{0ex}}=\phantom{\rule{0.50em}{0ex}}{1.5}_{0.3}^{+0.8}{({\mathrm{pc}}^{2}\phantom{\rule{0.25em}{0ex}}\mathrm{km})}^{1/3}$ describes turbulent density fluctuations and $\tilde{F}$G represents the geometric leverage to scattering that depends on the location of the scattering material. For a twoscreen scattering geometry whereτ arises from the host galaxy and Δν _{d}from the Milky Way, the implied distance between the FRB source and dominant scattering material is ≲100 pc. The host galaxy scattering and DM contributions support a novel technique for estimating FRB redshifts using theτ –DM relation, and are consistent with previous findings that scattering of localized FRBs is largely dominated by plasma within host galaxies and the Milky Way. 
Abstract A classical parking function of length
n is a list of positive integers whose nondecreasing rearrangement$$(a_1, a_2, \ldots , a_n)$$ $({a}_{1},{a}_{2},\dots ,{a}_{n})$ satisfies$$b_1 \le b_2 \le \cdots \le b_n$$ ${b}_{1}\le {b}_{2}\le \cdots \le {b}_{n}$ . The convex hull of all parking functions of length$$b_i \le i$$ ${b}_{i}\le i$n is ann dimensional polytope in , 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$${\mathbb {R}}^n$$ ${R}^{n}$ parking functions for$${\textbf{x}}$$ $x$ , which we refer to as$${\textbf{x}}=(a,b,\dots ,b)$$ $x=(a,b,\cdots ,b)$ 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 closedform 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 closedform expression for the volume of the convex hull of classical parking functions as a corollary.$${\textbf{x}}$$ $x$ 
For each odd integer
$n \geq 3$ , we construct a rank3 graph$\Lambda _n$ with involution$\gamma _n$ whose real$C^*$ algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)$ is stably isomorphic to the exotic Cuntz algebra$\mathcal E_n$ . This construction is optimal, as we prove that a rank2 graph with involution$(\Lambda ,\gamma )$ can never satisfy$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n$ , and Boersema reached the same conclusion for rank1 graphs (directed graphs) in [Münster J. Math.10 (2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank1 graph with involution$(\Lambda , \gamma )$ whose real$C^*$ algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )$ is stably isomorphic to the suspension$S \mathbb {R}$ . In the Appendix, we show that the$i$ fold suspension$S^i \mathbb {R}$ is stably isomorphic to a graph algebra iff$2 \leq i \leq 1$ .