基于有限障碍的全牛顿步内点算法

针对线性规划问题,文中引入了一种与传统障碍函数不同的新的障碍函数,其在可行域边界上的取值是有限的.沿此有限障碍函数所确定的新的搜索方向,给出了短步长全牛顿步内点算法,结果证明该算法具有目前求解线性规划问题最好的复杂性界.     

Hierarchies of recursive computations†

A recursive version of the Turing machine model is used to analyze the time and storage complexity of recursive algorithms. Hierarchy theorems are proven for time and for width of recursion (the amount of storage used at a level). A particular language is shown to be the “hardest” language to recognize without recursion. Previous results relating recursive and non-recursive time bounded computations are sharpened.     

On the complexity of a two-point boundary value problem in different settings

We study the complexity of a two-point boundary value problem. We concentrate on the linear problem of order k with separated boundary conditions. Right-hand side functions are assumed to be r times differentiable with all derivatives bounded by a constant. We consider three models of computation: deterministic with standard and linear information, randomized and quantum. In each setting, we construct an algorithm for solving the problem, which allows us to establish upper complexity bounds. In the deterministic setting, we show that the use of linear information gives us a speed-up of at least one order of magnitude compared with the standard information. For randomized algorithms, we show that the speed-up over standard deterministic algorithms is by 1/2 in the exponent. For quantum algorithms, we can achieve a speed-up by one order of magnitude. We also provide lower complexity bounds. They match upper bounds in the deterministic setting with the standard information, and almost match upper bounds in the randomized and quantum settings. In the deterministic setting with the linear information, a gap still remains between the upper and lower complexity bounds.     

Drift conditions for estimating the first hitting times of evolutionary algorithms

For the global optimization problems with continuous variables, evolutionary algorithms (EAs) are often used to find the approximate solutions. The number of generations for an EA to find the approximate solutions, called the first hitting time, is an important index to measure the performance of the EA. However, calculating the first hitting time is still difficult in theory. This paper proposes some new drift conditions that are used to estimate the upper bound of the first hitting times of EAs for finding the approximate solutions. Two case studies are given to show how to apply these conditions to estimate the first hitting times.     

The complexity for partitioning graphs by monochromatic trees,cycles and paths

Let G be an edge-coloured graph. We show in this paper that it is NP-hard to find the minimum number of vertex disjoint monochromatic trees which cover the vertices of the graph G. We also show that there is no constant factor approximation algorithm for the problem unless P?=?NP. The same results hold for the problem of finding the minimum number of vertex disjoint monochromatic cycles (paths, respectively) which cover the vertices of the graph.     

Parallel breadth-first search algorithms for trees and graphs

Parallel Breadth-First Search (BFS) algorithms for ordered trees and graphs on a shared memory model of a Single Instruction-stream Multiple Data-stream computer are proposed. The parallel BFS algorithm for trees computes the BFS rank of eachnode of an ordered tree consisting of n nodes in time of 0(β log n) when 0(n ^1+1/β) processors are used, β being an integer greater than or equal to 2. The parallel BFS algorithm for graphs produces Breadth-First Spanning Trees (BFSTs) of a directedgraph G having n nodes in time 0(log d.log n) using 0(n ³) processors, where d is the diameter of G If G is a strongly connected graph or a connected undirected graph the BFS algorithm produces n BFSTs, each BFST having a different start node.     

A new approach to rectangle intersections part I

Rectangle intersections involving rectilinearly-oriented (hyper-) rectangles in d-dimensional real space are examined from two points of view. First, a data structure is developed which is efficient in time and space and allows us to report all d-dimensional rectangles stored which intersect a d-dimensional query rectangle. Second, in Part II, a slightly modified version of this new data structure is applied to report all intersecting pairs of rectangles of a given set. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions.     

Time-bounded controlled bidirectional grammars

We study regularly controlled bidirectional (RCB) grammars from the viewpoint of time-bounded grammars. RCB-grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. Several modes of derivation can be distinguished for this kind of grammar. A time bound on such a grammar is a measure of its derivational complexity. For some families of time bounds and for some modes of derivation we establish closure properties and a normal form theorem. In addition parsing algorithms are given for some modes of derivation. We conclude with considering generalizations with respect to the family of control languages and the family of bounding functions..     

Quality aspects for component‐based systems: A metrics based approach

In component‐based development, software systems are built by assembling components already developed and prepared for integration. To estimate the quality of components, complexity, reusability, dependability, and maintainability are the key aspects. The quality of an individual component influences the quality of the overall system. Therefore, there is a strong need to select the best quality component, both from functional and nonfunctional aspects. The present paper produces a critical analysis of metrics for various quality aspects for components and component‐based systems. These aspects include four main quality factors: complexity, dependency, reusability, and maintainability. A systematic study is applied to find as much literature as possible. A total of 49 papers were found suitable after a defined search criteria. The analysis provided in this paper has a different objective as we focused on efficiency and practical ability of the proposed approach in the selected papers. The various key attributes from these two are defined. Each paper is evaluated based on the various key parameters viz. metrics definition, implementation technique, validation, usability, data source, comparative analysis, practicability, and extendibility. The paper critically examines various quality aspects and their metrics for component‐based systems. In some papers, authors have also compared the results with other techniques. For characteristics like complexity and dependency, most of the proposed metrics are analytical. Soft computing and evolutionary approaches are either not being used or much less explored so far for these aspects, which may be the future concern for the researchers. In addition, hybrid approaches like neuro‐fuzzy, neuro‐genetic, etc., may also be examined for evaluation of these aspects. However, to conclude that one particular technique is better than others may not be appropriate. It may be true for one characteristic by considering different set of inputs and dataset but may not be true for the same with different inputs. The intension in the proposed work is to give a score for each metric proposed by the researchers based on the selected parameters, but certainly not to criticize any research contribution by authors. Copyright © 2012 John Wiley & Sons, Ltd.