Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application

We show that an n-vertex bipartite K_3,3-free graph with n?3 has at most 2n−4 edges and that an n-vertex bipartite K₅-free graph with n?5 has at most 3n−9 edges. These bounds are also tight. We then use the bound on the number of edges in a K_3,3-free graph to extend two known NC algorithms for planar graphs to K_3,3-free graphs.     

Efficient primal-dual heuristic for a dynamic location problem

In this paper the dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal-dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal-dual heuristic based on the work of Erlenkotter [A dual-based procedure for uncapacitated facility location. Operations Research 1978;26:992–1009] and Van Roy and Erlenkotter [A dual-based procedure for dynamic facility location. Management Science 1982;28:1091–105] was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated as in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.     

Processor Utilization Bounds for Real-Time Systems With Precedence Constraints

This paper presents a novel approach to computing tight upper bounds on the processor utilization for general real-time systems where tasks are composed of subtasks and precedence constraints may exist among subtasks of the same task. By careful analysis of preemption effects among tasks, the problem is formulated as a set of linear programming (LP) problems. Observations are made to reduce the number of LP problem instances required to be solved, which greatly improves the computation time of the utilization bounds. Furthermore, additional constraints are allowed to be included under certain circumstances to improve the quality of the bounds.     

磁场和库仑场对量子点中强耦合束缚极化子性质的影响

采用线性组合算符和幺正变换方法研究了磁场和库仑场对半导体量子点中强耦合极化子性质的影响.导出了强耦合束缚磁极化子的振动频率和基态能量与量子点的有效受限长度、库仑束缚势、磁场的回旋共振频率和电子-声子耦合强度的变化关系.数值计算结果表明:强耦合束缚磁极化子的振动频率和基态能量随量子点的有效受限长度的减小而迅速增大,随磁场的回旋共振频率的增加而增大.基态能量随电子-声子耦合强度和库仑束缚势的增加而减少.     

On the design of multiple key hashing files for concurrent orthogonal range retrieval between two disks

This paper concerns the following problem: given a set of multi-attribute records, a fixed number of buckets and a two-disk system, arrange the records into the buckets and then store the buckets between the disks in such a way that, over all possible orthogonal range queries (ORQs), the disk access concurrency is maximized. We shall adopt the multiple key hashing (MKH) method for arranging records into buckets and use the disk modulo (DM) allocation method for storing buckets onto disks. Since the DM allocation method has been shown to be superior to any other allocation methods for allocating an MKH file onto a two-disk system for answering ORQs, the real issue is knowing how to determine an optimal way for organizing the records into buckets based upon the MKH concept.

A performance formula that can be used to evaluate the average response time, over all possible ORQs, of an MKH file in a two-disk system using the DM allocation method is first presented. Based upon this formula, it is shown that our design problem is related to a notoriously difficult problem, namely the Prime Number Problem. Then a performance lower bound and an efficient algorithm for designing optimal MKH files in certain cases are presented. It is pointed out that in some cases the optimal MKH file for ORQs in a two-disk system using the DM allocation method is identical to the optimal MKH file for ORQs in a single-disk system and the optimal average response time in a two-disk system is slightly greater than one half of that in a single-disk system.     

用热失重法确定水合粘土水分含量及存在形式

文章以蒙脱土为例，采用热失重法定性定量确定了水合粘土中结合水类型、界限及其相对含量，并与等温吸附法结果进行了对比。结果表明，用该方法得到的水合蒙脱土中各种水分的相对含量及总含水量与等温吸附实验结果相一致。热失重（25~250 ℃）分析结果表明，水合蒙脱土中水分子主要存在自由水、松散吸附结合水、紧密吸附水（强吸附结合水）3种状态，分别对应于25~75 ℃、75~120 ℃、120~230 ℃区间里的失水。从热失重（25~250 ℃）规律来看，仍存在两个明显的转折点p/ps=0.9、0.98，它们为粘土-水体系的两个特征湿度，前者为粘土表面强结合水与松散结合水（渗透结合水）之间的界限，后者为松散结合水与自由水之间的界限，这验证了等温吸附法确定的两个特征湿度及对粘土表面结合水界限划分的正确性。     

The Gender Congruency Effect and the Selection of Freestanding and Bound Morphemes: Evidence From Croatian.

The authors report 3 picture-word interference experiments in which they explore some properties of the agreement process in speech production. In Experiment 1, Croatian speakers were asked to produce utterances in which the noun's gender value had an impact on the selection of gender-marked freestanding morphemes (pronouns) while ignoring the presentation of same- or different-gender distractor words. In Experiments 2 and 3, Croatian speakers were asked to name the same pictures using noun phrases in which the noun's gender value surfaced as an inflectional suffix. Different-gender distractors interfered more than same-gender distractors (the gender congruency effect) in Experiment 1, but not in Experiments 2 and 3. These contrasting results show that the cause of the gender congruency effect is not at the level where lexical-grammatical information is selected but at the level of selection of freestanding morphemes. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Search for the upper bound of Bayesian estimates of the parameter in an exponential failure model with two known quantiles of an a priori distribution function

A fast exact algorithm of searching for the upper bound of Bayesian estimates for the parameter of the exponential distribution under the condition that an a priori distribution belongs to the class of all distribution functions with two equal quantiles. This problem arises in analyzing the sensitivity of Bayesian estimates to the choice of an a priori distribution in an exponential failure model. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 90–102, January–February 2007.     

搜索三个不同坏硬币的测试次数

§1.简介 设S={c_1,c_2,…,c_n}是由n个外观相同的硬币组成的集合,其中恰有m个稍重的坏硬币,试用最少的测试次数找出这m个坏硬币.以μ_m(n)表示最少测试次数,由信息论可知     

An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks

Formulating the minimum concave cost capacitated network flow problem as an integer concave minimization problem, we establish finite branch and bound algorithms, in which the branching operation is the so–called integral rectangular partition and the bounding procedure is performed by the classical minimum linear cost flow problem on subnetworks. For the special case that the flow cost function is concave on a fixed number of arcs and linear on the others, an upper bound of the running time is given. Received: 19 July 1996 / Accepted: 8 July 1997