Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

The asymptotic joint distribution of the state occupancy times in an alternating renewal process

An alternating renewal process starts at time zero and visits states 1,2,…,r, 1,2, …,r 1,2, …,r, … in sucession. The time spent in state i during any cycle has cumulative distribution function F_i, and the sojourn times in each state are mutually independent, positive and nondegenerate random variables. In the fixed time interval [0,T], let U_i(T) denote the total amount of time spent in state i. In this note, a central limit theorem is proved for the random vector (U_i(T), 1 ≤ i ≤ r) (properly normed and centered) as T → ∞.     

Test for the extreme value and weibull distributions based on normalized spacings

Discussed in this article are tests for the extreme-value distribution, or, equivalently, for the two-parameter Weibull distribution when parameters are unknown and the sample may be censored. The three tests investigated are based on the median, the mean, and the Anderson-Darling A² statistic calculated from a set zⁱ of values derived from the spacings of the sample. The median and the mean have previously been discussed by Mann, Scheuer, and Fertig [10] and by Tiku and Singh [14]. Asymptotic distributions and points are given for the test statistics, based on recently developed theory, and power studies are conducted to compare them with each other and with two other statistics suitable for the test. Of the normalized spacings tests, A² is recommended overall; the mean also gives good power in many situations, but can be nonconsistent.