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

Where does smoothness count the most for Fredholm equations of the second kind with noisy information?

JOURNAL OF COMPLEXITY 2003年第6期19卷 758-798页

作者： Werschulz, AG Columbia Univ Dept Comp Sci New York NY 10027 USA Fordham Univ Dept Comp & Informat Sci New York NY 10023 USA

We study the complexity of Fredholm problems (I - T-k)u =f of the second kind on I-d = [0,1](d), where T-k is an integral operator with kernel k. Previous work on the complexity of this problem has assumed either that we had complete information about k or that k and f had the same smoothness. In addition, most of this work has assumed that the information about k and f was exact. In this paper, we assume that k and f have different smoothness;more precisely, we assume that f is an element of W-r,W-p (I-d) with r > d/p and that k is an element of W-s,W-infinity (I-2d) with s>0. In addition, we assume that our information about k and f is contaminated by noise. We find that the nth minimal error is Theta(n(-mu) + delta), where mu = min{r/d(1)s/(2d)} and delta is a bound on the noise. We prove that a noisy modified finite element method has nearly minimal error. This algorithm can be efficiently implemented using multigrid techniques. We thus find tight bounds on the epsilon-complexity for this problem. These bounds depend on the cost c(delta) of calculating a delta-noisy information value. As an example, if the cost of a delta-noisy evaluation is proportional to delta(-t), then the epsilon-complexity is roughly (1/epsilon)(t+1/mu) (C) 2003 Elsevier Science (USA). All rights reserved.

关键词： Fredholm equation complexity optimal algorithms multigrid methods

来源：评论

学校读者我要写书评

暂无评论

Obnoxious facility location in multiple dimensional space

引用

TOP 2023年第2期31卷 331-354页

作者： Kalczynski, Pawel Suzuki, Atsuo Drezner, Zvi Calif State Univ Fullerton Coll Business & Econ Fullerton CA 92834 USA Nanzan Univ Dept Data Sci Nagoya Aichi 4668673 Japan

The obnoxious facility location problem in three dimensions is optimally solved by an exact method based on Apollonius spheres, and in three or more dimensions by a modification of the Big-Cube-Small-Cube (BCSC, Schobel and Scholz in Comput Oper Res 37:115-122, 2010) global optimization method to within a pre-specified accuracy. In our implementation, no specifically designed bounds are required. The general purpose bounds proposed in this paper do not employ derivatives of the functions. Such an approach can be used, for example, for locating multiple obnoxious facilities in two dimensional space, locating obnoxious facilities on the plane with demand points in three-dimensional space, or applying different distance norms. We concentrated mainly on three-dimensional problems which have the most practical applications. A four dimensional practical application is presented. We solved problems in a cube, part of a cube, a non-convex building, and locating a facility on the plane when demand points are in a three-dimensional space. We also solved problems in 4-6 dimensions to illustrate the effectiveness of the BCSC method.

关键词： Multi-dimensional space Obnoxious facility optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON THE 1-MAXIMAL ELEMENTS PROBLEM

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1993年第3-4期49卷 171-175页

作者： PIGLI, EM Department of Computer Science Norfolk State University Norfolk VA 23504 United States

Consider a set of S points in the plane. A point p in S is said to be k-maximal if exactly k elements in S dominate p. We propose a very simple, cost-optimal, EREW algorithm to solve the 1-maximal elements problem in ... 详细信息

关键词： PARALLEL algorithms optimal algorithms DOMINATION COMPUTATIONAL GEOMETRY MAXIMAL ELEMENTS

来源：评论

学校读者我要写书评

暂无评论

Single machine scheduling problems with deteriorating jobs

引用

APPLIED MATHEMATICS AND COMPUTATION 2005年第3期161卷 865-874页

作者： Zhao, CL Tang, HY Shenyang Normal Univ Coll Math & Syst Sci Shenyang 110034 Peoples R China

This paper considers the single machine scheduling problems with deteriorating jobs, i.e. jobs whose processing times are a decreasing linear function of their starting time. It is assumed that jobs have the different basic processing time and same decreasing rate. Based on the analysis of problems, the optimal algorithms are presented for the problems to minimize the sum of earliness penalties subject to no tardy jobs, to minimize the resource consumption with makespan constraints and to minimize the makespan with the total resource consumption constraints. (C) 2004 Elsevier Inc. All rights reserved.

关键词： scheduling single machine deteriorating jobs earliness penalties resource constraints optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Semi-matchings for bipartite graphs and load balancing

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2006年第1期59卷 53-78页

作者： Harvey, NJA Ladner, RE Lovász, L Tarnir, T MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA

We consider the problem of fairly matching the left-hand vertices of a bipartite graph to the right-hand vertices. We refer to this problem as the optimal semi-matching problem;it is a relaxation of the known bipartite matching problem. We present a way to evaluate the quality of a given semi-matching and show that, under this measure, an optimal semi-matching balances the load on the right-hand vertices with respect to any L-p-norm. In particular, when modeling a job assignment system, an optimal semi-matching achieves the minimal makespan and the minimal flow time for the system. The problem of finding optimal semi-matchings is a special case of certain scheduling problems for which known solutions exist. However, these known solutions are based on general network optimization algorithms, and are not the most efficient way to solve the optimal semi-matching problem. To compute optimal semi-matchings efficiently, we present and analyze two new algorithms. The first algorithm generalizes the Hungarian method for computing maximum bipartite matchings, while the second, more efficient algorithm is based on a new notion of cost-reducing paths. Our experimental results demonstrate that the second algorithm is vastly superior to using known network optimization algorithms to solve the optimal semi-matching problem. Furthermore, this same algorithm can also be used to find maximum bipartite matchings and is shown to be roughly as efficient as the best known algorithms for this goal. (C) 2005 Elsevier Inc. All rights reserved.

