In this article, we consider the problems of finding in $d+1$ dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of $d$-dimensional unit-radius balls can be packed under translations. The computational problem is neither known to be NP-hard nor to be in NP. We give a constant-factor approximation algorithm for each of these containers based on a reduction to finding a shortest Hamiltonian path in a weighted graph, which in turn models the problem of stabbing the centers of the input balls while keeping them disjoint. We also show that for $n$ such balls, a container of volume $O(n^{\frac{d-1}{d}})$ is always sufficient and sometimes necessary. As a byproduct, this implies that for $d \geq 2$ there is no finite size $(d+1)$-dimensional convex body into which all $d$-dimensional unit-radius balls can be packed simultaneously.
相關內容
In this paper, we derive the improved uniform error bounds for the long-time dynamics of the $d$-dimensional $(d=2,3)$ nonlinear space fractional sine-Gordon equation (NSFSGE). The nonlinearity strength of the NSFSGE is characterized by $\varepsilon^2$ where $0<\varepsilon \le 1$ is a dimensionless parameter. The second-order time-splitting method is applied to the temporal discretization and the Fourier pseudo-spectral method is used for the spatial discretization. To obtain the explicit relation between the numerical errors and the parameter $\varepsilon$, we introduce the regularity compensation oscillation technique to the convergence analysis of fractional models. Then we establish the improved uniform error bounds $O\left(\varepsilon^2 \tau^2\right)$ for the semi-discretization scheme and $O\left(h^m+\varepsilon^2 \tau^2\right)$ for the full-discretization scheme up to the long time at $O(1/\varepsilon^2)$. Further, we extend the time-splitting Fourier pseudo-spectral method to the complex NSFSGE as well as the oscillatory complex NSFSGE, and the improved uniform error bounds for them are also given. Finally, extensive numerical examples in two-dimension or three-dimension are provided to support the theoretical analysis. The differences in dynamic behaviors between the fractional sine-Gordon equation and classical sine-Gordon equation are also discussed.
We describe a `discretize-then-relax' strategy to globally minimize integral functionals over functions $u$ in a Sobolev space subject to Dirichlet boundary conditions. The strategy applies whenever the integral functional depends polynomially on $u$ and its derivatives, even if it is nonconvex. The `discretize' step uses a bounded finite element scheme to approximate the integral minimization problem with a convergent hierarchy of polynomial optimization problems over a compact feasible set, indexed by the decreasing size $h$ of the finite element mesh. The `relax' step employs sparse moment-sum-of-squares relaxations to approximate each polynomial optimization problem with a hierarchy of convex semidefinite programs, indexed by an increasing relaxation order $\omega$. We prove that, as $\omega\to\infty$ and $h\to 0$, solutions of such semidefinite programs provide approximate minimizers that converge in a suitable sense (including in certain $L^p$ norms) to the global minimizer of the original integral functional if it is unique. We also report computational experiments showing that our numerical strategy works well even when technical conditions required by our theoretical analysis are not satisfied.
We propose a new concept of lifts of reversible diffusion processes and show that various well-known non-reversible Markov processes arising in applications are lifts in this sense of simple reversible diffusions. Furthermore, we introduce a concept of non-asymptotic relaxation times and show that these can at most be reduced by a square root through lifting, generalising a related result in discrete time. Finally, we demonstrate how the recently developed approach to quantitative hypocoercivity based on space-time Poincar\'e inequalities can be rephrased and simplified in the language of lifts and how it can be applied to find optimal lifts.
In this note we consider the problem of ParaTuck-2 decomposition of a three-way tensor.We provide an algebraic algorithm for finding the ParaTuck-2 decomposition for the case when the ParaTuck-2 ranks are smaller than the frontal dimensions of the tensors.Our approach relies only on linear algebra operations and is based on finding the kernel of a structured matrix constructed from the tensor.
In social choice theory with ordinal preferences, a voting method satisfies the axiom of positive involvement if adding to a preference profile a voter who ranks an alternative uniquely first cannot cause that alternative to go from winning to losing. In this note, we prove a new impossibility theorem concerning this axiom: there is no ordinal voting method satisfying positive involvement that also satisfies the Condorcet winner and loser criteria, resolvability, and a common invariance property for Condorcet methods, namely that the choice of winners depends only on the ordering of majority margins by size.
We prove explicit uniform two-sided bounds for the phase functions of Bessel functions and of their derivatives. As a consequence, we obtain new enclosures for the zeros of Bessel functions and their derivatives in terms of inverse values of some elementary functions. These bounds are valid, with a few exceptions, for all zeros and all Bessel functions with non-negative indices. We provide numerical evidence showing that our bounds either improve or closely match the best previously known ones.
In this paper, we develop a new type of Runge--Kutta (RK) discontinuous Galerkin (DG) method for solving hyperbolic conservation laws. Compared with the original RKDG method, the new method features improved compactness and allows simple boundary treatment. The key idea is to hybridize two different spatial operators in an explicit RK scheme, utilizing local projected derivatives for inner RK stages and the usual DG spatial discretization for the final stage only. Limiters are applied only at the final stage for the control of spurious oscillations. We also explore the connections between our method and Lax--Wendroff DG schemes and ADER-DG schemes. Numerical examples are given to confirm that the new RKDG method is as accurate as the original RKDG method, while being more compact, for problems including two-dimensional Euler equations for compressible gas dynamics.
In this paper, we present a novel class of high-order Runge--Kutta (RK) discontinuous Galerkin (DG) schemes for hyperbolic conservation laws. The new method extends beyond the traditional method of lines framework and utilizes stage-dependent polynomial spaces for the spatial discretization operators. To be more specific, two different DG operators, associated with $\mathcal{P}^k$ and $\mathcal{P}^{k-1}$ piecewise polynomial spaces, are used at different RK stages. The resulting method is referred to as the sdRKDG method. It features fewer floating-point operations and may achieve larger time step sizes. For problems without sonic points, we observe optimal convergence for all the sdRKDG schemes; and for problems with sonic points, we observe that a subset of the sdRKDG schemes remains optimal. We have also conducted von Neumann analysis for the stability and error of the sdRKDG schemes for the linear advection equation in one dimension. Numerical tests, for problems including two-dimensional Euler equations for gas dynamics, are provided to demonstrate the performance of the new method.
Motivated by the problem of matching two correlated random geometric graphs, we study the problem of matching two Gaussian geometric models correlated through a latent node permutation. Specifically, given an unknown permutation $\pi^*$ on $\{1,\ldots,n\}$ and given $n$ i.i.d. pairs of correlated Gaussian vectors $\{X_{\pi^*(i)},Y_i\}$ in $\mathbb{R}^d$ with noise parameter $\sigma$, we consider two types of (correlated) weighted complete graphs with edge weights given by $A_{i,j}=\langle X_i,X_j \rangle$, $B_{i,j}=\langle Y_i,Y_j \rangle$. The goal is to recover the hidden vertex correspondence $\pi^*$ based on the observed matrices $A$ and $B$. For the low-dimensional regime where $d=O(\log n)$, Wang, Wu, Xu, and Yolou [WWXY22+] established the information thresholds for exact and almost exact recovery in matching correlated Gaussian geometric models. They also conducted numerical experiments for the classical Umeyama algorithm. In our work, we prove that this algorithm achieves exact recovery of $\pi^*$ when the noise parameter $\sigma=o(d^{-3}n^{-2/d})$, and almost exact recovery when $\sigma=o(d^{-3}n^{-1/d})$. Our results approach the information thresholds up to a $\operatorname{poly}(d)$ factor in the low-dimensional regime.
Mendelian randomization uses genetic variants as instrumental variables to make causal inferences about the effects of modifiable risk factors on diseases from observational data. One of the major challenges in Mendelian randomization is that many genetic variants are only modestly or even weakly associated with the risk factor of interest, a setting known as many weak instruments. Many existing methods, such as the popular inverse-variance weighted (IVW) method, could be biased when the instrument strength is weak. To address this issue, the debiased IVW (dIVW) estimator, which is shown to be robust to many weak instruments, was recently proposed. However, this estimator still has non-ignorable bias when the effective sample size is small. In this paper, we propose a modified debiased IVW (mdIVW) estimator by multiplying a modification factor to the original dIVW estimator. After this simple correction, we show that the bias of the mdIVW estimator converges to zero at a faster rate than that of the dIVW estimator under some regularity conditions. Moreover, the mdIVW estimator has smaller variance than the dIVW estimator.We further extend the proposed method to account for the presence of instrumental variable selection and balanced horizontal pleiotropy. We demonstrate the improvement of the mdIVW estimator over the dIVW estimator through extensive simulation studies and real data analysis.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191