Search

Martin-Löf defined algorithmic randomness, the use of martingales in this definition and several variants were explored by Schnorr, and Lutz introduced resource-bounded randomness. Ambos-Spies et al. have studied resource-bounded randomness under time-bounds and have shown that resource-bounded randomness implies resource-bounded genericity. While the genericity of Ambos-Spies is based on time-bound on finite-extension strategy, the genericity of Dowd, the main topic of this paper, is based on an analogy of the forcing theorem. For a positive integer r , an oracle D is r -generic in the sense of Dowd ( r -Dowd) if the following holds: If a certain formula F on an exponential-sized portion of D is a tautology then a polynomial-sized subfunction of D forces F to be a tautology. Here, r is the number of occurrences of query symbols in F . The relationship between resource-bounded randomness and Dowd-type genericity has been not clear so far. We show that there exists a primitive recursive function t ( n ) with the following property: Every t ( n ) -random set is r -Dowd for each positive integer r . A proof is done by means of constructing resource-bounded martingales. In our former paper, we left an open problem whether there exists a primitive recursive set which is r -Dowd for every positive integer r . In our recent work, we give an affirmative answer to the problem. The main theorem of the present paper gives an alternative proof of the affirmative answer. [ABSTRACT FROM AUTHOR]

Many problems on graphs can be expressed in the following language: given a graph G = ( V , E ) and a terminal set T ⊆ V , find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) passing through the vertices in T . We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the O ⁎ ( 2 n ) barrier for the classic Node Multiway Cut , Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising. [Copyright &y& Elsevier]

Abstract: Sequential selection has been solved in linear time by Blum et al. [M.B. Blum, R.W. Floyd, V.R. Pratt, R.L. Rivest, R.E. Tarjan, Time bounds for selection, J. Comput. System Sci. 7 (4) (1972) 448–461]. Running this algorithm on a problem of size N with , the size of the main-memory, results in an algorithm that reads and writes elements, while the number of comparisons is also bounded by . This is asymptotically optimal, but the constants are so large that in practice sorting is faster for most values of M and N. This paper provides the first detailed study of the external selection problem. A randomized algorithm of a conventional type is close to optimal in all respects. Our deterministic algorithm is more or less the same, but first the algorithm builds an index structure of all the elements. This effort is not wasted: the index structure allows the retrieval of elements so that we do not need a second scan through all the data. This index structure can also be used for repeated selections, and can be extended over time. For a problem of size N, the deterministic algorithm reads elements and writes only elements and is thereby optimal to within lower-order terms. [Copyright &y& Elsevier]