Stable matching problems with exchange restrictions

We study variants of classical stable matching problems in which there is an additional requirement for a stable matching, namely that there should not be two participants who would prefer to exchange partners. The problem is motivated by the experience of real-world medical matching schemes that use stable matchings, where cases have arisen in which two participants discovered that each of them would prefer the other’s allocation, a situation that is seen as unfair. Our main result is that the problem of deciding whether an instance of the classical stable marriage problem admits a stable matching, with the additional property that no two men would prefer to exchange partners, is NP-complete. This implies a similar result for more general problems, such as the hospitals/residents problem, the many-to-one extension of stable marriage. Unlike previous NP-hardness results for variants of stable marriage, the proof exploits the powerful algebraic structure underlying the set of all stable matchings. In practical matching schemes, however, applicants’ preference lists are typically of short fixed length, and we describe a linear time algorithm for the problem in the special case where all of the men’s preference lists are of length ≤3.     

Exordium for DNA Codes

We describe how deletion-correcting codes may be enhanced to yield codes with double-strand DNA-sequence codewords. This enhancement involves abstractions of the pertinent aspects of DNA; it nevertheless ensures specificity of binding for all pairs of single strands derived from its codewords—the key desideratum of DNA codes– i.e. with binding feasible only between reverse complementary strands. We defer discussing the combinatorial-optimization superincumbencies of code construction. Generalization of deletion similarity to an optimal sequence-alignment score could readily effect advantageous improvements (Kaderali, Master's Thesis, Informatics, U. Köln, 2001) but would render the combinatorics opaque. We mention motivating applications of DNA codes.     

Characterizing the reconstruction and enumerating the patterns of DNA sequences with repeats

A repeat in a DNA sequence is a substring that appears more than once. In DNA sequencing, the occurrence of repeats may hinder the unique reconstruction. In addition, the number of possible reconstructions depends on the pattern of repeats in a DNA sequence. Arratia et al. studied the patterns of DNA sequences with twofold repeats that result in k-way reconstructions. In this paper, multiple-fold repeats, including twofold repeats, are considered. For each pattern of DNA repeats, the possible reconstructions of the DNA sequence are enumerated by its reduced digraph. Then the reconstructions of DNA sequences with repeats are characterized using the pattern graphs. Finally, for DNA sequences with n repeats, the patterns of DNA repeats resulting in k-way reconstruction are enumerated. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.     

Any Maximal Planar Graph with Only One Separating Triangle is Hamiltonian

A graph is hamiltonian if it has a hamiltonian cycle. It is well-known that Tutte proved that any 4-connected planar graph is hamiltonian. It is also well-known that the problem of determining whether a 3-connected planar graph is hamiltonian is NP-complete. In particular, Chvátal and Wigderson had independently shown that the problem of determining whether a maximal planar graph is hamiltonian is NP-complete. A classical theorem of Whitney says that any maximal planar graph with no separating triangles is hamiltonian, where a separating triangle is a triangle whose removal separates the graph. Note that if a planar graph has separating triangles, then it can not be 4-connected and therefore Tutte's result can not be applied. In this paper, we shall prove that any maximal planar graph with only one separating triangle is still hamiltonian.     

基于Windows DNA技术的网络财务系统的实现

随着经济和技术的发展,财务系统网络化已在为一种必然趋势。在对Ｗｉｎｄｏｗｓ分布 式互联网应用框架技术深入分析的基础上,提出了一种实现企业信息集成的网络财务系统框型,结合组件对象模型（ＣＯＭ）组件技术,讨论具有动态浏览特点的网络财务系统的编码方法。     

Iterative Converging Algorithms for Computing Bounds on Durations of Activities in Pert and Pert-Like Models

Since its invention in 1958, Program Evaluation and Review Technique (PERT) has been widely used during the planning, design, and implementation of projects. Pert models the activities of a project as a single source-single sink directed acyclic graph where nodes represent events (end or beginning of activities) and arcs activities. The maximum amount by which an activity can be delayed without delaying the overall project is called the slack. Critical tasks have zero slack whereas all noncritical tasks have positive slacks. Pert is a valuable tool in the management of large projects since it allows to compute the slack of each activity of the project. Such information may be crucial in avoiding cost overruns that would be caused by delays to critical activities and/or excessive delays to noncritical activities. What Pert fails to provide is how one should go about distributing remaining slack on noncritical activities while taking into consideration properties of the activities as well as precedence relationships among them, so as to have reasonable upper bounds on duration of all activities, critical or noncritical. In this paper we propose several algorithms for the distribution of slack on non-critical activities. We show that if one desires to distribute the remaining slack proportionally to the initially assigned activity durations then the problem is in P, and propose an algorithm of linear time complexity. However if one desires to use distribution functions other than the initial durations of activities, then the problem of slack distribution becomes NP-complete. Finding the maximal bounds corresponding to zero-slack solution at the sink requires iterative application of exponential algorithm. For that case we introduce an approximation algorithm of linear time complexity on each iteration. The algorithm iteratively increases bounds on durations of activities and converges to the zero-slack solution on all paths from the source node to the sink node in the Pert-like graph. The algorithms described in this paper were successfully applied to solving timing bounds problems in VLSI design.     

DNA Screening, Pooling Design and Simplicial Complex

Pooling designs are used for DNA library screening. In this paper, we present a construction of pooling design with simplicial complex and establish some general results on the construction.     

Clustering Binary Oligonucleotide Fingerprint Vectors for DNA Clone Classification Analysis

We considered the problem of clustering binarized oligonucleotide fingerprints that attempts to identify clusters. Oligonucleotide fingerprinting is a powerful DNA array based method to characterize cDNA and rRNA libraries and has many applications including gene expression profiling and DNA clone classification. DNA clone classification is the main application for the problem considered in this paper. Most of the existing approaches for clustering use normalized real intensity values and thus do not treat positive and negative hybridization signals equally. This is demonstrated in a series of recent publications where a discrete approach typically useful in the classification of microbial rRNA clones has been proposed. In the discrete approach, hybridization intensities are normalized and thresholds are set such that a value of 1 represents hybridization, a value of 0 represents no hybridization, and an N represents unknown, which is also called a missing value. A combinatorial optimization problem is then formulated attempting to cluster the fingerprints and resolve the missing values simultaneously. It has been examined that missing values cause much difficulty in clustering analysis and most clustering methods are very sensitive to them. In this paper, we turned a little back to the traditional clustering problem, which takes in no missing values but with the revised goal to stabilize the number of clusters and maintain the clustering quality. We adopted the binarizing scheme used in the discrete approach as it is shown to be typically useful for the clone classifications. We formulated such a problem into another combinatorial optimization problem. The computational complexity of this new clustering problem and its relationships to the discrete approach and the traditional clustering problem were studied. We have designed an exact algorithm for the new clustering problem, which is an A* search algorithm for finding a minimum number of clusters. The experimental results on two commonly tested real datasets demonstrated that the A* search algorithm runs fast and performs better than some popular hierarchical clustering methods, in terms of separating clones that have different characteristics with respect to the given oligonucleotide probes.Supported by NSERC and CFI.Supported by NSERC.Supported partially by NSERC, CFI, and NNSF Grant 60373012.     

Probabilistic Nonadaptive and Two-Stage Group Testing with Relatively Small Pools and DNA Library Screening

We use a simple, but nonstandard, incidence relation to construct probabilistic nonadaptive group testing algorithms that identify many positives in a population with a zero probability of yielding a false positive. More importantly, we give two-stage modifications of our nonadaptive algorithms that dramatically reduce the expected number of sufficient pools. For our algorithms, we give a lower bound on the probability of identifying all the positives and we compute the expected number of positives identified. Our method gives control over the pool sizes. In DNA library screening algorithms, where relatively small pools are generally preferred, having control over the pool sizes is an important practical consideration.     

The Enhanced Double Digest Problem for DNA Physical Mapping

The double digest problem is a common NP-hard approach to constructing physical maps of DNA sequences. This paper presents a new approach called the enhanced double digest problem. Although this new problem is also NP-hard, it can be solved in linear time in certain theoretically interesting cases.     

Aligning DNA Sequences to Minimize the Change in Protein

We study an alignment model for coding DNA sequences recently proposed by J. Hein that takes into account both DNA and protein information, and attempts to minimize the total amount of evolution at both DNA and protein levels. Assuming that the gap penalty function is affine, we design a quadratic time dynamic programming algorithm for the model. Although the algorithm theoretically solves an open question of Hein, its running time is impractical because of the large constant factor embedded in the quadratic time complexity function. We therefore consider a mild simplification named Context-free Codon Alignment of Hein's model and present a much more efficient algorithm for the simplified model. The algorithms have been implemented and tested on both real and simulated sequences, and it is found that they produce almost identical alignments in most cases. Furthermore, we extend our model and design a heuristic algorithm to handle frame-shift errors and overlapping frames in coding regions.     

Efficient Algorithms for Local Alignment Search

We present efficient algorithms for local alignment search in biological sequences. These algorithms identify maximal segment pairs (MSPs). Our algorithms have the potential of performing better than BLAST (Basic Local Alignment Search Tool) and also are efficiently parallelizable. We employ Fast Fourier Transforms (FFTs). Though several attempts have been made in the past to employ FFTs in sequence analysis, they fail to capture local similarities. Our algorithms employ FFTs in a novel way to identify local similarities. FFT-based techniques have the attractive feature of benefiting from ultrafast special purpose hardware available for digital signal processing.     

基于DNA遗传算法的表面贴装生产线负荷优化分配

印制电路板组装任务的负荷优化分配包含设备约束、工艺约束等大量约束,是电子行业表面贴装生产线中的一类重要优化问题。其优化目标是在生产节拍给定和一定约束条件下,使得不同贴装机负荷均衡,任务分配达到最优。首先,根据不同表面贴装机、不同吸嘴及多种类型元件匹配的的复杂性,提出贴装机任务分配组合优化的问题;然后分析设备和元件的参数、组装可行性、贴装时间,以及贴装优化关系等因素,并提出假设条件,建立了平衡率最大化条件下的负荷分配组合优化的数学模型;最后,针对贴装生产线负荷分配问题的复杂性与特殊性,通过改良编码方式后的DNA遗传算法来优化组合数学模型,计算适应度,并借助MATLAB进行仿真求解,进而找到最优解。结果表明：本文提出的贴装生产线负荷分配方法可以解决带复杂约束的印制电路板组装负荷优化分配问题,提高设备的平衡率和生产效率,促进生产线的优化运行。     

Even Cycles and Perfect Matching Problems with Side Constraints

We study two different types of graphs that contain even cycles and, possibly, some chords. The objective is to analyze some properties of these types of graphs that can be used to solve perfect matching optimization problems with side constraints. In particular, we obtain the maximum number of edges of certain classes that can occur in the solutions to the considered problems. Finally, we apply the obtained results to derive a class of valid inequalities and a possible enumerative scheme.     

Axial solutions for multiple objective linear problems. An application to target setting in DEA models with preferences

In this paper we introduce the class of axial solutions for multiple objective optimization problems in contexts in which partial information on preference weights is available. These solutions combine the use of an improvement axis to direct the search of the most preferred result with the concept of efficiency with respect to preference information.     

Assisting employees with drinking problems: Changes in mental health, job perceptions and work performance

A sample of 104 British transportation employees with alcohol-related problems were examined for changes in mental health and job perceptions before and after a company-based counselling programme. Data was mainly obtained by means of structured interviews. When clients were assessed at a 6-month follow-up, significant positive changes were found for the group as a whole in terms of context-free mental health, self- and supervisor ratings of work performance as well as measures of absenteeism. Small positive differences were observed for measures relating to perceived work demands. However, no significant differences were observed for the measures of job satisfaction and job commitment. The findings are discussed in relation to the expected client and organizational outcomes of workplace counselling interventions.     

有限分布信息条件下MTO再制造系统提前期优化

在只知道零部件再制造时间有限分布信息（即一阶矩、二阶矩）条件下,基于MTO再制造策略研究由再制件和采购件组成的再制品的提前期问题,该问题被描述为一个矩问题。以最小化库存持有成本和缺货成本为目标建立min-max优化模型,在具有相同一阶矩、二阶矩的分布集合中寻找使最坏分布下的目标函数值最小的最优再制造提前期。最后通过算例进行了验证,求解结果与传统假设再制造时间服从正态分布、均匀分布得到的结果吻合较好,但本文的方法更符合生产实际,能保证在具有同样一阶矩和二阶矩的所有分布情况下的解的鲁棒性,对企业制定再制造计划、采购计划等具有现实的指导意义。     

线性二层决策问题的期望收益模型及算法

下层反应不唯一时 ,如何确定二层线性决策问题最优策略为一非确定型决策问题 .对此类问题 ,本文通过引入领导者对追随者合作程度的期望系数 ,提出期望收益模型 .利用双罚函数把该问题转换为一单层次优化问题 ,并提出一种求解问题的全局优化算法 .应用此模型分析二层线性问题可知 :对存在不确定性反应的二层决策问题 ,下层追随者与上层领导者的合作态度是领导者确定其最优策略的关键 ;对下层追随者而言 ,某些情况下 ,采取与领导者部分合作的态度对其自身收益的提高是合理的     

A comparison of spreadsheet users with different levels of experience

How do experienced spreadsheet users compare to inexperienced ones, and what light can this comparison shed on spreadsheet best practices? This is the question we address in this paper, using the results from a survey of nearly 1600 respondents. This survey was completed by a wide range of spreadsheet users and focused on their significant characteristics and practices. We were interested in their training, experience, collaboration, and quality control methods. We also examined the number of spreadsheet functions they used regularly, the manner in which they created spreadsheets, and the types of tests they used to check results. We compared two subgroups corresponding to two extremes with respect to their self-reported level of experience and skill. Each subgroup was represented by roughly 10% of the total respondents. Our results suggest that there is a substantial difference between these groups, not only in their personal backgrounds and the corporate setting within which they work, but also in their individual spreadsheet skills and practices. We find that the most experienced subgroup exhibits many desirable characteristics and practices.     

考虑随机利率和通货膨胀的连续时间资产组合选择

通过随机控制技术、Bellman最优性原理和HJB方程研究了通货膨胀、随机利率和交易成本等因素影响下的连续时间投资组合选择的最优化问题,将利率假定为服从Vasicek利率模型的随机过程,应用连续时间的动态均值-方差方法得到符合实际意义的HJB方程,通过多重网格的数值逼近方法求解相应的HJB方程得到双目标优化问题的最优投资策略。用实证方法与国内证券市场上代表性指数基金进行对比研究,发现通货膨胀和利率变动以及经济环境和投资者的异质信念等因素均会对最优策略产生影响,有效前沿会随之发生变化,债券与股票之间的投资比例并不是简单维持固定比例就可以保证总资产最优,拓展了基金分离定理。考虑通货膨胀和交易成本等因素的资产组合选择模型可以实实在在为机构投资者提供客观的实践指导和科学的理论依据。