We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in the graph are covered. The problem is called the k-partial vertex cover problem. There are some 2-approximation algorithms for the problem. In the paper we do not improve on the approximation ratios of the previous algorithms, but we derive an iterative rounding algorithm. We present our technique in two algorithms. The first is an iterative rounding algorithm and gives a (2 + Q/OPT)-approximation for the k-partial vertex cover problem where Q is the largest finite weight in the problem definition and OPT is the optimal value for the instance. The second algorithm uses the first as a subroutine and achieves an approximation ratio of 2.
Prior empirical studies find positive and negative momentum effect across the global nations, but few focus on explaining the mixed results. In order to address this issue, we apply the quantile regression approach to analyze the momentum effect in the context of Chinese stock market in this paper. The evidence suggests that the momentum effect in Chinese stock is not stable across firms with different levels of performance. We find that negative momentum effect in the short and medium horizon (3 months and 9 months) increases with the quantile of stock returns. And the positive momentum effect is observed in the long horizon (12 months), which also intensifies for the high performing stocks. According to our study, momentum effect needs to be examined on the basis of stock returns. OLS estimation, which gives an exclusive and biased result, provides misguiding intuitions for momentum effect across the global nations. Based on the empirical results of quantile regression, effective risk control strategies can also be inspired by adjusting the proportion of assets with past performances.
The stochastic dissipative Zakharov equations with white noise are mainly investigated. The global random attractors endowed with usual topology for the stochastic dissipative Zakharov equations are obtained in the sense of usual norm. The method is to transform the stochastic equations into the corresponding partial differential equations with random coefficients by Ornstein-Uhlenbeck process. The crucial compactness of the global random attractors will be obtained by decomposition of solutions.
An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a'(G), is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a'(G)≤16Δ for every graph G where Δ denotes the maximum degree of G. We prove that a'(G) < 13.8Δ for an arbitrary graph G. We also reduce the upper bounds of a'(G) to 9.8Δ and 9Δ with girth 5 and 7, respectively.
The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O(n logn+m)-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.
We investigate Chapman-Jouguet models in three-dimensional space by means of generalized characteristic analysis. The interaction of detonation, shock waves and contact discontinuity is discussed intensively in this paper. If contact discontinuity appears, the structure of global solutions becomes complex. We deal with this problem when strength of detonation is small.
We prove the existence and uniqueness of global strong solutions to the Cauchy problem of the three-dimensional magnetohydrodynamic equations in R^{3} when initial data are helically symmetric. Moreover, the large-time behavior of the strong solutions is obtained simultaneously.
The aim of this paper is to extend the semi-uniform ergodic theorem and semi-uniform sub-additive ergodic theorem to skew-product quasi-flows. Furthermore, more strict inequalities about these two theorems are established. By making use of these results, it is feasible to get uniform estimation of the Lyapunov exponent of some special systems even under non-uniform hypotheses.
Let [b, T] be the commutator of parabolic singular integral T. In this paper, the authors prove that the boundedness of [b, T] on the generalized Morrey spaces implies b ∈ BMO(R^{n}, ρ). The results in this paper improve and extend the Komori and Mizuhara's results.
By modifying the procedure of binary nonlinearization for the AKNS spectral problem and its adjoint spectral problem under an implicit symmetry constraint, we obtain a finite dimensional system from the Lax pair of the nonlinear Schrödinger equation. We show that this system is a completely integrable Hamiltonian system.
Delay discrete integral inequalities with n nonlinear terms in two variables are discussed, which generalize some existing results and can be used as powerful tools in the analysis of certain partial difference equations. An application example is also given to show boundedness of solutions of a difference equation.
This paper suggests a modified serial correlation test for linear panel data models, which is based on the parameter estimates for an artificial autoregression modeled by differencing and centering residual vectors. Specifically, the differencing operator over the time index and the centering operator over the individual index are, respectively, used to eliminate the potential individual effects and time effects so that the resultant serial correlation test is robust to the two potential effects. Clearly, the test is also robust to the potential correlation between the covariates and the random effects. The test is asymptotically chi-squared distributed under the null hypothesis. Power study shows that the test can detect local alternatives distinct at the parametric rate from the null hypothesis. The finite sample properties of the test are investigated by means of Monte Carlo simulation experiments, and a real data example is analyzed for illustration.
In this paper, we derive a posteriori error estimators for the constrained optimal control problems governed by semi-linear parabolic equations under some assumptions. Then we use them to construct reliable and efficient multi-mesh adaptive finite element algorithms for the optimal control problems. Some numerical experiments are presented to illustrate the theoretical results.
This paper consider the (BMAP_{1}, BMAP_{2})/(PH_{1}, PH_{2})/N retrial queue with finite-position buffer. The behavior of the system is described in terms of continuous time multi-dimensional Markov chain. Arriving type I calls find all servers busy and join the buffer, if the positions of the buffer are insufficient, they can go to orbit. Arriving type Ⅱ calls find all servers busy and join the orbit directly. Each server can provide two types heterogeneous services with Phase-type (PH) time distribution to every arriving call (including types I and Ⅱ calls), arriving calls have an option to choose either type of services. The model is quite general enough to cover most of the systems in communication networks. We derive the ergodicity condition, the stationary distribution and the main performance characteristics of the system. The effects of various parameters on the system performance measures are illustrated numerically.
Suppose that we have a partially linear model Y_{i} = x'_{i}β + g(t_{i}) + ε_{i} with independent zero mean errors ε_{i}, where {x_{i}, t_{i}, i = 1, …, n} are non-random and observed completely and {Y_{i}, i = 1, …, n} are missing at random(MAR). Two types of estimators of β and g(t) for fixed t are investigated: estimators based on semiparametric regression and inverse probability weighted imputations. Asymptotic normality of the estimators is established, which is used to construct normal approximation based confidence intervals on β and g(t). Results are reported of a simulation study on the finite sample performance of the estimators and confidence intervals proposed in this paper.
Distinguishability plays a crucial rule in studying observability of hybrid system such as switched system. Recently, for two linear systems, Lou and Si gave a condition not only necessary but also sufficient to the distinguishability of linear systems. However, the condition is not easy enough to verify. This paper will give a new equivalent condition which is relatively easy to verify.
Duffing equation with damping and external excitations is investigated. By using Melnikov method and bifurcation theory, the criterions of existence of chaos under periodic perturbations are obtained. By using second-order averaging method, the criterions of existence of chaos in averaged system under quasi-periodic perturbations for Ω= nω +εσ, n = 2, 4, 6 (where σis not rational to ω) are investigated. However, the criterions of existence of chaos for n = 1, 3, 5, 7 - 20 can not be given. The numerical simulations verify the theoretical analysis, show the occurrence of chaos in the averaged system and original system under quasi- periodic perturbation for n = 1, 2, 3, 5, and expose some new complex dynamical behaviors which can not be given by theoretical analysis. In particular, the dynamical behaviors under quasi-periodic perturbations are different from that under periodic perturbations, and the period-doubling bifurcations to chaos has not been found under quasi-periodic perturbations.
This paper deals with the boundedness of the solutions of the following dynamic equations (r(t)x^{Δ} (t))^{Δ} + a(t)f(x^{σ}(t)) + b(t)g(x^{σ}(t)) = 0 and (r(t)x^{Δ}(t))^{Δ} + a(t)x^{σ}(t) + b(t)f(x(t -τ(t))) = e(t) on a time scale T. By using the Bellman integral inequality, we establish some sufficient conditions for boundedness of solutions of the above equations. Our results not only unify the boundedness results for differential and difference equations but are also new for the q-difference equations.
In this paper, we investigate the a priori and a posteriori error estimates for the discontinuous Galerkin finite element approximation to a regularization version of the variational inequality of the second kind. We show the optimal error estimates in the DG-norm (stronger than the H^{1} norm) and the L^{2} norm, respectively. Furthermore, some residual-based a posteriori error estimators are established which provide global upper bounds and local lower bounds on the discretization error. These a posteriori analysis results can be applied to develop the adaptive DG methods.
This paper is devoted to the existence and long time behavior of the global classical solution to Fokker-Planck-Boltzmann equation with initial data near the absolute Maxwellian.