Distributed match-making

In many distributed computing environments, processes are concurrently executed by nodes in a store- and-forward communication network. Distributed control issues as diverse as name server, mutual exclusion, and replicated data management involve making matches between such processes. We propose a formal problem called distributed match-making as the generic paradigm. Algorithms for distributed match-making are developed and the complexity is investigated in terms of messages and in terms of storage needed. Lower bounds on the complexity of distributed match-making are established. Optimal algorithms, or nearly optimal algorithms, are given for particular network topologies.The work of the second author was supported in part by the Office of Naval Research under Contract N00014-85-K-0168, by the Office of Army Research under Contract DAAG29-84-K-0058, by the National Science Foundation under Grant DCR-83-02391, and by the Defence Advanced Research Projects Agency (DARPA) under Contract N00014-83-K-0125. Current address of both authors: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.     

Randomized range-maxima in nearly-constant parallel time

Given an array ofn input numbers, therange-maxima problem is that of preprocessing the data so that queries of the type what is the maximum value in subarray [i..j] can be answered quickly using one processor. We present a randomized preprocessing algorithm that runs inO(log^* n) time with high probability, using an optimal number of processors on a CRCW PRAM; each query can be processed in constant time by one processor. We also present a randomized algorithm for a parallel comparison model. Using an optimal number of processors, the preprocessing algorithm runs inO( (n)) time with high probability; each query can be processed inO ( (n)) time by one processor. (As is standard, (n) is the inverse of Ackermann function.) A constant time query can be achieved by some slowdown in the performance of the preprocessing stage.     

A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.     

An improved algorithm for finding the median distributively

Given two processes, each having a total-ordered set ofn elements, we present a distributed algorithm for finding median of these 2n elements using no more than logn +O(logn) messages, but if the elements are distinct, only logn +O(1) messages will be required. The communication complexity of our algorithm is better than the previously known result which takes 2 logn messages.     

A Holistic Evolutionary and 3D Pharmacophore Modelling Study Provides Insights into the Metabolism,Function, and Substrate Selectivity of the Human Monocarboxylate Transporter 4 (hMCT4)

Monocarboxylate transporters (MCTs) are of great research interest for their role in cancer cell metabolism and their potential ability to transport pharmacologically relevant compounds across the membrane. Each member of the MCT family could potentially provide novel therapeutic approaches to various diseases. The major differences among MCTs are related to each of their specific metabolic roles, their relative substrate and inhibitor affinities, the regulation of their expression, their intracellular localization, and their tissue distribution. MCT4 is the main mediator for the efflux of L-lactate produced in the cell. Thus, MCT4 maintains the glycolytic phenotype of the cancer cell by supplying the molecular resources for tumor cell proliferation and promotes the acidification of the extracellular microenvironment from the co-transport of protons. A promising therapeutic strategy in anti-cancer drug design is the selective inhibition of MCT4 for the glycolytic suppression of solid tumors. A small number of studies indicate molecules for dual inhibition of MCT1 and MCT4; however, no selective inhibitor with high-affinity for MCT4 has been identified. In this study, we attempt to approach the structural characteristics of MCT4 through an in silico pipeline for molecular modelling and pharmacophore elucidation towards the identification of specific inhibitors as a novel anti-cancer strategy.     

基于危险理论的人工免疫原理与应用*

侧重以危险理论的基本机制为线索,对危险理论的研究现状加以系统论述.首先以危险理论的免疫模型入手,归纳提炼出仿真机理并建立起隐喻算法;介绍其中具有代表性领域中的应用情况;最后对基于危险理论的人工免疫研究的下一步工作进行展望.     

基于遗传算法的产品制造的优化调度

研究了企业产品制造的调度问题 ,并建立了调度的最小模型。引入效率函数 ,运用遗传退火进化算法实现了调度决策的优化 ;提出了将遗传退火算法和分派规则相结合的调度策略和动态编码的方法 ,放宽了约束条件 ,提高了搜索效率和速度 ,保证其全局收敛性。     

Particle-in-Cell algorithms for emerging computer architectures

We have designed Particle-in-Cell algorithms for emerging architectures. These algorithms share a common approach, using fine-grained tiles, but different implementations depending on the architecture. On the GPU, there were two different implementations, one with atomic operations and one with no data collisions, using CUDA C and Fortran. Speedups up to about 50 compared to a single core of the Intel i7 processor have been achieved. There was also an implementation for traditional multi-core processors using OpenMP which achieved high parallel efficiency. We believe that this approach should work for other emerging designs such as Intel Phi coprocessor from the Intel MIC architecture.     

A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

In recent years growing interest in local distributed algorithms has widely been observed. This results from their high resistance to errors and damage, as well as from their good performance, which is independent of the size of the network. A local deterministic distributed algorithm finding an approximation of a Minimum Dominating Set in planar graphs has been presented by Lenzen et al., and they proved that the algorithm returns a 130-approximation of the Minimum Dominating Set. In this article we will show that the algorithm is two times more effective than was previously assumed, and we prove that the algorithm by Lenzen et al. outputs a 52-approximation to a Minimum Dominating Set. Therefore the gap between the lower bound and the approximation ratio of the best yet local deterministic distributed algorithm is reduced by half.     

Novel multi-objective resource allocation and activity scheduling for fourth party logistics

In order to reduce logistic costs, the scheduling of logistic tasks and resources for fourth party logistics (4PL) is studied. Current scheduling models only consider costs and finish times of each logistic resource or task. Not generally considered are the joint cost and time between two adjacent activities for a resource to process and two sequential activities of a task for two different resources to process are ignored. Therefore, a multi-objective scheduling model aiming at minimizing total operation costs, finishing time and tardiness of all logistic tasks in a 4PL is proposed. Not only are the joint cost and time of logistic activities between two adjacent activities and two sequential activities included but the constraints of resource time windows and due date of tasks are also considered. An improved nondominated sorting genetic algorithm (NSGA-II) is presented to solve the model. The validity of the proposed model and algorithm are verified by a corresponding case study.