The ski-rental problem with multiple discount options

We propose the ski-rental problem with multiple discount options in which there are n options to rent an equipment. Every option has a rental duration; the longer the duration, the more the discount. This generalizes the standard ski-rental problem where one can only rent or buy. We present a 4-competitive on-line algorithm for our problem and show that no deterministic algorithm can have a smaller competitive ratio when n is large enough. Comparing with the original ski-rental problem, the competitive ratio becomes larger when there are more options.     

The Leader–Follower Location Model

This paper summarizes some results for the leader–follower location model on networks in several scenarios. Discretization results are considered and differences derived from the inelastic and elastic demand assumptions, as well as from the customer’s choice rule, are emphasized. Finally, some issues for future lines of investigation are suggested.     

Online deadline scheduling with preemption penalties

This paper presents a study of the problem of online deadline scheduling under the preemption penalty model of Zheng, Xu, and Zhang (2007). In that model, each preemption incurs a penalty of ρ times the weight of the preempted job, where ρ ? 0 is the preemption penalty parameter. The objective is to maximise the total weight of jobs completed on time minus the total penalty.     

竞技体育运动训练机能监控预警系统的研究与应用

运用计算机与数据库技术,根据竞技体育运动训练机能监控的需求,构建竞技体育运动训练机能监控预警系统。该系统主要包括运动员基本信息管理、训练计划与测试方案、测试数据录入与查询、机能评定与监控预警,通过该系统实现对运动员运动训练机能监控预警。     

Enhancements to the dynamic self-organising neural network

Class Directed Unsupervised Learning (CDUL) is a dynamic self-organising network which has been shown to overcome many of the problems associated with unsupervised learning, thereby yielding performance characteristics superior to similar networks such as counter-propagation and LVQ. In this paper, the CDUL algorithm is developed further, to a point where the original two-phase learning process is combined into a single system of dynamic parameter variation; a training cycle that can then be terminated automatically at a point of zero error over the training set. The ability to improve training times using a FastCDUL algorithm is also explored. The new algorithm, CDUL2, is subsequently applied to the benchmark problem of mine detection given sonar data, and shown to outperform both backpropagation and LVQ in terms of training speed and recall performance. Finally, a measure of computational cost is estimated for both CDUL2 and LVQ training periods, reinforcing the suggested efficiency of CDUL2 over its counterparts.     

Simultaneous gesture segmentation and recognition based on forward spotting accumulative HMMs

Existing gesture segmentations use the backward spotting scheme that first detects the end point, then traces back to the start point and sends the extracted gesture segment to the hidden Markov model (HMM) for gesture recognition. This makes an inevitable time delay between the gesture segmentation and recognition and is not appropriate for continuous gesture recognition. To solve this problem, we propose a forward spotting scheme that executes gesture segmentation and recognition simultaneously. The start and end points of gestures are determined by zero crossing from negative to positive (or from positive to negative) of a competitive differential observation probability that is defined by the difference of observation probability between the maximal gesture and the non-gesture. We also propose the sliding window and accumulative HMMs. The former is used to alleviate the effect of incomplete feature extraction on the observation probability and the latter improves the gesture recognition rate greatly by accepting all accumulated gesture segments between the start and end points and deciding the gesture type by a majority vote of all intermediate recognition results. We use the predetermined association mapping to determine the 3D articulation data, which reduces the feature extraction time greatly. We apply the proposed simultaneous gesture segmentation and recognition method to recognize the upper-body gestures for controlling the curtains and lights in a smart home environment. Experimental results show that the proposed method has a good recognition rate of 95.42% for continuously changing gestures.     

Online hierarchical scheduling: An approach using mathematical programming

This paper considers an online hierarchical scheduling problem on parallel identical machines. We are given a set of m machines and a sequence of jobs. Each machine has a different hierarchy, and each job also has a hierarchy associated with it. A job can be assigned to a machine only if its hierarchy is no less than that of the machine. The objective is to minimize the makespan, i.e., the maximum load of all machines. Two models are studied in the paper. For the fractional model, we present an improved algorithm and lower bounds. Both the algorithm and the lower bound are based on solutions of mathematical programming. For any given m, our algorithm is optimal by numerical calculation. For the integral model, we present both a general algorithm for any m, and an improved algorithm with better competitive ratios of 2.333 and 2.610 for m=4 and 5, respectively.     

Optimal Time-Critical Scheduling via Resource Augmentation

Abstract. We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP . We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For optimization of average flow time, these are the first results of any sort, for any NP -hard version of the problem, that indicate that it might be possible to design good approximation algorithms.     

人工神经网络在模拟电路故障诊断中的应用

容差和非线性特性使得模拟电路的故障诊断趋于复杂化,针对这两个问题,几年来,人们提出了许多相关的诊断方法。但是,迄今为止．尚没有一种通用的、行之有效的方法。因此,尝试将自组织竞争网络引入到模拟电路的诊断过程中,并提出一种基于竞争网络的诊断方法。由于自组织竞争网络在非线性映射、容错与自学习方面的独特优势,理论上对于解决模拟电路的容差和非线性问题是非常适合的。最后,实例表明,基于竞争网络的方法能够准确识别出电路中的故障。     

Self-organizing map network as an interactive clustering tool — An application to group technology

The Self-Organizing Map (SOM) network, a variation of neural computing networks, is a categorization network developed by Kohonen. The theory of the SOM network is motivated by the observation of the operation of the brain. This paper presents the technique of SOM and shows how it may be applied as a clustering tool to group technology. A computer program for implementing the SOM neural networks is developed and the results are compared with other clustering approaches used in group technology. The study demonstrates the potential of using the Self-Organizing Map as the clustering tool for part family formation in group technology.