15 January 2010, Volume 26 Issue 1
    

  • Select all
    |
  • 论文
    AMethod of Estimating Computational Complexity Based on Input Conditions for N-vehicle Problem
    Xi Xia, Jin-chuan Cui
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 1-11.
    DOI:10.1007/s10255-008-8811-5
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N (input scale of problem). To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method: 1) to decrease computation in enumeration; 2) to efficiently obtain computational complexity for any N-vehicle case; 3) to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.

  • 论文
    Improved Algorithm for Broadcast Scheduling of Minimal Latency in Wireless Ad Hoc Networks
    Wei-ping Shang, Peng-junWan, Xiao-dong Hu
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 13-22.
    DOI:10.1007/s10255-008-8806-2
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648(rmax/rmin)2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most (1 + 2rmax/rmin)2 + 32. Moreover, under the proposed scheduling each node just needs to forward a message at most once.

  • 论文
    Some w-unique and w-P Properties for Linear Transformations on Hilbert Spaces
    Xin-he Miao, Zheng-hai Huang, Ji-ye Han
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 23-32.
    DOI:10.1007/s10255-008-8810-6
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    Given a real (finite-dimensional or infinite-dimensional) Hilbert space H with a Jordan product, we introduce the concepts of w-unique and w-P properties for linear transformations on H, and investigate some interconnections among these concepts. In particular, we discuss the w-unique and w-P properties for Lyapunov-like transformations on H. The properties of the Jordan product and the Lorentz cone in the Hilbert space play important roles in our analysis.

  • 论文
    Minimizing Maximum Risk for Fair Network Connection with Interval Data
    Jie Hu
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 33-40.
    DOI:10.1007/s10255-008-8812-4
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    In this paper we introduce a minimax model for network connection problems with interval parameters. We consider how to connect given nodes in a network with a path or a spanning tree under a given budget, where each link is associated with an interval and can be established at a cost of any value in the interval. The quality of an individual link (or the risk of link failure, etc.) depends on its construction cost and associated interval. To achieve fairness of the network connection, our model aims at the minimization of the maximum risk over all links used. We propose two algorithms that find optimal paths and spanning trees in polynomial time, respectively. The polynomial solvability indicates salient difference between our minimax model and the model of robust deviation criterion for network connection with interval data, which gives rise to NP-hard optimization problems.

  • 论文
    Optimal Policies for Inventory Systems with Discretionary Sales, Random Yield and Lost Sales
    Xiao-ming Yan, Ke Liu
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 41-54.
    DOI:10.1007/s10255-009-8824-8
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    We determine replenishment and sales decisions jointly for an inventory system with random demand, lost sales and random yield. Demands in consecutive periods are independent random variables and their distributions are known. We incorporate discretionary sales, when inventory may be set aside to satisfy future demand even if some present demand may be lost. Our objective is to minimize the total discounted cost over the problem horizon by choosing an optimal replenishment and discretionary sales policy. We obtain the structure of the optimal replenishment and discretionary sales policy and show that the optimal policy for finite horizon problem converges to that of the infinite horizon problem. Moreover, we compare the optimal policy under random yield with that under certain yield, and show that the optimal order quantity (sales quantity) under random yield is more (less) than that under certain yield.

  • 论文
    Complex Dynamics in Physical Pendulum Equation with Suspension Axis Vibrations
    Xiang-ling Fu, Jin Deng, Zhu-jun Jing
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 55-78.
    DOI:10.1007/s10255-008-8276-6
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    The physical pendulum equation with suspension axis vibrations is investigated. By using Melnikov’s method, we prove the conditions for the existence of chaos under periodic perturbations. By using second-order averaging method and Melinikov’s method, we give the conditions for the existence of chaos in an averaged system under quasi-periodic perturbations for Ω = nω + εν, n = 1 - 4, where ν is not rational to ω. We are not able to prove the existence of chaos for n = 5 - 15, but show the chaotic behavior for n = 5 by numerical simulation. By numerical simulation we check on our theoretical analysis and further exhibit the complex dynamical behavior, including the bifurcation and reverse bifurcation from period-one to period-two orbits; the onset of chaos, the entire chaotic region without periodic windows, chaotic regions with complex periodic windows or with complex quasi-periodic windows; chaotic behaviors suddenly disappearing, or converting to period-one orbit which means that the system can be stabilized to periodic motion by adjusting bifurcation parameters α, δ, f0 and Ω; and the onset of invariant torus or quasi-periodic behaviors, the entire invariant torus region or quasi-periodic region without periodic window, quasi-periodic behaviors or invariant torus behaviors suddenly disappearing or converting to periodic orbit; and the jumping behaviors which including from periodone orbit to anther period-one orbit, from quasi-periodic set to another quasi-periodic set; and the interleaving occurrence of chaotic behaviors and invariant torus behaviors or quasi-periodic behaviors; and the interior crisis; and the symmetry breaking of period-one orbit; and the different nice chaotic attractors. However, we haven’t find the cascades of period-doubling bifurcations under the quasi-periodic perturbations and show the differences of dynamical behaviors and technics of research between the periodic perturbations and quasi-periodic perturbations.

  • 论文
    Confident Estimation for Density of a Biological Population Based on Line Transect Sampling
    Ren-bin Gong, Yun-bei Ma, Yong Zhou
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 79-92.
    DOI:10.1007/s10255-009-9008-2
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    Line transect sampling is a very useful method in survey of wildlife population. Confident interval estimation for density D of a biological population is proposed based on a sequential design. The survey area is occupied by the population whose size is unknown. A stopping rule is proposed by a kernel-based estimator of density function of the perpendicular data at a distance. With this stopping rule, we construct several confidence intervals for D by difference procedures. Some bias reduction techniques are used to modify the confidence intervals. These intervals provide the desired coverage probability as the bandwidth in the stopping rule approaches zero. A simulation study is also given to illustrate the performance of this proposed sequential kernel procedure.

  • 论文
    Soft-capacitated Facility Location Game
    Yu Li, Da-chuan Xu
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 93-98.
    DOI:10.1007/s10255-008-8111-0
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    We study the soft-capacitated facility location game which is an extension of the facility location game of P′al and Tardös. We propose a 6-approximate cross-monotonic cost-sharing method. Numerical tests indicate that the method is effective.

  • 论文
    Compromise 4m2n Plans with Clear Two-factor Interactions
    Sheng-li Zhao, Run-chu Zhang
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 99-106.
    DOI:10.1007/s10255-006-6183-2
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    This paper gets some necessary conditions for the existence of some kinds of clear 4m2n compromise plans which allow estimation of all main effects and some specified two-factor interactions without assuming the remaining two-factor interactions being negligible. Some methods for constructing clear 4m2n compromise plans are introduced.

  • 论文
    An Erdös-Ko-Rado Theorem for Restricted Signed Sets
    Yu-shuang Li
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 107-112.
    DOI:10.1007/s10255-009-6184-z
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    A restricted signed r-set is a pair (A, f), where A ⊆ [n] = {1, 2, · · · , n} is an r-set and f is a map from A to [n] with f(i) ≠ i for all i ∈ A. For two restricted signed sets (A, f) and (B, g), we define an order as (A, f) ≤ (B, g) if A ⊆ B and g|A = f. A family A of restricted signed sets on [n] is an intersecting antichain if for any (A, f), (B, g)∈ A, they are incomparable and there exists x ∈ A ∩ B such that f(x) = g(x). In this paper, we first give a LYM-type inequality for any intersecting antichain A of restricted signed sets, from which we then obtain |A| ≤ (r-1 n-1)(n-1)r-1 if A consists of restricted signed r-sets on [n]. Unless r = n = 3, equality holds if and only if A consists of all restricted signed r-sets (A, f) such that x0 ∈ A and f(x0) = ε0 for some fixed x0 ∈ [n], ε0 ∈ [n] \ {x0}.

  • 论文
    Multiplicity of Positive Solutions to Period Boundary Value Problems for Second Order Impulsive Differential Equations
    Qiao-shu Zhou, Da-qing Jiang, Yu Tian
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 113-124.
    DOI:10.1007/s10255-007-7136-0
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    This paper deals with the existence and multiplicity of positive solutions to second order period boundary value problems with impulse effects. The proof of our main results relies on a well-known fixed point theorem in cones. The paper extends some previous results and reports some new results about impulsive differential equations.

  • 论文
    Mixtures of Semiparametric Varying Coefficient Models for Longitudinal Data with Nonignorable Dropout
    Zhi-qiang Li, Liu-gen Xue
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 125-132.
    DOI:10.1007/s10255-009-7141-6
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    Informative dropout often arise in longitudinal data. In this paper we propose a mixture model in which the responses follow a semiparametric varying coefficient random effects model and some of the regression coefficients depend on the dropout time in a non-parametric way. The local linear version of the profile-kernel method is used to estimate the parameters of the model. The proposed estimators are shown to be consistent and asymptotically normal, and the finite performance of the estimators is evaluated by numerical simulation.

  • 论文
    Blow Up Behavior for a Semilinear Parabolic Equation with Localized Source
    Ming Yang, Hui-ling Li
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 133-144.
    DOI:10.1007/s10255-008-8218-3
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    In this paper, we investigate the blow-up behavior of solutions of a parabolic equation with localized reactions. We completely classify blow-up solutions into the total blow-up case and the single point blow-up case, and give the blow-up rates of solutions near the blow-up time which improve or extend previous results of several authors. Our proofs rely on the maximum principle, a variant of the eigenfunction method and an initial data construction method.

  • 论文
    Multiplicity of Positive Solutions to M-point Boundary Value Problem of Second Order Impulsive Differential Equations
    Yuan-sheng Tian, Chun-gen Liu
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 145-158.
    DOI:10.1007/s10255-008-8231-6
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    In this paper, by using Avery-Peterson theorem on a convex cone, we consider the m-point boundary value problems for second order impulsive differential equations with the nonlinear term depending on the first order derivative, the multiplicity result of three positive solutions are obtained.

  • 论文
    Ergodicity of a Class of Nonlinear Time Series Models in Random Environment Domain
    En-wen Zhu, Han-jun Zhang, Gang Yang, Zai-ming Liu, Jie-zhong Zou, Shao-shun Long
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 159-168.
    DOI:10.1007/s10255-009-8245-8
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    In this paper, we study the problem of a variety of nonlinear time series model Xn+1 = TZn+1(X(n), · · ·,X(n - Zn+1), en+1(Zn+1)) in which {Zn} is a Markov chain with finite state space, and for every state i of the Markov chain, {en(i)} is a sequence of independent and identically distributed random variables. Also, the limit behavior of the sequence {Xn} defined by the above model is investigated. Some new novel results on the underlying models are presented.

  • 论文
    Integral Self-affine Tiles of Bandt’s Model
    Hui Rao, Li-jun Zhang
    Acta Mathematicae Applicatae Sinica(English Series). 2010, 26(1): 169-176.
    DOI:10.1007/s10255-009-9038-9
    Abstract ( )    Download PDF ( )   Knowledge map   Save
    Integral self-affine tiling of Bandt’s model is a generalization of the integral self-affine tiling. Using ergodic theory, we show that the Lebesgue measure of the tile is a rational number where the denominator equals to the order of the associate symmetry group. We apply the result to the study of the Levy Dragon.

Journal Online
News More