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

Computationally efficient approximations of the joint spectral radius

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2005年第1期27卷 256-272页

作者： Blondel, VD Nesterov, Y Catholic Univ Louvain Div Appl Math B-1348 Louvain Belgium Catholic Univ Louvain CORE B-1348 Louvain Belgium

The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate that can be obtained by forming long products of matrices taken from the set. This quantity appears in a number of application contexts but is notoriously difficult to compute and to approximate. We introduce in this paper a procedure for approximating the joint spectral radius of a finite set of matrices with arbitrary high accuracy. Our approximation procedure is polynomial in the size of the matrices once the number of matrices and the desired accuracy are fixed. For the special case of matrices with nonnegative entries we give elementary proofs of simple inequalities that we then use to obtain approximations of arbitrary high accuracy. From these inequalities it follows that the spectral radius of matrices with nonnegative entries is given by the simple expression. rho( A(1),..., A(m)) = lim k ->infinity rho(1/k)( A(1)(circle times k) + ... + A(m)(circle times k)), where it is somewhat surprising to notice that the right-hand side does not directly involve any mixed product between the matrices. ( A(circle times)k denotes the kth Kronecker power of A.) For matrices with arbitrary entries ( not necessarily nonnegative), we introduce an approximation procedure based on semidefinite liftings that can be implemented in a recursive way. For two matrices, even the first step of the procedure gives an approximation whose relative accuracy is at least 1/root 2, that is, more than 70%. The subsequent steps improve the accuracy but also increase the dimension of the auxiliary problems from which the approximation can be found. Our approximation procedures provide approximations of relative accuracy 1- epsilon in time polynomial in n((ln m)/epsilon), where m is the number of matrices and n is their size. These bounds are close from optimality since we show that, unless P= NP, no approximation algorithm is possible that provides a relative accuracy of 1 - epsilon and runs in ti

关键词： joint spectral radius generalized spectral radius approximation algorithm switched systems linear inclusion Lyapunov indicator Kronecker power

来源：评论

学校读者我要写书评

暂无评论

A multiexchange local search algorithm for the capacitated facility location problem

引用

MATHEMATICS OF OPERATIONS RESEARCH 2005年第2期30卷 389-403页

作者： Zhang, JW Chen, B Ye, YY NYU Stern Sch Business IOMS Operat Management New York NY 10012 USA Univ Warwick Warwick Business Sch Coventry W Midlands England Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We present a multiexchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between 3 + 2 root 2- epsilon and 3 + 2 root 2- + epsilon for any given constant epsilon > 0. The previously known best approximation ratio for the CFLP is 7.88, as shown by Mahdian and Pal (2003. Universal facility location. Proc. 11th Annual Eur. Sympos. algorithms (ESA), 409-421), based on the operations proposed by Pal et al. (2001. Facility location with hard capacities. Proc. 42nd IEEE Sympos. Foundations Comput. Sci. (FOCS), 329-338). Our upper bound 3+2 root 2-+epsilon also matches the best-known ratio, obtained by Chudak and Williamson (1999. Improved approximation algorithm for capacitated facility location problems. Proc. 7th Conf Integer Programming Combin. Optim. (IPCO), 99-113), for the CFLP with uniform capacities. In order to obtain the tight bound of our new algorithm, we make interesting use of the notion of exchange graph of Pal et al. and techniques from the area of parallel machine scheduling.

关键词： capacitated facility location approximation algorithm local search algorithm

来源：评论

学校读者我要写书评

暂无评论

An analysis of the LPT algorithm for the max-min and the min-ratio partition problems

引用

THEORETICAL COMPUTER SCIENCE 2005年第3期349卷 407-419页

作者： Wu, BY Shu Te Univ Dept Comp Sci & Informat Engn Kaohsiung 824 Taiwan

Given a set of positive numbers, the max-min partition problem asks for a k-partition such that the minimum part is maximized. The min-ratio partition problem has the similar definition but the objective is to minimize the ratio of the maximum to the minimum parts. In this paper, we analyze the performances of the longest processing time (LPT) algorithm for the two problems. We show that the tight bounds of the LPT are, respectively (4k - 2)/(3k - 1) and (7)/(5) (c) 2005 Elsevier B.V. All rights reserved.

关键词： partition optimization problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for minimum-cost vertex-connectivity problems (vol 18, pg 21, 1997)