关键词： bipartite graphs load balancing matching algorithms optimal algorithms semi-matching

来源：评论

学校读者我要写书评

暂无评论

Maximizing the minimum cover probability by emergency facilities

引用

ANNALS OF OPERATIONS RESEARCH 2016年第1-2期246卷 349-362页

作者： Drezner, Zvi Marianov, Vladimir Wesolowsky, George O. Calif State Univ Fullerton Steven G Mihaylo Coll Business & Econ Fullerton CA 92834 USA Pontificia Univ Catolica Chile Dept Elect Engn Santiago Chile McMaster Univ Fac Business Hamilton ON L8S 4M4 Canada

In this paper we propose a stochastic model for the location of emergency facilities. The model is formulated and analyzed. The location of one facility in the plane is optimally solved. optimal algorithms are proposed for the location of multiple facilities on a network. Computational experiments illustrate the effectiveness of these solution procedures.

关键词： Emergency facility location Multiple facilities optimal algorithms Heuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

Consistency, optimality, and incompleteness

引用

ANNALS OF PURE AND APPLIED LOGIC 2013年第12期164卷 1224-1235页

作者： Chen, Yijia Flum, Joerg Muller, Moritz Shanghai Jiao Tong Univ Shanghai 200030 Peoples R China Univ Freiburg Freiburg Germany Univ Vienna Kurt Godel Res Ctr A-1010 Vienna Austria

Assume that the problem P-0 is not solvable in polynomial time. Let T be a first-order theory containing a sufficiently rich part of true arithmetic. We characterize T U {Con(T)} as the minimal extension of T proving for some algorithm that it decides P-0 as fast as any algorithm B with the property that T proves that B decides P-0. Here, Con(T) claims the consistency of T. As a byproduct, we obtain a version of Godel's Second Incompleteness Theorem. Moreover, we characterize problems with an optimal algorithm in terms of arithmetical theories. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Consistency optimal algorithms First-order arithmetic Godel's Second Incompleteness Theorem

来源：评论

学校读者我要写书评

暂无评论

On the complexity of stochastic integration

引用

MATHEMATICS OF COMPUTATION 2001年第234期70卷 685-698页

作者： Wasilkowski, GW Wozniakowski, H Univ Kentucky Dept Comp Sci Lexington KY 40506 USA Columbia Univ Dept Comp Sci New York NY 10027 USA Univ Warsaw Inst Appl Math & Mech PL-02097 Warsaw Poland

We study the complexity of approximating stochastic integrals with error epsilon for various classes of functions. For Ito integration, we show that the complexity is of order epsilon (-1), even for classes of very smooth functions. The lower bound is obtained by showing that Ito integration is not easier than Lebesgue integration in the average case setting with the Wiener measure. The upper bound is obtained by the Milstein algorithm, which is almost optimal in the considered classes of functions. The Milstein algorithm uses the values of the Brownian motion and the integrand. It is bilinear in these values and is very easy to implement. For Stratonovich integration, we show that the complexity depends on the smoothness of the integrand and may be much smaller than the complexity of Ito integration.

关键词： Ito integrals Stratonovich integrals optimal algorithms complexity

来源：评论

学校读者我要写书评

暂无评论

ON THE optimal SOLUTION OF LARGE LINEAR-SYSTEMS

引用

JOURNAL OF THE ACM 1984年第3期31卷 545-559页

作者： TRAUB, JF WOZNIAKOWSKI, H UNIV WARSAW PL-00325 WARSAWPOLAND

The information-based study of the optimal solution of large linear systems is initiated by studying the case of Krylov information. Among the algorithms that use Krylov information are minimal residual, conjugate gradient, Chebyshev, and successive approximation algorithms. A "sharp" lower bound on the number of matrix-vector multiplications required to compute an å-approximation is obtained for any orthogonally invariant class of matrices. Examples of such classes include many of practical interest such as symmetric matrices, symmetric positive definite matrices, and matrices with bounded condition number. It is shown that the minimal residual algorithm is within at most one matrix-vector multiplication of the lower bound. A similar result is obtained for the generalized minimal residual algorithm. The lower bound is computed for certain classes of orthogonally invariant matrices. How the lack of certam properties (symmetry, positive definiteness) increases the lower bound is shown. A conjecture and a number of open problems are stated.

关键词： conjugate gradient algorithm Krylov information lower bounds optimal algorithms orthogonal invariance

来源：评论

学校读者我要写书评

暂无评论

An improvement on parallel computation of a maximal matching

引用

INFORMATION PROCESSING LETTERS 1995年第6期56卷 343-348页

作者： Han, YJ Electronic Data Systems Inc. 37350 Ecorse Rd. Romulus MI 48174 USA

We present an improved optimal parallel algorithm with time complexity O(log(3) n) for computing a maximal matching in a graph. The improvement is made on the recent result of Kelsen which requires O(log(4) n) time fo... 详细信息

关键词： graph algorithms maximal matching optimal algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：