Batch-Processing Scheduling with Setup Times

The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.     

Modified Wald statistics for generalized linear models

Summary: Wald statistics in generalized linear models are asymptotically ² distributed. The asymptotic chi–squared law of the corresponding quadratic form shows disadvantages with respect to the approximation of the finite–sample distribution. It is shown by means of a comprehensive simulation study that improvements can be achieved by applying simple finite–sample size approximations to the distribution of the quadratic form in generalized linear models. These approximations are based on a ² distribution with an estimated degree of freedom that generalizes an approach by Patnaik and Pearson. Simulation studies confirm that nominal level is maintained with higher accuracy compared to the Wald statistics.     

Calculating the density and distribution function for the singly and doubly noncentral F

Simple, closed form saddlepoint approximations for the distribution and density of the singly and doubly noncentral F distributions are presented. Their overwhelming accuracy is demonstrated numerically using a variety of parameter values. The approximations are shown to be uniform in the right tail and the associated limitating relative error is derived. Difficulties associated with some algorithms used for exact computation of the singly noncentral F are noted.     

Center and Distinguisher for Strings with Unbounded Alphabet

Consider two sets and of strings of length L with characters from an unbounded alphabet , i.e., the size of is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of is a string that minimizes the maximum of Hamming¹ distance(s, s*) over all string s : s . In contrast, a farthest string t* from maximizes the minimum of Hamming distance(t*,t) over all elements t: t . A distinguisher of from is a string that is close to every string in and far away from any string in . We obtain polynomial time approximation schemes to settle the above problems.     

Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals

Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, is the best known approximation ratio achievable in polynomial time for SBR. A very closely related problem, called Breakpoint Graph Decomposition (BGD), calls for a largest collection of edge disjoint cycles in a suitably-defined graph. It has been shown that for almost all instances SBR is equivalent to BGD, in the sense that any solution of the latter corresponds to a solution of the former having the same value. In this paper, we show how to improve the approximation ratio achievable in polynomial time for BGD, from the previously known to for any > 0. Combined with the results in (Caprara, Journal of Combinatorial Optimization, vol. 3, pp. 149–182, 1999b), this yields the same approximation guarantee for n! – O((n – 5)!) out of the n! instances of SBR on permutations with n elements. Our result uses the best known approximation algorithms for Stable Set on graphs with maximum degree 4 as well as for Set Packing where the maximum size of a set is 6. Any improvement in the ratio achieved by these approximation algorithms will yield an automatic improvement of our result.     

The densest <Emphasis Type="Italic">k</Emphasis>-subgraph problem on clique graphs

The Densest k-Subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The problem is strongly NP-hard, as a generalization of the well known Clique problem and we also know that it does not admit a Polynomial Time Approximation Scheme (PTAS). In this paper we focus on special cases of the problem, with respect to the class of the input graph. Especially, towards the elucidation of the open questions concerning the complexity of the problem for interval graphs as well as its approximability for chordal graphs, we consider graphs having special clique graphs. We present a PTAS for stars of cliques and a dynamic programming algorithm for trees of cliques. M.L. is co-financed within Op. Education by the ESF (European Social Fund) and National Resources. V.Z. is partially supported by the Special Research Grants Account of the University of Athens under Grant 70/4/5821.     

Fast and Accurate Inference for the Smoothing Parameter in Semiparametric Models

A fast and accurate method of confidence interval construction for the smoothing parameter in penalised spline and partially linear models is proposed. The method is akin to a parametric percentile bootstrap where Monte Carlo simulation is replaced by saddlepoint approximation, and can therefore be viewed as an approximate bootstrap. It is applicable in a quite general setting, requiring only that the underlying estimator be the root of an estimating equation that is a quadratic form in normal random variables. This is the case under a variety of optimality criteria such as those commonly denoted by maximum likelihood (ML), restricted ML (REML), generalized cross validation (GCV) and Akaike's information criteria (AIC). Simulation studies reveal that under the ML and REML criteria, the method delivers a near‐exact performance with computational speeds that are an order of magnitude faster than existing exact methods, and two orders of magnitude faster than a classical bootstrap. Perhaps most importantly, the proposed method also offers a computationally feasible alternative when no known exact or asymptotic methods exist, e.g. GCV and AIC. An application is illustrated by applying the methodology to well‐known fossil data. Giving a range of plausible smoothed values in this instance can help answer questions about the statistical significance of apparent features in the data.     

一种基于加权F-范数的半正定矩阵的逼近方法

正定性是许多金融预测模型的重要假设前提，然而从实际样本中得到的相关系数矩阵并不能保证其正定性。为此在介绍如何根据样本设定相关系数矩阵以及范数逼近原理的基础上，如何根据该原理找到与之最接近的相关系数矩阵，即最接近的单位对角半正定对称矩阵。通过实证，验证了其方法的有效性。     

一类混合指数型算子的一致逼近

主要讨论了一类混合指数型算子的一致逼近问题，并给出了逼近阶的估计和特征刻划。     

Landau多项式算子与无界函数逼近

利用扩展乘数法构造了 Landau型多项式算子逼近全空间或有界集上无界函数的若干收敛定理 ,给出了具有一般性的结论 ,从而推广了已有文献的若干结果 .