Table of Content

15 March 2010, Volume 14 Issue 1

   Next Issue

Original Articles

A Note on The Steiner Problem ---An Approach to Find The Minimal Network

Yue Minyi, Cheng Congdian

2010, 14(1):  1-14. 

Asbtract ( 1590 )  

Related Articles | Metrics

This article addresses the problem how to find a minimal  network connecting 5 given points in the plane. The related results with four points have been given by Pollack (1978) and  Yue Minyi.  The present work  proposes a fast algorithm to solve the problem.

Utility-based Differential Game for Portfolio  in CIR Framework Non-uniformly Bounded Costs

Wan Shuping

2010, 14(1):  15-23. 

Asbtract ( 1516 )  

Related Articles | Metrics

Utility-based differential game for portfolio with Cox-Ingersoll-Ross (CIR) stochastic interest rate in continuous time between two investors is developed. The market interest rate has the dynamics of CIR interest rate. The prices of risky stocks are affected by CIR interest rate. There is a single payoff function which depends on both investors' wealth processes. One player chooses a dynamic portfolio strategy in order to maximize this expected payoff, while his opponent is simultaneously choosing a dynamic portfolio strategy so as to minimize the same quantity. The optimal strategies for the utility-based game are obtained by the stochastic control theory. Especially for the constant relative risk aversion utility game with fixed duration, the explicit optimal strategies and value of the game are derived. The numerical example and simulation are provided to illustrate the results obtained in this paper.

Extremal Graphs about Bipartite Matching Extendability

WANG Xiu-Mei, SHANG Wei-苹, LIN Yi-Xun

2010, 14(1):  23-30. 

Asbtract ( 1573 )  

Related Articles | Metrics

Let $G$ be a simple  graph containing a perfect matching.  $G$ is said to be bipartite matching extendable (BM-extendable) if every matching $M$ whose induced subgraph is a bipartite graph extends to a perfect matching. Extremal graph problems are at the core  of graph theory. In this paper, we characterize maximally BM-unextendable graphs, maximally BM-extendable graphs in the class of complete $k$-partite graphs with $k\geq 2$.

Strong NP-hardness of the Single-variable-resource Scheduling Problem to Minimize the Total Weighted Completion Time

Yuan-Jin-Jiang, WANG Qin

2010, 14(1):  31-36. 

Asbtract ( 1563 )  

Related Articles | Metrics

Baker and Nuttle studied the following single-variable-resource scheduling problem: sequencing $n$ jobs for processing by a single resource to minimize a function of job  completion times, when the availability of the resource varies over time.  When the objective function to be minimized is the total weighted completion time,   Baker and Nuttle conjectured that the problem is NP-hard. Recently, Yuan, Cheng and Ng   showed that this problem is NP-hard in the binary sense, but the   exact complexity of the problem is still open. We show in this paper  that this problem is strongly NP-hard.

 Algorithm for Nonlinear Integer programming

YANG Hua-Yun, YANG Yong-Jian

2010, 14(1):  37-45. 

Asbtract ( 1457 )  

Related Articles | Metrics

 In this paper, a novel  filled function is proposed for nonlinear integer programming  problem. This function contains only one parameter. We also  discuss the properties of the proposed function and using this filled function  to solve the nonliner integer programming problem. Numerical experiments on  several test problems have demonstrated the reliability and efficiency of  the proposed method.

Set in Constrained Convex Vector Optimization

Chen-Yao, HUANG Xue-Xiang, GUO Li

2010, 14(1):  46-54. 

Asbtract ( 1297 )  

Related Articles | Metrics

In this paper, we first characterize the nonemptiness and boundedness of the efficient solution set of a cone-constrained convex vector optimization problem whose domination cone is  polyhedral.  Then, we apply a key condition in the characterizations to the convergence analysis of a class of penalty methods.

A Weighted-Path-Following Interior-Point Algorithm for Convex

JIN Zheng-Jing, BAI Yan-Qin, HAN Bo-Shun

