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. Global well-posedness for 2D generalized parabolic Anderson model via paracontrolled calculus

   https://doi.org/10.1007/s40072-025-00358-z  

   Shen, Hao; Zhu, Rongchan; Zhu, Xiangchan (May 2025, Stochastics and Partial Differential Equations: Analysis and Computations)

   Abstract This article revisits the problem of global well-posedness for the generalized parabolic Anderson model on$$\mathbb {R}^+\times \mathbb {T}^2$$ $R^{+}\times T^2$within the framework of paracontrolled calculus (Gubinelli et al. in Forum Math, 2015). The model is given by the equation:$$\begin{aligned} (\partial _t-\Delta ) u=F(u)\eta \end{aligned}$$ $\begin{array}{c}({\partial }_t-\Delta )u=F\left(u\right)\eta \end{array}$where$$\eta \in C^{-1-\kappa }$$ $\eta \in C^{-1-\kappa }$with$$1/6>\kappa >0$$ $1/6>\kappa >0$, and$$F\in C_b^2(\mathbb {R})$$ $F\in C_b^2\left(R\right)$. Assume that$$\eta \in C^{-1-\kappa }$$ $\eta \in C^{-1-\kappa }$and can be lifted to enhanced noise, we derive new a priori bounds. The key idea follows from the recent work by Chandra et al. (A priori bounds for 2-d generalised Parabolic Anderson Model,,2024), to represent the leading error term as a transport type term, and our techniques encompass the paracontrolled calculus, the maximum principle, and the localization approach (i.e. high-low frequency argument). 

   more » « less
3. Connection probabilities of multiple FK-Ising interfaces

   https://doi.org/10.1007/s00440-024-01269-1  

   Feng, Yu; Peltola, Eveliina; Wu, Hao (June 2024, Probability Theory and Related Fields)

   Abstract We find the scaling limits of a general class of boundary-to-boundary connection probabilities and multiple interfaces in the critical planar FK-Ising model, thus verifying predictions from the physics literature. We also discuss conjectural formulas using Coulomb gas integrals for the corresponding quantities in general critical planar random-cluster models with cluster-weight$${q \in [1,4)}$$ $q\in [1,4)$. Thus far, proofs for convergence, including ours, rely on discrete complex analysis techniques and are beyond reach for other values ofqthan the FK-Ising model ($$q=2$$ $q=2$). Given the convergence of interfaces, the conjectural formulas for other values ofqcould be verified similarly with relatively minor technical work. The limit interfaces are variants of$$\text {SLE}_\kappa $$ ${\text{SLE}}_{\kappa }$curves (with$$\kappa = 16/3$$ $\kappa =16/3$for$$q=2$$ $q=2$). Their partition functions, that give the connection probabilities, also satisfy properties predicted for correlation functions in conformal field theory (CFT), expected to describe scaling limits of critical random-cluster models. We verify these properties for all$$q \in [1,4)$$ $q\in [1,4)$, thus providing further evidence of the expected CFT description of these models. 

   more » « less
4. Hardness and approximation of submodular minimum linear ordering problems

   https://doi.org/10.1007/s10107-023-02038-z  

   Farhadi, Majid; Gupta, Swati; Sun, Shengding; Tetali, Prasad; Wigal, Michael C (December 2023, Mathematical Programming)

   Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ $f(·)$due to an ordering$$\sigma $$ $\sigma$of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma }{\sum }_{i\in \left[n\right]}f\left(E_{i,\sigma }\right)$, where$$E_{i,\sigma }$$ $E_{i,\sigma }$is the set of items mapped by$$\sigma $$ $\sigma$to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ $(2-\frac{1+{\ell }_f}{1+\left|E\right|})$-approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell }_f=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$satisfies$$1 \le \ell _f \le |E|$$ $1\le {\ell }_f\le \left|E\right|$. Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ $(2-\frac{1+r\left(E\right)}{1+\left|E\right|})$-approximation for the matroid MLOP, where$$f = r$$ $f=r$is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ $\frac{4}{3}$-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. 

   more » « less
5. Size dependence- and induced transformations- of fractional quantum Hall effects under tilted magnetic fields

   https://doi.org/10.1038/s41598-022-22812-x  

   Wijewardena, U. Kushan; Nanayakkara, Tharanga R.; Kriisa, Annika; Reichl, Christian; Wegscheider, Werner; Mani, Ramesh G. (November 2022, Scientific Reports)

   Abstract Two-dimensional electron systems subjected to high transverse magnetic fields can exhibit Fractional Quantum Hall Effects (FQHE). In the GaAs/AlGaAs 2D electron system, a double degeneracy of Landau levels due to electron-spin, is removed by a small Zeeman spin splitting,$$g \mu _B B$$ $g{\mu }_{B}B$, comparable to the correlation energy. Then, a change of the Zeeman splitting relative to the correlation energy can lead to a re-ordering between spin polarized, partially polarized, and unpolarized many body ground states at a constant filling factor. We show here that tuning the spin energy can produce fractionally quantized Hall effect transitions that include both a change in$$\nu$$ $\nu$for the$$R_{xx}$$ $R_{\mathrm{xx}}$minimum, e.g., from$$\nu = 11/7$$ $\nu =11/7$to$$\nu = 8/5$$ $\nu =8/5$, and a corresponding change in the$$R_{xy}$$ $R_{\mathrm{xy}}$, e.g., from$$R_{xy}/R_{K} = (11/7)^{-1}$$ $R_{\mathrm{xy}}/R_K={(11/7)}^{-1}$to$$R_{xy}/R_{K} = (8/5)^{-1}$$ $R_{\mathrm{xy}}/R_K={(8/5)}^{-1}$, with increasing tilt angle. Further, we exhibit a striking size dependence in the tilt angle interval for the vanishing of the$$\nu = 4/3$$ $\nu =4/3$and$$\nu = 7/5$$ $\nu =7/5$resistance minima, including “avoided crossing” type lineshape characteristics, and observable shifts of$$R_{xy}$$ $R_{\mathrm{xy}}$at the$$R_{xx}$$ $R_{\mathrm{xx}}$minima- the latter occurring for$$\nu = 4/3, 7/5$$ $\nu =4/3,7/5$and the 10/7. The results demonstrate both size dependence and the possibility, not just of competition between different spin polarized states at the same$$\nu$$ $\nu$and$$R_{xy}$$ $R_{\mathrm{xy}}$, but also the tilt- or Zeeman-energy-dependent- crossover between distinct FQHE associated with different Hall resistances. 

   more » « less