Estimation of Distribution Functions Using Data from Different Environments

Suppose that when a unit operatesin a certain environment, its lifetime has distribution G,and when the unit operates in another environment, its lifetimehas a different distribution, say F. Moreover, supposethe unit is operated for a certain period of time in the firstenvironment and is then transferred to the second environment.Thus we observe a censored lifetime in the first environmentand a failure time of a ``used' unit in the second environment.We propose an EM algorithm approach for obtaining a self-consistentestimator of F. Moreover, suppose using observations from both environments.The case where failure times are subject to right censoring isconsidered as well. We also establish the maximum likelihoodestimator of F. Moreover, suppose when the unit is repairable. Applicationand simulation studies are presented to illustrate the methodsderived.     

Optimal Augmentation of a 2-Vertex-Connected Multigraph to a k-Edge-Connected and 3-Vertex-Connected Multigraph

Given an undirected multigraph G = (V, E) and two positive integers and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an -edge-connected and k-vertex-connected multigraph. In this paper, we show that the problem can be solved in Õ(mn²) time for any fixed and k = 3 if an input multigraph G is 2-vertex-connected, where n = |V| and m is the number of pairs of adjacent vertices in G.     

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.     

CAI函数图形发生器FGG的设计与实现

介绍在Ｗｉｎｄｏｗｓ环境下用ＢｏｒｌａｎｄＣ＋＋３．１开发的通用函数图形发生器的结构和功能，讨论了实现中的表达式求值算法和图形生成算法。ＦＧＧ的主要特点是，对输入的任意一元、二元函数表达式可直接生成对应的二维和三维图形。ＦＧＧ作为ＣＡＩ写作工具的支撑软件，可用于ＣＡＩ课件的开发及演示。     

高等教育最优投资双层规划模型研究

高等教育投资具有"双层"的特点,上层为省级主管部门,下层为高等学校。本文成功运用了双层规划模型,在不考虑高校自筹发展资金投入的情况下,建立了高等教育最优投资双层规划模型,研究了模型最优解的存在性,给出并证明了模型最优解的等价形式,设计了模型解的算法并进行了算法复杂性分析。通过求解模型,可以同时得到省级主管部门和高等学校的最优投资决策方案。文章最后还给出了考虑高校自筹发展资金的两种情况下建立投资模型和求得最优解的方法。     

On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover

The problems dealt with in this paper are generalizations of the set cover problem, min{cx | Ax b, x {0,1}ⁿ}, where c Q₊ⁿ, A {0,1}^{m × n}, b 1. The covering 0-1 integer program is the one, in this formulation, with arbitrary nonnegative entries of A and b, while the partial set cover problem requires only m–K constrains (or more) in Ax b to be satisfied when integer K is additionall specified. While many approximation algorithms have been recently developed for these problems and their special cases, using computationally rather expensive (albeit polynomial) LP-rounding (or SDP-rounding), we present a more efficient purely combinatorial algorithm and investigate its approximation capability for them. It will be shown that, when compared with the best performance known today and obtained by rounding methods, although its performance comes short in some special cases, it is at least equally good in general, extends for partial vertex cover, and improves for weighted multicover, partial set cover, and further generalizations.     

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.     

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.     

Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition

Let G = (V,E) be a plane graph with nonnegative edge weights, and let be a family of k vertex sets , called nets. Then a noncrossing Steiner forest for in G is a set of k trees in G such that each tree connects all vertices, called terminals, in net N _i, any two trees in do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time if G has n vertices and each net contains a bounded number of terminals.