引用

algorithmICA 2002年第1期34卷 98-107页

作者： Ravi, R Williamson, DP Carnegie Mellon Univ GSIA Pittsburgh PA 15213 USA IBM Corp Almaden Res Ctr San Jose CA 95120 USA

There is an error in our paper "An approximation algorithm fur Minimum-Cost Vertex-Connectivity Problems" (algorithmica (1997), 18:21-43). In that paper we considered the following problem: given an undirected graph and values r(ij) for each pair of vertices i and j, find a minimum-cost set of edged, such that there are r(ij) vertex-disjoint paths between vertices i and j. We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal-dual approach which has led to approximation El algorithms for many edge-connectivity problems, The algorithms work in a series of stages;in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case r(ij) = k for all i, j, we described a polynomial-time algorithm that claimed to output a solution of cost no more than 27-l(k) times optimal, where H(n) 1 + 1/2 + ... + 1/n. This result is erroneous. We describe an example where our primal-dual augmentation subroutine, when augmenting a k-vertex connected graph to a (k + 1)-vertex connected graph, gives solutions that are a factor n (k) away from the minimum, In the case r(ij) is an element of {0, 1, 2} for all i, j, we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k-vertex connected case does hold, and that the algorithm performs as claimed.

关键词： approximation algorithm vertex connectivity survivable network design primal-dual method

来源：评论

学校读者我要写书评

暂无评论

Approximating the minmax rooted-subtree cover problem

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2005年第5期E88A卷 1335-1338页

作者： Nagamochi, H Kyoto Univ Dept Appl Math & Phys Kyoto 6068501 Japan

Let G = (V, E) be a connected graph such that each edge e is an element of E and each vertex nu is an element of V are weighted by nonnegative reals w(e) and h(nu), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X = {X-1, X-2,..., X-p} of V and a set of p subtrees T-1, T-2,..., T-p such that each T-i contains X-i boolean OR {r} so as to minimize the maximum cost of the subtrees, where the cost of Ti is defined to be the sum of the weights of edges in T-i and the weights of vertices in X-i. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X-1, X-2,..., X-p} of V and a set of p cycles C-1, C-2,..., C-P such that C-i contains X-i boolean OR {r} so as to minimize the maximum cost of the cycles, where the cost of C-i is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p + 1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p + 1))-approximation algorithm to the MRCC with a metric (G, w).

关键词： approximation algorithm graph algorithm partition subtree cover problem traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

Separating points by axis-parallel lines

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2005年第6期15卷 575-590页

作者： Calinescu, G Dumitrescu, A Karloff, H Wan, PJ IIT Chicago IL 60616 USA Univ Wisconsin Milwaukee WI 53211 USA AT&T Labs Res Florham Pk NJ 07932 USA

We study the problem of separating n points in the plane, no two of which have the same x- or y-coordinate, using a minimum number of vertical and horizontal lines avoiding the points, so that each cell of the subdivision contains at most one point. Extending previous NP-hardness results due to Freimer et al. we prove that this problem and some variants of it are APX-hard. We give a 2-approximation algorithm for this problem, and a d-approximation algorithm for the d-dimensional variant, in which the points are to be separated using axis-parallel hyperplanes. To this end, we reduce the point separation problem to the rectangle stabbing problem studied by Gaur et al. Their approximation algorithm uses LP-rounding. We present an alternative LP-rounding procedure which also works for the rectangle stabbing problem. We show that the integrality ratio of the LP is exactly 2.

关键词： point separation approximation algorithm LP-rounding integrality gap

来源：评论

学校读者我要写书评

暂无评论

An efficient convergent lattice algorithm for European Asian options

引用

APPLIED MATHEMATICS AND COMPUTATION 2005年第2期169卷 1458-1471页

作者： Dai, TS Huang, GS Lyuu, YD Chung Yuan Christian Univ Dept Appl Math Chungli 32023 Taiwan Natl Chi Nan Univ Dept Comp Sci & Informat Engn Taipei 545 Taiwan Natl Taiwan Univ Dept Finance Taipei 106 Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 106 Taiwan

