An Augmentation Algorithm for the Maximum Weighted Stable Set Problem

Edge projection is a specialization of Lovász and Plummer's clique reduction when restricted to edges. A concept of augmenting sequences of edge-projections is defined w.r.t. a stable set S. It is then proved the equivalence between the optimality of S and the existence of an augmenting sequence w.r.t. S. This result is then exploited to develop a new tabu-search heuristic for the Maximum Stable Set Problem (weighted and unweighted). The resulting code proved to be competitive with the best codes presented in the literature.     

Computation of Error Bounds for P-matrix Linear Complementarity Problems

We give new error bounds for the linear complementarity problem where the involved matrix is a P-matrix. Computation of rigorous error bounds can be turned into a P-matrix linear interval system. Moreover, for the involved matrix being an H-matrix with positive diagonals, an error bound can be found by solving a linear system of equations, which is sharper than the Mathias-Pang error bound. Preliminary numerical results show that the proposed error bound is efficient for verifying accuracy of approximate solutions. This work is partly supported by a Grant-in-Aid from Japan Society for the Promotion of Science.     

极小化加权总完工时间的分批排序问题

本文讨论了分批排序中极小化加权总完工时间的两个问题.就所有工件的加工时间都相等这一特殊情况,分别给出两个算法,并证明了算法的最优性.     

订单带多类工件时的最大迟后问题

本文考虑多工类工件的单机排序问题,每一客户提供一由若干工件组成的订单,总共n个工件又分成k个类,当机器从加工某类中的工件转向加工不同于它的第i类工件时需一调整时间S_i,每一订单有一给定的应交工时间,所考虑目标函数是使订单的最大迟后最小,相应这一排序问题的三种模式,文中分别给出了一多项式算法,分枝定界算法和动态规划解法。     

Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain

In this paper, we study the problem of moving $n$ n sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an $O(n^2\log n)$ O ( n 2 log n ) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes $O(n^2)$ O ( n 2 ) time. We present an $O(n\log n)$ O ( n log n ) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes $O(n)$ O ( n ) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in $O(n)$ O ( n ) time, improving the previously best $O(n^2)$ O ( n 2 ) time solution.     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

Imprecise expectations for imprecise linear filtering

In most sensor measure based applications, the raw sensor signal has to be processed by an appropriate filter to increase the signal-to-noise ratio or simply to recover the signal to be measured. In both cases, the filter output is obtained by convoluting the sensor signal with a supposedly known appropriate impulse response. However, in many real life situations, this impulse response cannot be precisely specified. The filtered value can thus be considered as biased by this arbitrary choice of one impulse response among all possible impulse responses considered in this specific context. In this paper, we propose a new approach to perform filtering that aims at computing an interval valued signal containing all outputs of filtering processes involving a coherent family of conventional linear filters. This approach is based on a very straightforward extension of the expectation operator involving appropriate concave capacities.     

IDEA (Imprecise Data Envelopment Analysis) with CMDs (Column Maximum Decision Making Units)

IDEA (Imprecise Data Envelopment Analysis) extends DEA so it can simultaneously treat exact and imprecise data where the latter are known only to obey ordinal relations or to lie within prescribed bounds. AR-IDEA extends this further to include AR (Assurance Region) and the like approaches to constraints on the variables. In order to provide one unified approach, a further extension also includes cone-ratio envelopment approaches to simultaneous transformations of the data and constraints on the variables. The present paper removes a limitation of IDEA and AR-IDEA which requires access to actually attained maximum values in the data. This is accomplished by introducing a dummy variable that supplies needed normalizations on maximal values and this is done in a way that continues to provide linear programming equivalents to the original problems. This dummy variable can be regarded as a new DMU (Decision Making Unit), referred to as a CMD (Column Maximum DMU).     

资源有限的加权总完工时间单机排序问题

本讨论资源有限的加权总工时间单机排序问题，对现在仍为OPEN问题1｜pj=bj-ajuj，∑uj≤U｜∑wjCj给出了一个有关最优解中最优资源分配的重要性质，并利用该性质分别给出了三种情况bj=b,wj=w,aj=a；bj=b,wj=w,uj=u；aj=a,wj=w,uj=u的最优算法。     

Sharp Error Estimate for Maximum Likelihood Estimator of Nonstationary Diffusion Processes

We consider the maximum likelihood estimator of the unknown parameter in a class of nonstationary diffusion processes. We give further a precise estimate for the error of the estimator.     

Uniform Estimate for Maximum of Randomly Weighted Sums with Applications to Ruin Theory

This paper obtains the uniform estimate for maximum of sums of upper-tail independent and heavy-tailed random variables with nonnegative dependent random weights. Then the applications to ruin probabilities in a discrete time risk model with dependent gross losses and dependent stochastic returns are considered.     

