Table of Content

15 June 2019, Volume 23 Issue 2

Previous Issue    Next Issue

M/G/1 queueing system with Min(N,D,V)- policy control

LUO Le, TANG Yinghui

2019, 23(2):  1-16.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.001

Asbtract ( 968 )   PDF (2405KB) ( 184 )  

References | Related Articles | Metrics

In this paper, we consider the M/G/1 queueing system with multiple server vacations and Min(N,D,V) -policy. By using the total probability decomposition technique and the Laplace transformation tool, the transient queue-length distribution and the steady queue-length distribution are discussed. Both the expressions of the Laplace transformation of the transient queue-length distribution and the recursive expressions of the steady queue-length distribution are obtained. Meanwhile, we present the stochastic decomposition result of the steady queue length and the explicit expression of the additional queue length distribution. Furthermore, some special cases are discussed when N→1, D→1, p{V=∞}=1 or p{V=0}=1. Finally, the explicit expression of the long-run expected cost rate is derived under a given cost structure. And by through numerical calculation, we determine the optimal control policy (N^*; D^*) for minimizing the long-run expected cost per unit time as well as compare with the single optimal N^*-policy and the single optimal D^*-policy.

A cubic regularization method for solving nonsmooth equations

MIAO Xiaonan, GU Jian, XIAO Xiantao

2019, 23(2):  17-30.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.002

Asbtract ( 1142 )   PDF (583KB) ( 202 )  

References | Related Articles | Metrics

A cubic regularization method and its convergence for solving a nonsmooth system of equations are studied in this paper. By applying the classical trust region technique, the proposed method is ensured to be globally convergent. When BDregular condition is satisfied and the subproblem is inexactly solved, we analyze the local convergence rate of the nonsmooth cubic regularization method. Finally, the efficiency of our method is verified by numerical results.

Contraction graph method for the interval edge-colorings of graphs

TAO Yanliang, HUANG Qiongxiang, CHEN Lin

2019, 23(2):  31-43.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.003

Asbtract ( 1085 )   PDF (1678KB) ( 140 )  

References | Related Articles | Metrics

An edge-coloring of a graph G with colors 1, 2,…, t is an interval t-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integer. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. The set of all interval colorable graphs is denoted by N. For a graph G∈N, the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G) and W (G), respectively. In this paper, we introduce a contraction graph method for the interval edge-colorings of graphs. By using this method, we show that w(G)=△(G) or △(G) + 1 for any bicyclic graph G∈N. Moreover, we completely determine bicyclic graphs with w(G)=△(G) and w(G)=△(G) + 1, respectively.

Optimal investment strategy for the DC pension fund with Stein-Stein volatility and dynamic VaR constraint

SUN Jingyun, TIAN Lina, CHEN Zheng

2019, 23(2):  44-56.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.004

Asbtract ( 928 )   PDF (2552KB) ( 159 )  

References | Related Articles | Metrics

In this paper, we consider the optimal asset allocation problem for the defined contribution pension plan on the phase of accumulation before retirement. We assume that the pension fund can be invested into a financial market consisting of a risk-free asset and a risky asset who's price process satisfies Stein-Stein stochastic volatility model. By using the method of stochastic optimal control, we obtain the optimal investment strategy of the pension fund without or with dynamic value at risk constraint aiming to maximize the expected utility of relative wealth at retirement time, and derive the corresponding analytic expression of the optimal value function. Finally, a numerical example is provided to verify the related theoretical results and the sensitivity of the optimal investment strategy on some parameters is analyzed.

Fluid models driven by a working vacation-queue with PH-service time distribution

WANG Huining, XU Xiuli

2019, 23(2):  57-66.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.005

Asbtract ( 1207 )   PDF (939KB) ( 121 )  

References | Related Articles | Metrics

This paper is concerned with the fluid model which is driven by a PHservice time and single-server queue with server working vacation. To analyze the fluid model, we first establish the stationary distribution of the queue length process. Based on the steady-state distribution, then the matrix-type ordinary differential equation is obtained for the joint distribution characterizing the fluid model dynamics. With the help of the Laplace transform (LT) and the Laplace-Stieltjes transform (LST), as usual, the probability for the system empty and the average fluid level are given. An application of these obtained results to the mobile Ad Hoc networks is provided. The sensitivities about the system primitive parameters to the performance measures such as the average fluid level are discussed by some numerical experiments.

Scheduling with sub-jobs' due dates

ZHONG Weiya, YANG Ruoyao

2019, 23(2):  67-74.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.006

Asbtract ( 1073 )   PDF (500KB) ( 137 )  

References | Related Articles | Metrics

In this paper, we study a single machine scheduling problem in which sub-jobs have due dates. Given a set of jobs, each job is divided into several sub-jobs and each sub-job has a due date. A job is completed on time only if all its sub-jobs are completed before their due dates. We prove that even if each job has two sub-jobs, this problem is NP-hard and there is no FPTAS for this special case. Furthermore, we propose two heuristics for this model and a heuristic to get an upper bound and carry out numerical experiments to compare their performances.

Algorithm design and the fair incentive mechanism in Chinese college admissions matching market

LI Jianrong

2019, 23(2):  75-85.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.007

