In this paper we investigate the existence of subexponential parameterized algorithms of three fundamental cycle-hitting problems in geometric graph classes. The considered problems, \textsc{Triangle Hitting} (TH), \textsc{Feedback Vertex Set} (FVS), and \textsc{Odd Cycle Transversal} (OCT) ask for the existence in a graph $G$ of a set $X$ of at most $k$ vertices such that $G-X$ is, respectively, triangle-free, acyclic, or bipartite. Such subexponential parameterized algorithms are known to exist in planar and even $H$-minor free graphs from bidimensionality theory [Demaine et al., JACM 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of "fat" objects ([Grigoriev et al., FOCS 2022] and [Lokshtanov et al., SODA 2022]). In this paper we focus on "thin" objects by considering intersection graphs of segments in the plane with $d$ possible slopes ($d$-DIR graphs) and contact graphs of segments in the plane. Assuming the ETH, we rule out the existence of algorithms: - solving TH in time $2^{o(n)}$ in 2-DIR graphs; and - solving TH, FVS, and OCT in time $2^{o(\sqrt{n})}$ in $K_{2,2}$-free contact 2-DIR graphs. These results indicate that additional restrictions are necessary in order to obtain subexponential parameterized algorithms for %these problems. In this direction we provide: - a $2^{O(k^{3/4}\cdot \log k)}n^{O(1)}$-time algorithm for FVS in contact segment graphs; - a $2^{O(\sqrt d\cdot t^2 \log t\cdot k^{2/3}\log k)} n^{O(1)}$-time algorithm for TH in $K_{t,t}$-free $d$-DIR graphs; and - a $2^{O(k^{7/9}\log^{3/2}k)} n^{O(1)}$-time algorithm for TH in contact segment graphs.
相關內容
In the present work, we consider multi-scale computation and convergence for nonlinear time-dependent thermo-mechanical equations of inhomogeneous shells possessing temperature-dependent material properties and orthogonal periodic configurations. The first contribution is that a novel higher-order macro-micro coupled computational model is rigorously devised via multi-scale asymptotic technique and Taylor series approach for high-accuracy simulation of heterogeneous shells. Benefitting from the higher-order corrected terms, the higher-order multi-scale computational model keeps the conservation of local energy and momentum for nonlinear thermo-mechanical simulation. Moreover, a global error estimation with explicit rate of higher-order multi-scale solutions is first derived in the energy norm sense. Furthermore, an efficient space-time numerical algorithm with off-line and on-line stages is presented in detail. Adequate numerical experiments are conducted to confirm the competitive advantages of the presented multi-scale approach, exhibiting not only the exceptional numerical accuracy, but also the less computational expense for heterogeneous shells.
In this paper, we introduce the flexible interpretable gamma (FIG) distribution which has been derived by Weibullisation of the body-tail generalised normal distribution. The parameters of the FIG have been verified graphically and mathematically as having interpretable roles in controlling the left-tail, body, and right-tail shape. The generalised gamma (GG) distribution has become a staple model for positive data in statistics due to its interpretable parameters and tractable equations. Although there are many generalised forms of the GG which can provide better fit to data, none of them extend the GG so that the parameters are interpretable. Additionally, we present some mathematical characteristics and prove the identifiability of the FIG parameters. Finally, we apply the FIG model to hand grip strength and insurance loss data to assess its flexibility relative to existing models.
We combine Kronecker products, and quantitative information flow, to give a novel formal analysis for the fine-grained verification of utility in complex privacy pipelines. The combination explains a surprising anomaly in the behaviour of utility of privacy-preserving pipelines -- that sometimes a reduction in privacy results also in a decrease in utility. We use the standard measure of utility for Bayesian analysis, introduced by Ghosh at al., to produce tractable and rigorous proofs of the fine-grained statistical behaviour leading to the anomaly. More generally, we offer the prospect of formal-analysis tools for utility that complement extant formal analyses of privacy. We demonstrate our results on a number of common privacy-preserving designs.
To minimize the average of a set of log-convex functions, the stochastic Newton method iteratively updates its estimate using subsampled versions of the full objective's gradient and Hessian. We contextualize this optimization problem as sequential Bayesian inference on a latent state-space model with a discriminatively-specified observation process. Applying Bayesian filtering then yields a novel optimization algorithm that considers the entire history of gradients and Hessians when forming an update. We establish matrix-based conditions under which the effect of older observations diminishes over time, in a manner analogous to Polyak's heavy ball momentum. We illustrate various aspects of our approach with an example and review other relevant innovations for the stochastic Newton method.
Ghost, or fictitious points allow to capture boundary conditions that are not located on the finite difference grid discretization. We explore in this paper the impact of ghost points on the stability of the explicit Euler finite difference scheme in the context of the diffusion equation. In particular, we consider the case of a one-touch option under the Black-Scholes model. The observations and results are however valid for a much wider range of financial contracts and models.
The distributed task allocation problem, as one of the most interesting distributed optimization challenges, has received considerable research attention recently. Previous works mainly focused on the task allocation problem in a population of individuals, where there are no constraints for affording task amounts. The latter condition, however, cannot always be hold. In this paper, we study the task allocation problem with constraints of task allocation in a game-theoretical framework. We assume that each individual can afford different amounts of task and the cost function is convex. To investigate the problem in the framework of population games, we construct a potential game and calculate the fitness function for each individual. We prove that when the Nash equilibrium point in the potential game is in the feasible solutions for the limited task allocation problem, the Nash equilibrium point is the unique globally optimal solution. Otherwise, we also derive analytically the unique globally optimal solution. In addition, in order to confirm our theoretical results, we consider the exponential and quadratic forms of cost function for each agent. Two algorithms with the mentioned representative cost functions are proposed to numerically seek the optimal solution to the limited task problems. We further perform Monte Carlo simulations which provide agreeing results with our analytical calculations.
In this paper we develop a numerical method for efficiently approximating solutions of certain Zakai equations in high dimensions. The key idea is to transform a given Zakai SPDE into a PDE with random coefficients. We show that under suitable regularity assumptions on the coefficients of the Zakai equation, the corresponding random PDE admits a solution random field which, for almost all realizations of the random coefficients, can be written as a classical solution of a linear parabolic PDE. This makes it possible to apply the Feynman--Kac formula to obtain an efficient Monte Carlo scheme for computing approximate solutions of Zakai equations. The approach achieves good results in up to 25 dimensions with fast run times.
In this paper, we study a numerical artifact of solving the nonlinear shallow water equations with a discontinuous bottom topography. For various first-order schemes, the numerical solution of the momentum will form a spurious spike at the discontinuous points of the bottom, which should not exist in the exact solution. The height of the spike cannot be reduced even after the mesh is refined. For subsonic problems, this numerical artifact may cause the wrong convergence to a function far away from the exact solution. To explain the formation of the spurious spike, we perform a convergence analysis by proving a Lax--Wendroff type theorem. It is shown that the spurious spike is caused by the numerical viscosity in the computation of the water height at the discontinuous bottom. The height of the spike is proportional to the magnitude of the viscosity constant in the Lax--Friedrichs flux. Motivated by this conclusion, we propose a modified scheme by adopting the central flux at the bottom discontinuity in the equation of mass conservation, and show that this numerical artifact can be removed in many cases. For various numerical tests with nontransonic Riemann solutions, we observe that the modified scheme is able to retrieve the correct convergence.
This paper develops power series expansions of a general class of moment functions, including transition densities and option prices, of continuous-time Markov processes, including jump--diffusions. The proposed expansions extend the ones in Kristensen and Mele (2011) to cover general Markov processes. We demonstrate that the class of expansions nests the transition density and option price expansions developed in Yang, Chen, and Wan (2019) and Wan and Yang (2021) as special cases, thereby connecting seemingly different ideas in a unified framework. We show how the general expansion can be implemented for fully general jump--diffusion models. We provide a new theory for the validity of the expansions which shows that series expansions are not guaranteed to converge as more terms are added in general. Thus, these methods should be used with caution. At the same time, the numerical studies in this paper demonstrate good performance of the proposed implementation in practice when a small number of terms are included.
This paper focuses on investigating the density convergence of a fully discrete finite difference method when applied to numerically solve the stochastic Cahn--Hilliard equation driven by multiplicative space-time white noises. The main difficulty lies in the control of the drift coefficient that is neither globally Lipschitz nor one-sided Lipschitz. To handle this difficulty, we propose a novel localization argument and derive the strong convergence rate of the numerical solution to estimate the total variation distance between the exact and numerical solutions. This along with the existence of the density of the numerical solution finally yields the convergence of density in $L^1(\mathbb{R})$ of the numerical solution. Our results partially answer positively to the open problem emerged in [J. Cui and J. Hong, J. Differential Equations (2020)] on computing the density of the exact solution numerically.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191