More Like this

1. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra; Inamdar, Tanmay; Quanrud, Kent; Varadarajan, Kasturi; Zhang, Zhao (June 2022, Journal of Combinatorial Optimization)

   Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$ $f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$ $k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$ $S\subseteq N$such that$$f_i(S) \ge k_i$$ $f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$ $1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$ $O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$ $k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$ $(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$ $f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. 

   more » « less
2. Evolution of Magnetohydrodynamic Turbulence in the Expanding Solar Wind: Residual Energy and Intermittency

   https://doi.org/10.3847/1538-4357/ad9f38  

   Shi_时, Chen_辰; Sioulas, Nikos; Huang_黄, Zesen_泽森; Velli, Marco; Tenerani, Anna; Réville, Victor (January 2025, The Astrophysical Journal)

   Abstract We conduct 3D magnetohydrodynamic simulations of decaying turbulence in the context of the solar wind. To account for the spherical expansion of the solar wind, we implement the expanding box model. The initial turbulence comprises uncorrelated counterpropagating Alfvén waves and exhibits an isotropic power spectrum. Our findings reveal the consistent generation of negative residual energy whenever nonlinear interactions are present, independent of the normalized cross helicityσ_cand compressibility. The spherical expansion facilitates this process. The resulting residual energy is primarily distributed in the perpendicular direction, withS₂(b) − S₂(u) ∝ l_⊥or equivalently $-E_r\propto k_{\perp }^{-2}$. HereS₂(b) andS₂(u) are second-order structure functions of magnetic field and velocity respectively. In most runs,S₂(b) develops a scaling relation $S_2\left(\mathit{b}\right)\propto l_{\perp }^{1/2}$( $E_b\propto k_{\perp }^{-3/2}$). In contrast,S₂(u) is consistently shallower thanS₂(b), which aligns with in situ observations of the solar wind. We observe that the higher-order statistics of the turbulence, which act as a proxy for intermittency, depend on the initialσ_cand are strongly affected by the expansion effect. Generally, the intermittency is more pronounced when the expansion effect is present. Finally, we find that in our simulations, although the negative residual energy and intermittency grow simultaneously as the turbulence evolves, the causal relation between them seems to be weak, possibly because they are generated on different scales. 

   more » « less
3. Lower bounds for incidences

   https://doi.org/10.1007/s00222-025-01331-2  

   Cohen, Alex; Pohoata, Cosmin; Zakharov, Dmitrii (March 2025, Inventiones mathematicae)

   Abstract Let$$p_{1},\ldots ,p_{n}$$ $p_1,\dots ,p_n$be a set of points in the unit square and let$$T_{1},\ldots ,T_{n}$$ $T_1,\dots ,T_n$be a set of$$\delta $$ $\delta$-tubes such that$$T_{j}$$ $T_j$passes through$$p_{j}$$ $p_j$. We prove a lower bound for the number of incidences between the points and tubes under a natural regularity condition (similar to Frostman regularity). As a consequence, we show that in any configuration of points$$p_{1},\ldots , p_{n} \in [0,1]^{2}$$ $p_1,\dots ,p_n\in {[0,1]}^2$along with a line$$\ell _{j}$$ ${\ell }_j$through each point$$p_{j}$$ $p_j$, there exist$$j\neq k$$ $j\ne k$for which$$d(p_{j}, \ell _{k}) \lesssim n^{-2/3+o(1)}$$ $d(p_j,{\ell }_k)\lesssim n^{-2/3+o\left(1\right)}$. It follows from the latter result that any set of$$n$$ $n$points in the unit square contains three points forming a triangle of area at most$$n^{-7/6+o(1)}$$ $n^{-7/6+o\left(1\right)}$. This new upper bound for Heilbronn’s triangle problem attains the high-low limit established in our previous work arXiv:2305.18253. 

   more » « less
4. Bounds on eigenfunctions of quantum cat maps

   https://doi.org/10.1088/1402-4896/ad0331  

   Kim, Elena; Koirala, Robert (October 2023, Physica Scripta)

   Abstract We studyℓ^∞norms ofℓ²-normalized eigenfunctions of quantum cat maps. For maps with short quantum periods (constructed by Bonechi and de Biévre in F Bonechi and S De Bièvre (2000,Communications in Mathematical Physics,211, 659–686)) we show that there exists a sequence of eigenfunctionsuwith $\parallel u{\parallel }_{\infty }\gtrsim {\left(\log N\right)}^{-1/2}$. For general eigenfunctions we show the upper bound $\parallel u{\parallel }_{\infty }\lesssim {\left(\log N\right)}^{-1/2}$. Here the semiclassical parameter is $h={\left(2\pi N\right)}^{-1}$. Our upper bound is analogous to the one proved by Bérard in P Bérard (1977,Mathematische Zeitschrift,155, 249-276) for compact Riemannian manifolds without conjugate points. 

   more » « less
5. Acceleration and Spectral Redistribution of Cosmic Rays in Radio-jet Shear Flows

   https://doi.org/10.3847/1538-4357/acfda9  

   Webb, G. M.; Xu, Y.; Biermann, P. L.; Al-Nussirat, S.; Mostafavi, P.; Li, G.; Barghouty, A. F.; Zank, G. P. (November 2023, The Astrophysical Journal)

   Abstract A steady-state, semi-analytical model of energetic particle acceleration in radio-jet shear flows due to cosmic-ray viscosity obtained by Webb et al. is generalized to take into account more general cosmic-ray boundary spectra. This involves solving a mixed Dirichlet–Von Neumann boundary value problem at the edge of the jet. The energetic particle distribution functionf₀(r,p) at cylindrical radiusrfrom the jet axis (assumed to lie along thez-axis) is given by convolving the particle momentum spectrum $f_0(\infty ,p\prime )$with the Green’s function $G(r,p;p\prime )$, which describes the monoenergetic spectrum solution in which $f_0\to \delta (p-p\prime )$asr→ ∞ . Previous work by Webb et al. studied only the Green’s function solution for $G(r,p;p\prime )$. In this paper, we explore for the first time, solutions for more general and realistic forms for $f_0(\infty ,p\prime )$. The flow velocityu=u(r)e_zis along the axis of the jet (thez-axis).uis independent ofz, andu(r) is a monotonic decreasing function ofr. The scattering time $\tau {(r,p)={\tau }_0\left(p/p_0\right)}^{\alpha }$in the shear flow region 0 <r<r₂, and $\tau {(r,p)={\tau }_0\left(p/p_0\right)}^{\alpha }{\left(r/r_2\right)}^s$, wheres> 0 in the regionr>r₂is outside the jet. Other original aspects of the analysis are (i) the use of cosmic ray flow lines in (r,p) space to clarify the particle spatial transport and momentum changes and (ii) the determination of the probability distribution ${\psi }_p(r,p;p\prime )$that particles observed at (r,p) originated fromr→ ∞ with momentum $p\prime$. The acceleration of ultrahigh-energy cosmic rays in active galactic nuclei jet sources is discussed. Leaky box models for electron acceleration are described. 

   more » « less