Asbtract ( 1147 )   PDF (575KB) ( 2032 )  

References | Related Articles | Metrics

This paper, using matching game theoretic methods, studies the algorithm design and the fair incentive mechanism in Chinese college admissions market. Based on the admissions procedure, we design the Chinese college admissions algorithm, which we proved is feasible. We prove that every stable allocation can be produced by a Nash equilibrium, but not vice versa. We demonstrate the relationship between fairness and stability, and prove that stability implies fairness but not vice versa. Then we construct a (Gale and Shapley) deferred-acceptance algorithm in our market and show that it is both stable and strategy-proof. Therefore, it is a fair incentive mechanism.

A splitting augmented Lagrangian method embedding in the BB method for solving the sparse logistic problem

LIANG Renli, BAI Yanqin

2019, 23(2):  86-94.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.008

Asbtract ( 755 )   PDF (873KB) ( 166 )  

References | Related Articles | Metrics

Logistic regression is a promising method that has been used widely in many applications of data mining, machine learning, computer vision. In this paper, we study on the l₀ sparse logistic regression problem. This problem has been proposed as a promising method for feature selection in classification problems, and it is in general NP-hard. In order to solve this problem, we develop a splitting augmented Lagrange method with embedding BB (Barzilai and Borwein) method (SALM-BB). At each iteration, SALM-BB solves an unconstrained convex subproblem and a quadratic programming with l₀ constraint. We use BB method to solve the unconstrained convex subproblem. For the quadratic programming subproblem, we obtain its exact optimal solution directly. Furthermore, we prove the convergence of SALM-BB, under certain assumptions. Finally, we implement SALM-BB on the l₀ sparse logistic regression problem based on the simulation data and the data of University of California, Irvine, Machine Learning Repository. Numerical results show that SALM-BB outperforms the well-known first-order solver SLEP in terms of lower average logistic loss and lower misclassification error rate.

A class of generalized mond-weir type duality theory for mathematical programs with equilibrium constraints

GAO Leifu, YAN Tingting

2019, 23(2):  95-103.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.009

Asbtract ( 859 )   PDF (483KB) ( 153 )  

References | Related Articles | Metrics

In this paper, considering the mathematical programs with equilibrium constraints is difficult to meet the constrained qualification and difficult to solve, we establish a class of generalized Mond-Weir type duality of equilibrium constrained optimization problem. Using the S-stability, we propose the duality theory, which is based on the dual form of standard nonlinear programming proposed by Mond and Weir. The theory provides a new method for solving the problem of equilibrium constraint optimization. Under the condition of Hanson-Mond generalized convexity, the weak duality, strong duality and strict inverse duality theorems are proposed by using the sublinear function, and the corresponding proofs are given. The generalization of the dual method provides a theoretical basis for studying the solution of the mathematical programs with equilibrium constraints.

Path-transformation graph of maximum matchings

LIU Yan, LEI Mengxia, HUANG Xiaoxian

2019, 23(2):  104-112.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.010

Asbtract ( 491 )   PDF (860KB) ( 178 )  

References | Related Articles | Metrics

The path-transformation graph of maximum matchings of a graph G, denoted by NM(G), is a graph where vertices are maximum matchings of G and two maximum matchings M₁ and M₂ are adjacent in NM(G) if the symmetric difference of M₁ and M₂ induces a path (there is no limit for the length of the path). In the paper, we study the connectivity of the transformation graph, and obtain the necessary and sufficient condition that the transformation graph is a complete graph or a tree or a cycle, respectively.

The linear aboricity of planar graphs with 6-cycles containing at most one chord

LUO Zhaoyang, SUN Lin

2019, 23(2):  113-119.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.011

Asbtract ( 504 )   PDF (599KB) ( 111 )  

References | Related Articles | Metrics

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, using the discharging method, it is proved that for a planar graph G, la(G)=「△(G)/2」 if △(G) > 7 and every 6-cycle of G contains at most one chord.

Two sufficient conditions for maximally restricted-edge-connected hypergraphs

PEI Jianfeng, LIN Shangwei

2019, 23(2):  120-126.  doi:10.15960/j.cnki.issn.1007-6093.2019.02.012

Asbtract ( 1839 )   PDF (622KB) ( 142 )  

References | Related Articles | Metrics

The restricted edge-connectivity of a graph is a generalization of the classical edge-connectivity, and can be used to accurately measure the fault tolerance of networks. Maximally restricted-edge-connected graphs are a class of graphs with optimal restricted edge-connectivity. In this paper, we first extend the concepts of the restricted edge-connectivity and the minimum edge degree to r-uniform and linear hypergraphs H, prove that the minimum edge degree ξ(H) of H is an upper bound on its restricted edge-connectivity λ'(H) if its minimum degree δ(H) ≥ r + 1, and call the hypergraph H with ξ(H)=λ'(H) a maximally restricted-edge-connected hypergraph. Next, we show that an r-uniform and linear hypergraph H with order n and minimum degree δ(H)≥n-1/2(r-1) + (r-1) is maximally restricted-edge-connected. Finally, we prove that an r-uniform and linear hypergraph H with diameter 2 and girth at least 4 is maximally restricted-edge-connected. These results are generalizations of corresponding results in graphs.