More Like this

1. A deterministic near-linear time approximation scheme for geometric transportation

   https://doi.org/10.1109/FOCS57990.2023.00078  

   Fox, Emily ; Lu, Jiashuai ( November 2023 , IEEE)

   Given a set of points $P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$ for some constant $d$ and a supply function $\mu:P\to \mathbb{R}$ such that $\mu(p) > 0~\forall p \in P^+$, $\mu(p) < 0~\forall p \in P^-$, and $\sum_{p\in P}{\mu(p)} = 0$, the geometric transportation problem asks one to find a transportation map $\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$ such that $\sum_{q\in P^-}{\tau(p, q)} = \mu(p)~\forall p \in P^+$, $\sum_{p\in P^+}{\tau(p, q)} = -\mu(q) \forall q \in P^-$, and the weighted sum of Euclidean distances for the pairs $\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $(1 + \varepsilon)$ factor of optimal. More precisely, our algorithm runs in $O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$ time for any constant $\varepsilon > 0$. While a randomized $n\varepsilon^{-O(d)}\log^{O(d)}{n}$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $(1 + \varepsilon)$-approximation algorithms run in~$\Omega(n^{3/2})$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $n\varepsilon^{-O(d)}\log^{O(d)}{n}$ time $(1 + \varepsilon)$-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $(1 + \varepsilon)$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $(1 + \varepsilon)$-approximate deterministic algorithm for geometric bipartite matching and the first $(1 + \varepsilon)$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $d$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $O(\varepsilon^{-2} m \log^{O(1)} n)$ time $(1 + \varepsilon)$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary \emph{real} edge costs. 

   more » « less
2. A simple proof of reflexivity and separability of N^{1,p} Sobolev spaces

   https://doi.org/10.54330/afm.127419  

   Alvarado, Ryan ; Hajłasz, Piotr ; Malý, Lukáš ( October 2022 , Annales Fennici Mathematici)

   We present an elementary proof of a well-known theorem of Cheeger which states that if a metric-measure space \(X\) supports a \(p\)-Poincaré inequality, then the \(N^{1,p}(X)\) Sobolev space is reflexive and separable whenever \(p\in (1,\infty)\). We also prove separability of the space when \(p=1\). Our proof is based on a straightforward construction of an equivalent norm on \(N^{1,p}(X)\), \(p\in [1,\infty)\), that is uniformly convex when \(p\in (1,\infty)\). Finally, we explicitly construct a functional that is pointwise comparable to the minimal \(p\)-weak upper gradient, when \(p\in (1,\infty)\). 

   more » « less
3. Panmixia in spiders ( Mecaphesa celer , Thomisidae) despite fragmented habitat at Craters of the Moon in Idaho

   https://doi.org/10.1111/een.13149  

   Peterson, Katie ; Hendricks, Sarah ; Hohenlohe, Paul ; Parent, Christine_E ( April 2022 , Ecological Entomology)

   A fragmented landscape, which contains a patchwork of vegetated hospitable areas and a barren intervening matrix, may reduce gene flow in a population and over time result in an increase in population structure.

   We tested this prediction in crab spiders (Mecaphesa celer(Hentz, 1847)) inhabiting isolated habitat patches in the lava matrix of Craters of the Moon National Monument and Preserve, Idaho, USA.

   Using reduced‐representation genomic sequencing, we did not find evidence of population structure due to a reduction in gene flow among habitat patches.

   Instead, our results show strong evidence of panmixia likely due to abundant juvenile dispersal and possible connectivity to outer regions surrounding the lava flows despite the species' habitat specificity.

    

   more » « less
4. A brief report on the effects of vasoactive agents on peripheral venous waveforms in a porcine model

   https://doi.org/10.1177/2048004020940857  

   Polcz, Monica ; Hocking, Kyle_M ; Chang, Devin ; Leisy, Philip ; Sobey, Jenna_H ; Huston, Jessica ; Eagle, Susan ; Brophy, Colleen ; Alvis, Bret_D ( August 2020 , JRSM Cardiovascular Disease)

   Non-invasive venous waveform analysis (NIVA) is a recently described, novel technique to assess intravascular volume status. Waveforms are captured with a piezoelectric sensor; analysis in the frequency domain allows for calculation of a “NIVA value” that represents volume status. The aim of this report was to determine the effects of vasoactive agents on the venous waveform and calculated NIVA values.

   Porcine experimental model.

   Operating theatre.

   A piezoelectric sensor was secured over the surgically exposed saphenous vein in eight anesthetized pigs.

   NIVA value, pulmonary capillary wedge pressure (PCWP), and mean arterial pressure prior to and post intravenous administration of 150–180 µg of phenylephrine or 100 µg of sodium nitroprusside.

   Phenylephrine led to a decrease in NIVA value (mean 9.2 vs. 4.6, p < 0.05), while sodium nitroprusside led to an increase in NIVA value (mean 9.5 vs. 11.9, p < 0.05). Mean arterial pressure increased after phenylephrine ( p < 0.05) and decreased after sodium nitroprusside ( p < 0.05). PCWP did not change significantly after phenylephrine ( p = 0.25) or sodium nitroprusside ( p = 0.06).

   Vasoactive agents lead to changes in non-invasively obtained venous waveforms in euvolemic pigs, highlighting a potential limitation in the ability to NIVA to estimate static volume in this setting. Further studies are indicated to understand the effects of vasoactive agents in the setting of hypovolemia and hypervolemia.

    

   more » « less
5. Photosynthetic reaction center variants made via genetic code expansion show Tyr at M210 tunes the initial electron transfer mechanism

   https://doi.org/10.1073/pnas.2116439118  

   Weaver, Jared Bryce ; Lin, Chi-Yun ; Faries, Kaitlyn M. ; Mathews, Irimpan I. ; Russi, Silvia ; Holten, Dewey ; Kirmaier, Christine ; Boxer, Steven G. ( December 2021 , Proceedings of the National Academy of Sciences)

   Photosynthetic reaction centers (RCs) from Rhodobacter sphaeroides were engineered to vary the electronic properties of a key tyrosine (M210) close to an essential electron transfer component via its replacement with site-specific, genetically encoded noncanonical amino acid tyrosine analogs. High fidelity of noncanonical amino acid incorporation was verified with mass spectrometry and X-ray crystallography and demonstrated that RC variants exhibit no significant structural alterations relative to wild type (WT). Ultrafast transient absorption spectroscopy indicates the excited primary electron donor, P*, decays via a ∼4-ps and a ∼20-ps population to produce the charge-separated state P + H A − in all variants. Global analysis indicates that in the ∼4-ps population, P + H A − forms through a two-step process, P*→ P + B A − → P + H A − , while in the ∼20-ps population, it forms via a one-step P* → P + H A − superexchange mechanism. The percentage of the P* population that decays via the superexchange route varies from ∼25 to ∼45% among variants, while in WT, this percentage is ∼15%. Increases in the P* population that decays via superexchange correlate with increases in the free energy of the P + B A − intermediate caused by a given M210 tyrosine analog. This was experimentally estimated through resonance Stark spectroscopy, redox titrations, and near-infrared absorption measurements. As the most energetically perturbative variant, 3-nitrotyrosine at M210 creates an ∼110-meV increase in the free energy of P + B A − along with a dramatic diminution of the 1,030-nm transient absorption band indicative of P + B A – formation. Collectively, this work indicates the tyrosine at M210 tunes the mechanism of primary electron transfer in the RC. 

   more » « less