In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization(SDO) problems. The proposed algorithm is based on a new kernel fun...
详细信息
In this paper, we establish the polynomial complexity of a primal-dual path-following interior point algorithm for solving semidefinite optimization(SDO) problems. The proposed algorithm is based on a new kernel function which differs from the existing kernel functions in which it has a double barrier term. With this function we define a new search direction and also a new proximity function for analyzing its complexity. We show that if q1 〉 q2 〉 1, the algorithm has O((q1 + 1) nq1+1/2(q1-q2)logn/ε)and O((q1 + 1)2(q1-q2)^3q1-2q2+1√n logn/c) complexity results for large- and small-update methods, respectively.
In this paper, we present a primal-dual interior point algorithm for linearly constrained convex optimization (LCCO). The algorithm uses only full-Newton step to update iterates with an appropriate proximity measure f...
详细信息
In this paper, we present a primal-dual interior point algorithm for linearly constrained convex optimization (LCCO). The algorithm uses only full-Newton step to update iterates with an appropriate proximity measure for controlling feasible iterations near the central path during the solution process. The favorable polynomial complexity bound for the algorithm with short-step method is obtained, namely O(root n log n/epsilon) which is as good as the linear and convex quadratic optimization analogue. Numerical results are reported to show the efficiency of the algorithm.
In this paper, we propose a weighted short-step primal-dual interior point algorithm for solving monotone linear complementarity problem (LCP). The algorithm uses at each interior point iteration a full-Newton step an...
详细信息
In this paper, we propose a weighted short-step primal-dual interior point algorithm for solving monotone linear complementarity problem (LCP). The algorithm uses at each interior point iteration a full-Newton step and the strategy of the central path to obtain an epsilon-approximate solution of LCP. This algorithm yields the best currently well-known theoretical complexity iteration bound, namely, O(root n log n/epsilon) which is as good as the bound for the linear optimization analogue. The implementation of the algorithm and the algorithm in Wang et al. (Fuzzy Inform Eng 54:479-487, 2009) is done followed by a comparison between these two obtained numerical results.
For a set of vertices of a connected graph , a Steiner W-tree is a connected subgraph of such that and is minimum. Vertices in are called terminals. In this work, we design an algorithm for the enumeration of all Stei...
详细信息
For a set of vertices of a connected graph , a Steiner W-tree is a connected subgraph of such that and is minimum. Vertices in are called terminals. In this work, we design an algorithm for the enumeration of all Steiner -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner -tree in polynomial time, our algorithm enumerates the remaining trees with delay (where ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966-984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given and a vertex , is in a Steiner -tree for some ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when has arbitrary size. In addition, we prove that deciding whether is in some Steiner -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.
Full Reversal and Partial Reversal are two well-known routing algorithms that were introduced by Gafni and Bertsekas [IEEE Trans. Commun., 29 (1981), pp. 11-18]. By reversing the directions of some links of the graph,...
详细信息
Full Reversal and Partial Reversal are two well-known routing algorithms that were introduced by Gafni and Bertsekas [IEEE Trans. Commun., 29 (1981), pp. 11-18]. By reversing the directions of some links of the graph, these algorithms transform a connected input DAG (directed acyclic graph) into an output DAG in which each node has at least one path to a distinguished destination node. We present a generalization of these algorithms, called the link reversal (LR) algorithm, based on a novel formalization that assigns binary labels to the links of the input DAG. We characterize the legal link labelings for which LR is guaranteed to establish routes. Moreover, we give an exact expression for the number of steps - called work complexity - taken by each node in every execution of LR from any legal input graph. Exact expressions for the per-node work complexity of Full Reversal and Partial Reversal follow from our general formula;this is the first exact expression known for Partial Reversal. Our binary link labels formalism facilitates comparison of the work complexity of certain link labelings - including those corresponding to Full Reversal and Partial Reversal - using game theory. We consider labelings in which all incoming links of a given node i are labeled with the same binary value mu(i). Finding initial labelings that induce good work complexity can be considered as a game in which to each node i a player is associated who has strategy mu(i). In this game, one tries to minimize the cost, i. e., the number of steps. Modeling the initial labelings as this game allows us to compare the work complexity of Full Reversal and Partial Reversal in a way that provides a rigorous basis for the intuition that Partial Reversal is better than Full Reversal with respect to work complexity.
Recently a new variation of approximate Boyer-Moore string matching was presented for the k-mismatch problem. The variation, called FAAST, is specifically tuned for small alphabets. We further improve this algorithm g...
详细信息
Recently a new variation of approximate Boyer-Moore string matching was presented for the k-mismatch problem. The variation, called FAAST, is specifically tuned for small alphabets. We further improve this algorithm gaining speedups in both preprocessing and searching. We also present three variations of the algorithm for the k-difference problem. We show that the searching time of the algorithms is average-optimal and the preprocessing also has a lower time complexity than FAAST. Our experiments show that our algorithm for the k-mismatch problem is about 30% faster than FAAST and the new algorithms compare well against other state-of-the-art algorithms for approximate string matching.
Let F be a free group of finite rank. We say that the monomorphism problem in F is decidable if there is an algorithm such that, for any two elements u and v in F, it determines whether there exists a monomorphism of ...
详细信息
Let F be a free group of finite rank. We say that the monomorphism problem in F is decidable if there is an algorithm such that, for any two elements u and v in F, it determines whether there exists a monomorphism of F that sends u to v. In this paper we show that the monomorphism problem is decidable and we provide an effective algorithm that solves the problem.
The methods of burst-error correction for cyclic (n, k) codes based on the mathematical theory of linear finite-state machines (LFSM) are considered. The algorihtm of sparse error burst correction of length no more th...
详细信息
ISBN:
(纸本)9781424439676
The methods of burst-error correction for cyclic (n, k) codes based on the mathematical theory of linear finite-state machines (LFSM) are considered. The algorihtm of sparse error burst correction of length no more than n - k/2, allowing to achieve k/2 times performance gain compared to with known methods is suggested. The algorihtm of full error burst correction of arbitrary length tau and complexity O(n x tau) based LFSM graphical models is suggested (tau = 1 divided by n - 1). The possibility of parallel search of the errors of various types is shown.
The purpose of the paper is twofold. First, we want to search for a more efficient sample sort. Secondly, by analyzing a variant of Samplesort, we want to settle an open problem: the average case analysis of Proportio...
详细信息
The purpose of the paper is twofold. First, we want to search for a more efficient sample sort. Secondly, by analyzing a variant of Samplesort, we want to settle an open problem: the average case analysis of Proportion Extend Sort (PEsort for short). An efficient variant of Samplesort given in the paper is called full sample sort. This algorithm is simple. It has a shorter object code and is almost as fast as PEsort. Theoretically, we show that full sample sort with a linear sampling size performs at most n log n + O(n) comparisons and O(n log n) exchanges on the average, but O(n log(2) n) comparisons in the worst case. This is an improvement on the original Samplesort by Frazer and McKellar, which requires n log n + O(n log log n) comparisons on the average and O(n(2)) comparisons in the worst case. On the other hand, we use the same analyzing approach to show that PEsort, with any p > 0, performs also at most n log n + O (n) comparisons on the average. Notice, Cole and Kandathil analyzed only the case p = 1 of PEsort. For any p > 0, they did not. Namely, their approach is suitable only for a special case such as p = 1, while our approach is suitable for the generalized case. (c) 2006 Elsevier B.V. All rights reserved.
We study the complexity of a noninterior path-following method for the linear complementarity problem. The method is based on the Chen-Harker-Kanzow-Smale smoothing function. It is assumed that the matrix M is either ...
详细信息
We study the complexity of a noninterior path-following method for the linear complementarity problem. The method is based on the Chen-Harker-Kanzow-Smale smoothing function. It is assumed that the matrix M is either a P-matrix or symmetric and positive definite. When M is a P-matrix, it is shown that the algorithm finds a solution satisfying the conditions Mx-y+q=0 and parallel tomin{x, y}parallel to(infinity)less than or equal toepsilon in at most (sic) ((2-beta)(1+(1/l(M)))(2)log((1+(1/2)beta)mu(0))/epsilon)) Newton iterations;here, beta and mu(0) depend on the initial point, l (M) depends on M, and epsilon > 0. When M is symmetric and positive definite, the complexity bound is (sic) ((2+beta)C(2)log((1+(1/2)betamu(0))/epsilon), where, C=1+(rootnroot(min{lambda(min)(M), 1/lambda(max)(M)}), and lambdamin(M), lambdamax(M) are the smallest and largest eigenvalues of M.
暂无评论