Error Estimates for the Adaptive Computation of a Scalar Three Well Problem

We investigate the numerical approximation of Young measure solutions appearing as generalised solutions in scalar non‐convex variational problems. A priori and a posteriori error estimates for a macroscopic quantity, i.e., the stress, are given. Numerical experiments for a scalar three well problem, occurring as a subproblem in the theory of phase transitions in crystalline solids, show that the computational effort can be significantly reduced using an adaptive mesh‐refinement strategy combined with an active set technique by Carstensen and Roubíček.     

差错概率最小化机场安检员在岗模式问题研究

随着国内外安全形势不断严峻,机场安检作为民航安全的重要屏障面临着巨大的压力。安检人员疲劳程度是影响安检差错的主要因素之一。在不改变现有上班模式下,已知不同时段的客流特征、安检员连续在岗时间和安检正确率的关系,建立双目标非线性0~1规划模型,合理安排不同时段内安检人员数量及其连续在岗工作时间模式,使得在安检错误放行概率不高于一定标准的条件下保证安检错误报警概率最小及人员总数最小。文章最后根据模型特点设计了算法并给出了算例。     

On Koetter's Algorithm and the Computation of Error Values

In this article, we show that Koetter's algorithm for decoding one-point codes can compute error evaluator polynomials as well. We also show that the error evaluators do not need to be computed. The updating functions used in Koetter's algorithm can be used to compute error values instead.     

加权完工时间和的调整时间可分离Flow shop排序问题

讨论了2台机器调整时间可分离的FlowShop排序问题,目标函数为极小化加权完工时间和.给出了对于一种特殊情况,问题存在多项式最优算法的充分条件.接着又给出了求解该问题的一个分枝定界法.     

Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time

The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence independent setup time preceding the processing of each group. The setup times and the job processing times are controllable through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource. Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming. This research was supported in part by The Hong Kong Polytechnic University under grant number G-T246 and the Research Grants Council of Hong Kong under grant number PolyU 5191/01E. In addition, the research of M.Y. Kovalyov was supported by INTAS under grant number 00-217.     

Computation of the Distribution of the Maximum of Stationary Gaussian Processes

To test the presence of signal in a “signal plus noise” model, the maximum of the observation is a good statistic. To compute threshold or power, it is necessary to compute the distribution of this statistic under a stationary model. Unfortunately, no general theoretical solutions exist. The paper presents a numerical solution in the case of stationary Gaussian processes on the real line with differentiable sample paths. It is based on the so called “Record method” followed by quasi Monte Carlo integration. An explicit evaluation of the error, which is new is given. Our method applies also, of course, to random sequences and provides some lower bound of the tail for processes with non differentiable paths. Some examples are given at the end that concern both continuous and discrete time cases.     

Stable Computation of Maximum Likelihood Estimates in Identity Link Poisson Regression

Identity link Poisson regression is useful when the mean of a count variable depends additively on a collection of predictor variables. It is particularly important in epidemiology, for modeling absolute differences in disease incidence rates as a function of covariates. A complication of such models is that standard computational methods for maximum likelihood estimation can be numerically unstable due to the nonnegativity constraints on the Poisson means. Here we present a straightforward and flexible method that provides stable maximization of the likelihood function over the constrained parameter space. This is achieved by conducting a sequence of maximizations within subsets of the parameter space, after which the global maximum is identified from among the subset maxima. The method adapts and extends EM algorithms that are useful in specialized applications involving Poisson deconvolution, but which do not apply in more general regression contexts. As well as allowing categorical and continuous covariates, the method has the flexibility to accommodate covariates with an unspecified isotonic form. Its computational reliability makes it particularly useful in bootstrap analyses, which may require stable convergence for thousands of implementations. Computations are illustrated using epidemiological data on occupational mortality, and biological data on crab population counts. This article has supplementary material online.     

Imprecise probabilities for representing ignorance about a parameter

This paper distinguishes between objective probability—or chance—and subjective probability. Most statistical methods in machine learning are based on the hypothesis that there is a random experiment from which we get a set of observations. This random experiment could be identified with a chance or objective probability, but these probabilities depend on some unknown parameters. Our knowledge of these parameters is not objective and in order to learn about them, we must assess some epistemic probabilities about their values. In some cases, our objective knowledge about these parameters is vacuous, so the question is: What epistemic probabilities should be assumed? In this paper we argue for the assumption of non-vacuous (a proper subset of [0, 1]) interval probabilities. There are several reasons for this; some are based on the betting interpretation of epistemic probabilities while others are based on the learning capabilities under the vacuous representation. The implications of the selection of epistemic probabilities in different concepts as conditioning and learning are studied. It is shown that in order to maintain some reasonable learning capabilities we have to assume more informative prior models than those frequently used in the literature, such as the imprecise Dirichlet model.