检索结果-内蒙古大学图书馆

complexity Analysis of an Interior Point Algorithm for the Semidefinite Optimization Based on a Kernel Function with a Double Barrier Term

引用

Acta Mathematica Sinica,English Series 2015年第3期31卷 543-556页

作者： Mohamed ACHACHE Laboratoire de Mathématiques Fondamentales et Numériques Faculté des Sciences Université Ferhat Abbas Sétif 1Algérie

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.

关键词： Semidefinite optimization kernel functions primal-dual interior point methods large andsmall-update algorithms complexity of algorithms

来源：评论

学校读者我要写书评

暂无评论

complexity analysis and numerical implementation of a full-Newton step interior-point algorithm for LCCO

引用

NUMERICAL algorithms 2015年第2期70卷 393-405页

作者： Achache, Mohamed Goutali, Moufida Univ Ferhat Abbas Setif1 Lab Math Fondamentales & Numer Setif Algeria Univ Ferhat Abbas Setif1 Fac Sci Dept Math Setif Algeria

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.

关键词： Linearly constrained convex optimization Interior point methods Short-step primal-dual algorithms complexity of algorithms

来源：评论

学校读者我要写书评

暂无评论

A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP

引用

AFRIKA MATEMATIKA 2015年第1-2期26卷 139-151页

作者： Achache, Mohamed Khebchache, Radia Univ Ferhat Abbas Setif1 Lab Math Fondament & Numer Setif Algeria Univ Ferhat Abbas Setif1 Fac Sci Dept Math Setif Algeria

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.

关键词： Linear complementarity problems Interior point methods Short-step primal-dual algorithms complexity of algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

引用

ANNALS OF OPERATIONS RESEARCH 2014年第1期223卷 155-171页

作者： Dourado, Mitre C. Oliveira, Rodolfo A. Protti, Fabio Univ Fed Rio de Janeiro Rio De Janeiro Brazil Univ Fed Fluminense Niteroi RJ Brazil

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.

关键词： complexity of algorithms Enumerative combinatorics Steiner convexity Steiner tree

来源：评论

学校读者我要写书评

暂无评论

LINK REVERSAL ROUTING WITH BINARY LINK LABELS: WORK complexity

引用

SIAM JOURNAL ON COMPUTING 2013年第2期42卷 634-661页

作者： Charron-Bost, Bernadette Gaillard, Antoine Welch, Jennifer L. Widder, Josef Ecole Polytech CNRS LIX F-91128 Palaiseau France Ecole Polytech LIX F-91128 Palaiseau France Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA TU Wien Formal Methods Syst Engn Grp A-1040 Vienna Austria

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.

关键词： link reversal routing wireless networks complexity of algorithms applications of game theory

来源：评论

学校读者我要写书评

暂无评论

Approximate Boyer-Moore String Matching for Small Alphabets

引用

ALGORITHMICA 2010年第3期58卷 591-609页

作者： Salmela, Leena Tarhio, Jorma Kalsi, Petri Helsinki Univ Technol Dept Comp Sci & Engn Espoo 02015 Finland

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.

关键词： Approximate string matching Edit distance Hamming distance complexity of algorithms Biological sequences

来源：评论

学校读者我要写书评

暂无评论

The monomorphism problem in free groups

引用

ARCHIV DER MATHEMATIK 2010年第5期94卷 423-434页

作者： Ciobanu, Laura Houcine, Abderezak Ould Univ Fribourg CH-1700 Fribourg Switzerland Univ Mons B-7000 Mons Belgium Univ Lyon 1 INSA Lyon F-69621 Villeurbanne France Univ Lyon 1 CNRS Ecole Cent Lyon Inst Camille JordanUMR5208 F-69622 Villeurbanne France

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.

关键词： Free groups Decision problems complexity of algorithms

来源：评论

学校读者我要写书评

暂无评论

BURST-ERROR CORRECTION FOR CYCLIC CODES

BURST-ERROR CORRECTION FOR CYCLIC CODES

引用

International IEEE Conference Devoted to the 150-Anniversary of Alexander S Popov

作者： Semerenko, Vasyl P.

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.

关键词： cyclic codes error bursts linear finite-state machines complexity of algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient sample sort and the average case analysis of PEsort

引用

THEORETICAL COMPUTER SCIENCE 2006年第1-3期369卷 44-66页

作者： Chen, Jing-Chao DongHua Univ Sch Informat Shanghai 200051 Peoples R China

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.

关键词： sorting samplesort complexity of algorithms master theorem quicksort proportion extend sort

来源：评论

学校读者我要写书评

暂无评论

complexity of a noninterior path-following method for the linear complementarity problem

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2002年第1期112卷 53-76页

作者： Burke, J Xu, S Univ Washington Dept Math Seattle WA 98195 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

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.

关键词： linear complementarity noninterior path-following methods complexity of algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：