Handling precedence constraints in scheduling problems by the sequence pair representation

In this paper, we show that sequence pair (SP) representation, primarily applied to the rectangle packing problems appearing in the VLSI industry, can be a solution representation of precedence constrained scheduling. We present three interpretations of sequence pair, which differ in complexity of schedule evaluation and size of a corresponding solution space. For each interpretation we construct an incremental precedence constrained SP neighborhood evaluation algorithm, computing feasibility of each solution in the insert neighborhood in an amortized constant time per examined solution, and prove the connectivity property of the considered neighborhoods. To compare proposed interpretations of SP, we construct heuristic and metaheuristic algorithms for the multiprocessor job scheduling problem, and verify their efficiency in the numerical experiment.     

On locally optimal invariant unbiased tests for the variance components ratio in mixed linear models

In the paper the problem of testing of two-sided hypotheses for variance components in mixed linear models is considered. When the uniformly most powerful invariant test does not exist (see e.g. Das and Sinha, in Proceedings of the second international Tampere conference in statistics, 1987; Gnot and Michalski, in Statistics 25:213–223, 1994; Michalski and Zmyślony, in Statistics 27:297–310, 1996) then to conduct the optimal statistical inference on model parameters a construction of a test with locally best properties is desirable, cf. Michalski (in Tatra Mountains Mathematical Publications 26:1–21, 2003). The main goal of this article is the construction of the locally best invariant unbiased test for a single variance component (or for a ratio of variance components). The result has been obtained utilizing Andersson’s and Wijsman’s approach connected with a representation of density function of maximal invariant (Andersson, in Ann Stat 10:955–961, 1982; Wijsman, in Proceedings of fifth Berk Symp Math Statist Prob 1:389–400, 1967; Wijsman, in Sankhyā A 48:1–42, 1986; Khuri et al., in Statistical tests for mixed linear models, 1998) and from generalized Neyman–Pearson Lemma (Dantzig and Wald, in Ann Math Stat 22:87–93, 1951; Rao, in Linear statistical inference and its applications, 1973). One selected real example of an unbalanced mixed linear model is given, for which the power functions of the LBIU test and Wald’s test (the F-test in ANOVA model) are computed, and compared with the attainable upper bound of power obtained by using Neyman–Pearson Lemma.     

On the Complexity of Constructing Evolutionary Trees

In this paper we study a few important tree optimization problems with applications to computational biology. These problems ask for trees that are consistent with an as large part of the given data as possible. We show that the maximum homeomorphic agreement subtree problem cannot be approximated within a factor of , where N is the input size, for any 0 in polynomial time unless P = NP, even if all the given trees are of height 2. On the other hand, we present an O(N log N)-time heuristic for the restriction of this problem to instances with O(1) trees of height O(1) yielding solutions within a constant factor of the optimum. We prove that the maximum inferred consensus tree problem is NP-complete, and provide a simple, fast heuristic for it yielding solutions within one third of the optimum. We also present a more specialized polynomial-time heuristic for the maximum inferred local consensus tree problem.     

Subhypergraph counts in extremal and random hypergraphs and the fractional <Emphasis Type="Italic">q</Emphasis>-independence

We study the extremal parameter N(n,m,H) which is the largest number of copies of a hypergraph H that can be formed of at most n vertices and m edges. Generalizing previous work of Alon (Isr. J. Math. 38:116–130, 1981), Friedgut and Kahn (Isr. J. Math. 105:251–256, 1998) and Janson, Oleszkiewicz and the third author (Isr. J. Math. 142:61–92, 2004), we obtain an asymptotic formula for N(n,m,H) which is strongly related to the solution α _q (H) of a linear programming problem, called here the fractional q-independence number of H. We observe that α _q (H) is a piecewise linear function of q and determine it explicitly for some ranges of q and some classes of H. As an application, we derive exponential bounds on the upper tail of the distribution of the number of copies of H in a random hypergraph.     

Fiscal harmonization in view of the Euro adoption: Economic implications for Poland

In this paper, we investigate the ex ante effects of fiscal policy harmonization that might be necessary for the adoption of the common currency on economic growth in Poland using a neoclassical dynamic two-sector general equilibrium model. We study two fiscal policy scenarios. In the first one, we adjust all taxes to German and EU-27 levels, respectively, while in the second one, we change only consumption taxes to German and EU-27 levels. We find that in the first scenario, the current Polish taxes yield the highest rate of growth due to lower capital taxation. However, in the second scenario, German and EU-27 taxes yield the highest rate of growth due to the lower consumption tax on capital-intensive good. From a policy perspective, our results suggest that fiscal policy with lower taxes on capital and capital-intensive goods can generate a higher rate of growth in the long-run. In the case of fiscal harmonization, our findings propose adopting only German or EU-27 consumption tax structure into the Polish tax system.     

面向技术安全的机械设计数据库

机械设计中的计算机辅助设计和数据库技术对于技术安全工作正变得越来越重要，它需要CAD系统直接定位于一些特殊类型的机械。本文对数据库技术及设计结果作了介绍。     

General class of covariance structures for two or more repeated factors in longitudinal data analysis

The main difficulty in parametric analysis of longitudinal data lies in specifying covariance structure. Several covariance structures, which usually reflect one series of measurements collected over time, have been presented in the literature. However there is a lack of literature on covariance structures designed for repeated measures specified by more than one repeated factor. In this paper a new, general method of modelling covariance structure based on the Kronecker product of underlying factor specific covariance profiles is presented. The method has an attractive interpretation in terms of independent factor specific contribution to overall within subject covariance structure and can be easily adapted to standard software.