On the On-line Number of Snacks Problem

In the number of snacks problem (NSP), which was originally proposed by our team, an on-line player is given the task of deciding how many shares of snacks his noshery should prepare each day. The on-line player must make his decision and then finish the preparation before the customers come to his noshery for the snacks; in other words, he must make decision in an on-line fashion. His goal is to minimize the competitive ratio, defined as _: C_A()/C_OPT(), where denotes a sequence of numbers of customers, C _OPT() is the cost of satisfying by an optimal off-line algorithm, and C _A() is the cost of satisfying by an on-line algorithm. In this paper we give a competitive algorithm for on-line number of snacks problem P1, the Extreme Numbers Harmonic Algorithm(ENHA), with competitive ratio 1+p(M-m)/(M+m), where M and m are two extreme numbers of customers over the total period of the game, and p is a ratio concerning the cost of the two types of situations, and then prove that this competitive ratio is the best one if an on-line player chooses a fixed number of shares of snacks for any sequence of numbers of customers. We also discuss several variants of the NSP and give some results for it. Finally, we propose a conjecture for the on-line NSP.     

On-line construction of the upper envelope of triangles and surface patches in three dimensions

In this paper, we describe a randomized incremental algorithm for computing the upper envelope (i.e., the pointwise maximum) of a set of n triangles in three dimensions. This algorithm is an on-line algorithm. It is structure-sensitive: the expected cost of inserting the n-th triangle is O(log nΣ_r=1ⁿτ(r)/r²) and depends on the expected size τ(r) of an intermediate result for r triangles. Since τ(r) can be Θ(r²(r)) in the worst case, this cost is bounded in the worst case by O(n(n) log n). (The expected behaviour is analyzed by averaging over all possible orderings of the input.) The main new characteristics is the use of a two-level history graph. (The history graph is an auxiliary data structure maintained by randomized incremental algorithms.) Our algorithm is fairly simple and appears to be efficient in practice. It extends to surfaces and surface patches of fixed maximum algebraic degree.     

Randomized algorithm for the k-server problem on decomposable spaces

We study the randomized k-server problem on metric spaces consisting of widely separated subspaces. We give a method which extends existing algorithms to larger spaces with the growth rate of the competitive quotients being at most O(logk). This method yields o(k)-competitive algorithms solving the randomized k-server problem for some special underlying metric spaces, e.g. HSTs of “small” height (but unbounded degree). HSTs are important tools for probabilistic approximation of metric spaces.     

On the on-line rent-or-buy problem in probabilistic environments

Fujiwara and Iwama [In: The 13th Annual International Symposium on Algorithms and Computation, pp. 476–488 (2002)] first integrated probability distribution into the classical competitive analysis to study the rental problem. They assumed that the future inputs are drawn from an exponential distribution, and obtained the optimal competitive strategy and the competitive ratio by the derivative method. In this paper, we introduce the interest rate and tax rate into the continuous model of Fujiwra and Iwama [In: The 13th Annual International Symposium on Algorithms and Computation, pp. 476–488 (2002)]. Moreover, we use the forward difference method in different probabilistic environments to consider discrete leasing models both with and without the interest rate. We not only give the optimal competitive strategies and their competitive ratios in theory, but also give numerical results. We find that with the introduction of the interest rate and tax rate, the uncertainty involved in the process of decision making will diminish and the optimal purchasing date will be put off.     

Dynamic modeling of copper flash smelting process at a Smelter in China

Due to the highly dynamic characteristic in copper smelting process at a Copper Smelter in China, it is difficult to maintain high performance level control. As a key process indicator to evaluate smelting performance, matte grade is in urgent need of being monitored online. Thus, a real-time dynamic model of predicting matte grade was developed and validated with data collected at an actual plant. Based on desulfurization ratio of copper concentrate, the model couples dynamic mass balances on each species with equilibrium relationships for major component (Cu, Fe, S, SiO₂, et al.) to form a system of differential and algebraic equations. The simulation results illustrate that the maximum relative error and average relative error of matte grade between measured values and predicted value of the model proposed is 3.3%, and the average relative error is 0.54%, which verify the effectiveness of the model developed in providing the guidance for controlling the copper flash smelting process.     

