More Like this

1. 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
2. Lp quasi-norm minimization: algorithm and applications

   https://doi.org/10.1186/s13634-024-01114-6  

   Sleem, Omar M. ; Ashour, M. E. ; Aybat, N. S. ; Lagoa, Constantino M. ( February 2024 , EURASIP Journal on Advances in Signal Processing)

   Sparsity finds applications in diverse areas such as statistics, machine learning, and signal processing. Computations over sparse structures are less complex compared to their dense counterparts and need less storage. This paper proposes a heuristic method for retrieving sparse approximate solutions of optimization problems via minimizing the$$\ell _{p}$$${\ell }_p$quasi-norm, where$$0$0<p<1$. An iterative two-block algorithm for minimizing the$$\ell _{p}$$${\ell }_p$quasi-norm subject to convex constraints is proposed. The proposed algorithm requires solving for the roots of a scalar degree polynomial as opposed to applying a soft thresholding operator in the case of$$\ell _{1}$$${\ell }_1$norm minimization. The algorithm’s merit relies on its ability to solve the$$\ell _{p}$$${\ell }_p$quasi-norm minimization subject to any convex constraints set. For the specific case of constraints defined by differentiable functions with Lipschitz continuous gradient, a second, faster algorithm is proposed. Using a proximal gradient step, we mitigate the convex projection step and hence enhance the algorithm’s speed while proving its convergence. We present various applications where the proposed algorithm excels, namely, sparse signal reconstruction, system identification, and matrix completion. The results demonstrate the significant gains obtained by the proposed algorithm compared to other$$\ell _{p}$$${\ell }_p$quasi-norm based methods presented in previous literature.

    

   more » « less
3. Measurement of the mass dependence of the transverse momentum of lepton pairs in Drell–Yan production in proton–proton collisions at $$\sqrt{s} = 13\,\text {Te\hspace{-.08em}V} $$

   https://doi.org/10.1140/epjc/s10052-023-11631-7  

   Tumasyan, A. ; Adam, W. ; Andrejkovic, J. W. ; Bergauer, T. ; Chatterjee, S. ; Dragicevic, M. ; Valle, A. Escalante ; Frühwirth, R. ; Jeitler, M. ; Krammer, N. ; et al ( July 2023 , The European Physical Journal C)

   The double differential cross sections of the Drell–Yan lepton pair ($$\ell ^+\ell ^-$$${\ell }^{+}{\ell }^{-}$, dielectron or dimuon) production are measured as functions of the invariant mass$$m_{\ell \ell }$$$m_{\ell \ell }$, transverse momentum$$p_{\textrm{T}} (\ell \ell )$$$p_{\text{T}}\left(\ell \ell \right)$, and$$\varphi ^{*}_{\eta }$$${\phi }_{\eta }^{\ast }$. The$$\varphi ^{*}_{\eta }$$${\phi }_{\eta }^{\ast }$observable, derived from angular measurements of the leptons and highly correlated with$$p_{\textrm{T}} (\ell \ell )$$$p_{\text{T}}\left(\ell \ell \right)$, is used to probe the low-$$p_{\textrm{T}} (\ell \ell )$$$p_{\text{T}}\left(\ell \ell \right)$region in a complementary way. Dilepton masses up to 1$$\,\text {Te\hspace{-.08em}V}$$$\text{Te}\text{V}$are investigated. Additionally, a measurement is performed requiring at least one jet in the final state. To benefit from partial cancellation of the systematic uncertainty, the ratios of the differential cross sections for various$$m_{\ell \ell }$$$m_{\ell \ell }$ranges to those in the Z mass peak interval are presented. The collected data correspond to an integrated luminosity of 36.3$$\,\text {fb}^{-1}$$${\text{fb}}^{-1}$of proton–proton collisions recorded with the CMS detector at the LHC at a centre-of-mass energy of 13$$\,\text {Te\hspace{-.08em}V}$$$\text{Te}\text{V}$. Measurements are compared with predictions based on perturbative quantum chromodynamics, including soft-gluon resummation.

    

   more » « less
4. Search for Higgs boson pair production in association with a vector boson in pp collisions at $$\sqrt{s}=13\,\text {TeV}$$ with the ATLAS detector

   https://doi.org/10.1140/epjc/s10052-023-11559-y  

   Aad, G. ; Abbott, B. ; Abbott, D. C. ; Abeling, K. ; Abidi, S. H. ; Aboulhorma, A. ; Abramowicz, H. ; Abreu, H. ; Abulaiti, Y. ; Hoffman, A. C. ; et al ( June 2023 , The European Physical Journal C)

   This paper reports a search for Higgs boson pair (hh) production in association with a vector boson ($$W\; {\text {o}r}\; Z$$$W\text{o}rZ$) using 139 fb$$^{-1}$$${}^{-1}$of proton–proton collision data at$$\sqrt{s}=13\,\text {TeV}$$$\sqrt{s}=13\text{TeV}$recorded with the ATLAS detector at the Large Hadron Collider. The search is performed in final states in which the vector boson decays leptonically ($$W\rightarrow \ell \nu ,\, Z\rightarrow \ell \ell ,\nu \nu $$$W\to \ell \nu ,Z\to \ell \ell ,\nu \nu$with$$\ell =e, \mu $$$\ell =e,\mu$) and the Higgs bosons each decay into a pair ofb-quarks. It targetsVhhsignals from both non-resonanthhproduction, present in the Standard Model (SM), and resonanthhproduction, as predicted in some SM extensions. A 95% confidence-level upper limit of 183 (87) times the SM cross-section is observed (expected) for non-resonantVhhproduction when assuming the kinematics are as expected in the SM. Constraints are also placed on Higgs boson coupling modifiers. For the resonant search, upper limits on the production cross-sections are derived for two specific models: one is the production of a vector boson along with a neutral heavy scalar resonanceH, in the mass range 260–1000 GeV, that decays intohh, and the other is the production of a heavier neutral pseudoscalar resonanceAthat decays into aZboson andHboson, where theAboson mass is 360–800 GeV and theHboson mass is 260–400 GeV. Constraints are also derived in the parameter space of two-Higgs-doublet models.

    

   more » « less
5. Sparse representation of vectors in lattices and semigroups

   https://doi.org/10.1007/s10107-021-01657-8  

   Aliev, Iskander ; Averkov, Gennadiy ; De Loera, Jesús A. ; Oertel, Timm ( May 2021 , Mathematical Programming)

   We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the$$\ell _0$$${\ell }_0$-norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$${\ell }_0$-norm of solutions to systems$$A\varvec{x}=\varvec{b}$$$Ax=b$, where$$A\in \mathbb {Z}^{m\times n}$$$A\in Z^{m\times n}$,$${\varvec{b}}\in \mathbb {Z}^m$$$b\in Z^m$and$$\varvec{x}$$$x$is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\ell _0$$${\ell }_0$-norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\mathbb {R}$$$R$, to other subdomains such as$$\mathbb {Z}$$$Z$. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.

    

   more » « less