More Like this

1. On a Traveling Salesman Problem for Points in the Unit Cube

   https://doi.org/10.1007/s00453-024-01257-w  

   Balogh, József; Clemen, Felix Christian; Dumitrescu, Adrian (September 2024, Algorithmica)

   Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ ${[0,1]}^k$where$$k \ge 2$$ $k\ge 2$. According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$ $x_1,x_2,\dots ,x_n$through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}\le c_k$, where$$|x-y|$$ $|x-y|$is the Euclidean distance betweenxandy, and$$c_k$$ $c_k$is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ $x_{n+1}\equiv x_1$. From the other direction, for every$$k \ge 2$$ $k\ge 2$and$$n \ge 2$$ $n\ge 2$, there existnpoints in$$[0,1]^k$$ ${[0,1]}^k$, such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}=2^{1/k}·\sqrt{k}$. For the plane, the best constant is$$c_2=2$$ $c_2=2$and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=9{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$for every$$k \ge 3$$ $k\ge 3$and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ $c_k=2^{1/k}·\sqrt{k}$, for every$$k \ge 2$$ $k\ge 2$. Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=3\sqrt{5}{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ $c_k=2.91\sqrt{k}(1+o_k\left(1\right))$. Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ $c_3\ge 2^{7/6}$, which disproves the conjecture for$$k=3$$ $k=3$. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. 

   more » « less
2. 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)

   Abstract 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
3. Measurement of the branching fractions of $$ \overline{B} $$ → D(*)K−$$ {K}_{(S)}^{\left(\ast \right)0} $$ and $$ \overline{B} $$ → D(*)$$ {D}_s^{-} $$ decays at Belle II

   https://doi.org/10.1007/JHEP08(2024)206  

   Adachi, I; Aggarwal, L; Aihara, H; Akopov, N; Aloisio, A; Althubiti, N; Anh_Ky, N; Asner, D M; Atmacan, H; Aushev, T; et al (August 2024, Journal of High Energy Physics)

   Abstract We present measurements of the branching fractions of eight$$ {\overline{B}}^0 $$ ${\overline{B}}^0$→D^(*)+K⁻$$ {K}_{(S)}^{\left(\ast \right)0} $$ $K_{\left(S\right)}^{\left(\ast \right)0}$,B⁻→D^(*)0K⁻$$ {K}_{(S)}^{\left(\ast \right)0} $$ $K_{\left(S\right)}^{\left(\ast \right)0}$decay channels. The results are based on data from SuperKEKB electron-positron collisions at the Υ(4S) resonance collected with the Belle II detector, corresponding to an integrated luminosity of 362 fb⁻¹. The event yields are extracted from fits to the distributions of the difference between expected and observedBmeson energy, and are efficiency-corrected as a function ofm(K⁻$$ {K}_{(S)}^{\left(\ast \right)0} $$ $K_{\left(S\right)}^{\left(\ast \right)0}$) andm(D^(*)$$ {K}_{(S)}^{\left(\ast \right)0} $$ $K_{\left(S\right)}^{\left(\ast \right)0}$) in order to avoid dependence on the decay model. These results include the first observation of$$ {\overline{B}}^0 $$ ${\overline{B}}^0$→D⁺K⁻$$ {K}_S^0 $$ $K_S^0$,B⁻→D*⁰K⁻$$ {K}_S^0 $$ $K_S^0$, and$$ {\overline{B}}^0 $$ ${\overline{B}}^0$→D*⁺K⁻$$ {K}_S^0 $$ $K_S^0$decays and a significant improvement in the precision of the other channels compared to previous measurements. The helicity-angle distributions and the invariant mass distributions of theK⁻$$ {K}_{(S)}^{\left(\ast \right)0} $$ $K_{\left(S\right)}^{\left(\ast \right)0}$systems are compatible with quasi-two-body decays via a resonant transition with spin-parityJ^P= 1⁻for theK⁻$$ {K}_S^0 $$ $K_S^0$systems andJ^P= 1⁺for theK⁻K*⁰systems. We also present measurements of the branching fractions of four$$ {\overline{B}}^0 $$ ${\overline{B}}^0$→D^(*)+$$ {D}_s^{-} $$ $D_s^{-}$,B⁻→D^(*)0$$ {D}_s^{-} $$ $D_s^{-}$decay channels with a precision compatible to the current world averages. 

   more » « less
4. Controllable deformations in compressible isotropic implicit elasticity

   https://doi.org/10.1007/s00033-024-02305-9  

   Yavari, Arash; Goriely, Alain (August 2024, Zeitschrift für angewandte Mathematik und Physik)

   Abstract For a given material,controllable deformationsare those deformations that can be maintained in the absence of body forces and by applying only boundary tractions. For a given class of materials,universal deformationsare those deformations that are controllable for any material within the class. In this paper, we characterize the universal deformations in compressible isotropic implicit elasticity defined by solids whose constitutive equations, in terms of the Cauchy stress$$\varvec{\sigma }$$ $\sigma$and the left Cauchy-Green strain$$\textbf{b}$$ $b$, have the implicit form$$\varvec{\textsf{f}}(\varvec{\sigma },\textbf{b})=\textbf{0}$$ $f(\sigma ,b)=0$. We prove that universal deformations are homogeneous. However, an important observation is that, unlike Cauchy (and Green) elasticity, not every homogeneous deformation is constitutively admissible for a given implicit-elastic solid. In other words, the set of universal deformations is material-dependent, yet it remains a subset of homogeneous deformations. 

   more » « less
5. A folding preprocess for the max k-cut problem

   https://doi.org/10.1007/s11590-025-02199-0  

   Fakhimi, Ramin; Validi, Hamidreza; Hicks, Illya_V; Terlaky, Tamás; Zuluaga, Luis_F (April 2025, Optimization Letters)

   Abstract Given graph$$G=(V,E)$$ $G=(V,E)$with vertex setVand edge setE, the maxk-cut problem seeks to partition the vertex setVinto at mostksubsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number of the vertices and edges of graphG) for the weighted maxk-cut problem that may help reduce the problem’s dimensionality. While our theoretical results hold for any$$k \ge 2$$ $k\ge 2$, our computational results show the effectiveness of the proposed preprocessonlyfor$$k=2$$ $k=2$and on two sets of instances. Furthermore, we observe that the preprocess improves the performance of a MIP solver on a set of large-scale instances of the max cut problem. 

   more » « less