随机化应答调查方案的参数估计问题

随机化应答调查是一种特殊的数据采集技术,使得调查者既得到了某个敏感问题的信息又保护了被调查者的隐私,本文研究从两种随机化答调查方案采得数据后的参数估计问题,在应用Ｂａｙｅｓ估计时,给出了便于Ｍａｔｈｅｍａｔｉｃａ软件计算的后验均值和方差的公式,通过模拟实验,比较了两个方案所得估计量的优劣。     

Global stability for a model of competition in the chemostat with microbial inputs

We propose a model of competition of n species in a chemostat, with constant input of some species. We mainly emphasize the case that can lead to coexistence in the chemostat in a non-trivial way, i.e., where the n−1 less competitive species are in the input. We prove that if the inputs satisfy a constraint, the coexistence between the species is obtained in the form of a globally asymptotically stable (GAS) positive equilibrium, while a GAS equilibrium without the dominant species is achieved if the constraint is not satisfied. This work is round up with a thorough study of all the situations that can arise when having an arbitrary number of species in the chemostat inputs; this always results in a GAS equilibrium that either does or does not encompass one of the species that is not present in the input.     

Dynamic effects in inefficiency: Evidence from the Colombian banking sector

Firms face a continuous process of technological and environmental changes that requires them to make managerial decisions in a dynamic context. However, costs and constraints prevent firms from making instant adjustments towards optimal conditions and may cause inefficiency to persist in time. We propose a dynamic inefficiency specification that captures differences in the adjustment costs among firms and non-persistent effects of inefficiency heterogeneity. The model is fitted to a ten year sample of Colombian banks. The new specification improves model fit and have effects on efficiency estimations. Overall, Colombian banks present high inefficiency persistence but important differences between institutions are found. In particular, merged banks present low adjustment costs that allow them to recover rapidly efficiency losses derived from merging processes.     

A network-DEA model with new efficiency measures to incorporate the dynamic effect in production networks

A production network can be described as a collection of production processes performed by several interdependent groups of sub decision-making units (SDMUs) within a DMU. Dynamic effects pertain to the situation where intermediate outputs consumed by one SDMU may also dynamically influence its output level in the future. Without considering these effects in efficiency measurement, we would obtain biased efficiency measurement, because the measure could not faithfully reflect the underlying performance. Hence the result would provide misleading information to decision-makers. This paper proposes a network-DEA model with new efficiency measures to systematically cope with the dynamic effect within a production network. Various interconnections between the new measure and the DEA-efficiency have also been established. Additionally, we also formalize the relationship between returns-to-scale properties of DMUs and those of its constituting SDMUs. This paper presents a unified framework to analyze performances in a dynamic production network.     

XGobi: Interactive Dynamic Data Visualization in the X Window System

Abstract

XGobi is a data visualization system with state-of-the-art interactive and dynamic methods for the manipulation of views of data. It implements 2-D displays of projections of points and lines in high-dimensional spaces, as well as parallel coordinate displays and textual views thereof. Projection tools include dotplots of single variables, plots of pairs of variables, 3-D data rotations, various grand tours, and interactive projection pursuit. Views of the data can be reshaped. Points can be labeled and brushed with glyphs and colors. Lines can be edited and colored. Several XGobi processes can be run simultaneously and linked for labeling, brushing, and sharing of projections. Missing data are accommodated and their patterns can be examined; multiple imputations can be given to XGobi for rapid visual diagnostics. XGobi includes an extensive online help facility. XGobi can be integrated in other software systems, as has been done for the data analysis language S, the geographic information system (GIS) Arc View?, and the interactive multidimensional scaling program XGvis. XGobi is implemented in the X Window System? for portability as well as the ability to run across a network.     

The S-Related Dynamic Convex Valuation in the Brownian Motion Setting

Let be an array of row-wise exchangeable random elements in a separable Banach space. Strong laws of large numbers are obtained for under certain moment conditions on the random variables and a condition relating to nonorthogonality. By using reverse martingale techniques, similar results are obtained for triangular arrays of random elements inseparable Banach spaces which are row-wise exchangeable