排序方式: 共有36条查询结果,搜索用时 15 毫秒
1.
Leszek Gasieniec Jesper Jansson Andrzej Lingas Anna Östlin 《Journal of Combinatorial Optimization》1999,3(2-3):183-197
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. 相似文献
2.
3.
Andrzej Dudek Joanna Polcyn Andrzej Ruciński 《Journal of Combinatorial Optimization》2010,19(2):184-199
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. 相似文献
4.
Andrzej Kozik 《Journal of Combinatorial Optimization》2017,33(2):445-472
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. 相似文献
5.
6.
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. 相似文献
7.
On locally optimal invariant unbiased tests for the variance components ratio in mixed linear models
Andrzej Michalski 《Statistical Papers》2009,50(4):855-868
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. 相似文献
8.
Jerzy WROBEL Andrzeji MACHNIEWSKI 《内蒙古工业大学学报》2001,20(2):110-113
机械设计中的计算机辅助设计和数据库技术对于技术安全工作正变得越来越重要,它需要CAD系统直接定位于一些特殊类型的机械。本文对数据库技术及设计结果作了介绍。 相似文献
9.
10.
Allotment gardens are a key feature of the urban landscape, providing numerous benefits beyond those of food production. These include ecosystem services such as local climate modification, pollination, and providing a pleasant location for socialising. The biodiversity of flora underpins many of these ecosystem services. The aims of this study are to assess the spontaneous vascular flora of urban allotment gardens and derive estimates of the species richness and diversity. In doing so, the specific position of allotment gardens within urban green infrastructure will be revealed and the role of allotment users in shaping local biodiversity determined. 358 species of spontaneous flora were recorded in 11 representative allotment garden estates (total area 150 ha) in Poznań, Poland. Fourteen biodiversity features were taken into account. The investigated areas exhibited high plant species richness, high diversity, low synanthropisation level, and contained valuable geobotanical elements, including plants of key importance for the European Community. For these reasons, allotment gardens should be considered as biodiversity hotspots for native species within urban green infrastructure. Based on an analysis of the spatial and functional organization of 110 individual plots, four types of usage, and corresponding plant diversity have been distinguished. The composition of the flora depends mostly on spatial and functional organization of allotment gardens and, to a much lesser extent, on the habitat conditions, which on individual plots varied very little. The high species richness and diversity in allotment gardens has important consequences for urban planning. 相似文献