2010, 14(1):  55-65. 

Asbtract ( 1641 )  

Related Articles | Metrics

Inspired by Darvay's work that developed a weighted path-following interior point algorithm for solving Linear Programming, we extend in this paper the algorithm of Darvay to solve convex quadratic optimization problem and show that this algorithm has local quadratic convergence rate and the favorable polynomial complexity bound.  

 A Linearization Technique for Quadratic Integer Programming with Box Constrain

REN Yan, CHEN Wei

2010, 14(1):  66-76. 

Asbtract ( 1603 )  

Related Articles | Metrics

In this paper, we discusses the linearization technique for the quadratic integer programming problem. Under the objective function is quadratic function, we consider the linearization strategy for the  problem with quadratic constrain, and extend the method for quadratic $0-1$problem to the quadratic problem with box constrains.  We consider the reduction of quadratic integer programming problems to linear mixed $0-1$ programming problems,and then solve the linear mixed $0-1$ programming problems with ilog-cplex or Excel.

 The Ruin Probability for Markov Risk Model with  Claim Amounts Being Exponentially Distributed

JIN Shi-Wei

2010, 14(1):  77-84. 

Asbtract ( 1373 )  

Related Articles | Metrics

The ruin probability for a Markov risk model is considered in the paper. In the case where the claim distribution is exponential or mixed exponential, the explicit form of the ruin probability is given by solving the differential-integral systems satisfied by the ruin probability.

Total Dominating Functions on Subclasses    of Chordal Graphs

ZHOU Li-Gang, DAN 而Fang, WANG Hai-Chao

2010, 14(1):  85-94. 

Asbtract ( 1287 )  

Related Articles | Metrics

 In this paper we show that the $k$-total domination and signed total domination problems are NP-complete on doubly chordal graphs. Also, we present an unified approach to slove the signed total domination, minus total domination, $k$-total domination and $\{k\}$-total domination problems on a strongly chordal graph in linear-time, if the strong elemination ordering for the strongly chordal graph is given.

 A Condition for Strong Average Optimality  of MDP with Non-uniformly Bounded Costs

XIAO Qing-Chu, TAN Hang-Sheng

2010, 14(1):  95-105. 

Asbtract ( 1371 )  

Related Articles | Metrics

In this paper, we consider the Markov decision processes under an average cost criterion with non- uniformly bounded cost,  denumerable state and arbitrary action spaces. Some sufficient conditions are given under which every average optimal policy is strong average optimal. We improve the main results obtained by Cavazos-Cadena R.and Fernandez-Gaucheran E. (Math. Meth. Oper. Res., 1996, 43: 281-300).  

 Mean-Variance-Approximate Skewness Portfolio  Model and Empirical Analysis

Yu-Jing

2010, 14(1):  106-114. 

Asbtract ( 1640 )  

Related Articles | Metrics

The classical Markowitz's mean-variance model in modern investment science uses variance as  risk measure while it ignores the asymmetry of the return istribution. When skewness is adopted to measure the asymmetry,  the portfolio optimization model becomes very difficult due to the nonconvex and non-quadratic features of skewness.In this paper,  we propose a mean-variance-approximate skewness (MVAS) model which measures the asymmetry by the radio of positive semi-variance and negative semi-variance. Empirical analysis of Chinese stock market shows that the portfolio models which consider  the asymmetry of the return distribution  outperform  MV and MAD models when the market has non-normal feature.

 An Introduction to the Cost for Multistage  Rocket of Series Type

ZHU Xue-Jun, CHEN Shu, ZHANG Lian-Sheng

2010, 14(1):  115-128. 

Asbtract ( 1297 )  

Related Articles | Metrics

 On basis of the maximum velocity's regularity of a multistage rocket we reform the commonly used mathematical model for the cost problem: the least least propellant plan. We analyze the cost problems for multistage rocket of series type in all cases, and verify the effectivity of the new model by some examples