Financial options whose payoff depends critically on historical prices are called path-dependent options. Their prices are usually harder to calculate than options whose prices do not depend on past histories. Asian options are popular path-dependent derivatives, and it has been a long-standing problem to price them efficiently and accurately. No known exact pricing formulas are available to price them under the continuous-time Black-Scholes model. Although approximate pricing formulas exist, they lack accuracy guarantees. Asian options can be priced numerically on the lattice. A lattice divides the time to maturity into n equal-length time steps. The option price computed by the lattice converges to the option value under the Black-Scholes model as n -> infinity. Unfortunately, only subexponential-time algorithms are available if Asian options are to be priced on the lattice without approximations. Efficient approximation algorithms are available for the lattice. The fastest lattice algorithm published in the literature runs in O(n(3.5))-time, whereas for the related PDE method, the fastest one runs in O(n(3)) time. This paper presents a new lattice algorithm that runs in O(n(2.5)) time, the best in the literature for such methods. Our algorithm exploits the method of Lagrange multipliers to minimize the approximation error. Numerical results verify its accuracy and the excellent performance. (c) 2004 Elsevier Inc. All rights reserved.

关键词： option pricing lattice path-dependent derivative Asian option approximation algorithm Lagrange multiplier

来源：评论

学校读者我要写书评

暂无评论

On the approximability of the maximum induced matching problem

引用

JOURNAL OF DISCRETE algorithmS 2005年第1期3卷 79-91页

作者： Duckworth, William Manlove, David F. Zito, Michele Macquarie Univ Dept Comp Sydney NSW 2109 Australia Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland Univ Liverpool Dept Comp Sci Liverpool L69 7ZF Merseyside England

In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d - 1 for MIM in d-regular graphs, for each d >= 3. We also prove that MIM is APX-complete in d-regular graphs, for each d >= 3. (C) 2004 Elsevier B.V. All rights reserved.

关键词： Induced matching Strong matching Regular graph approximation algorithm APX-completeness

来源：评论

学校读者我要写书评

暂无评论

The k-splittable flow problem

引用

algorithmICA 2005年第3-4期42卷 231-248页

作者： Baier, G Köhler, E Skutella, M Tech Univ Berlin Inst Math Fak Math & Nat Wissensch 2 D-10623 Berlin Germany Univ Dortmund Fachbereich Math D-44221 Dortmund Germany

In traditional multi-commodity flow theory, the task is to send a certain amount of each commodity from its start to its target node, subject to capacity constraints on the edges. However, no restriction is imposed on the number of paths used for delivering each commodity;it is thus feasible to spread the flow over a large number of different paths. Motivated by routing problems arising in real-life applications, e.g., telecommunication, unsplittable flows have moved into the focus of research. Here, the demand of each commodity may not be split but has to be sent along a single path. In this paper a generalization of this problem is studied. In the considered flow model, a commodity can be split into a bounded number of chunks which can then be routed on different paths. In contrast to classical (splittable) flows and unsplittable flows, the single-commodity case of this problem is already NP-hard and even hard to approximate. We present approximation algorithms for the single- and multi-commodity case and point out strong connections to unsplittable flows. Moreover, results on the hardness of approximation are presented. In particular, we show that some of our approximation results are in fact best possible, unless P=NP.

关键词： network flow approximation algorithm max-flow min-cut unsplittable flow

来源：评论

学校读者我要写书评

暂无评论

A 2-approximation algorithm for the minimum weight edge dominating set problem

引用

DISCRETE APPLIED MATHEMATICS 2002年第3期118卷 199-207页

作者： Fujito, T Nagamochi, H Nagoya Univ Dept Elect Chikusa Ku Nagoya Aichi 4648603 Japan Toyohashi Univ Technol Dept Informat & Comp Sci Tempa Ku Toyohashi Aichi 4418580 Japan

We present a polynomial-time algorithm approximating the minimum weight edge dominating set problem within a factor of 2. It has been known that the problem is NP-hard but, when edge weights are uniform (so that the smaller the better), it can be efficiently approximated within a factor of 2. When general weights were allowed, however, very little had been known about its approximability, and only very recently was it shown to be approximable within a factor of 2 1/10 by reducing to the edge cover problem via LP relaxation. In this paper we extend the approach given therein, by studying more carefully polyhedral structures of the problem, and obtain an improved approximation bound as a result. While the problem considered is as hard to approximate as the weighted vertex cover problem is, the best approximation (constant) factor known for vertex cover is 2 even for the unweighted case, and has not been improved in a long time, indicating that improving our result would be quite difficult. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： edge dominating set problem approximation algorithm LP relaxation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：