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

A one-step worst-case optimal algorithm for bi-objective univariate optimization

OPTIMIZATION LETTERS 2014年第7期8卷 1945-1960页

作者： Zilinskas, Antanas Vilnius State Univ Inst Math & Informat Akademijos St 4 LT-08663 Vilnius Lithuania

A bi-objective optimization problem with univariate non-convex objectives is considered. The objective functions are assumed Lipschitz continuous. An algorithm is developed implementing the concept of one-step worst case optimality. The possibility of extension of the proposed algorithm to the multivariate case is discussed. Some illustrative numerical examples are included where the proposed algorithm is compared with an average case optimal algorithm.

关键词： Multi-objective optimization optimal algorithms Global optimization Lipschitz optimization

来源：评论

学校读者我要写书评

暂无评论

Probabilistic optimal Estimation With Uniformly Distributed Noise

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2014年第8期59卷 2113-2127页

作者： Dabbene, Fabrizio Sznaier, Mario Tempo, Roberto Politecn Torino CNR IEIIT Turin Italy Northeastern Univ Boston MA 02115 USA

The classical approach to system identification is based on stochastic assumptions about the measurement error, and provides estimates that have random nature. Worst-case identification, on the other hand, only assumes the knowledge of deterministic error bounds, and establishes guaranteed estimates, thus being in principle better suited for the use in control design. However, a main limitation of such deterministic bounds lies in their potential conservatism, thus leading to estimates of restricted use. In this paper, we propose a rapprochement between the stochastic and worst-case system identification viewpoints, which is based on the probabilistic setting of information-based complexity. The main idea in this line of research is to "discard" sets of measure at most epsilon, where epsilon is a probabilistic accuracy, from the set of deterministic estimates. Therefore, we are decreasing the so-called worst-case radius of information at the expense of a given probabilistic "risk." In the case of uniformly distributed noise, we derive new computational results, and in particular we compute a trade-off curve, called violation function, which shows how the radius of information decreases as a function of the accuracy. To this end, we construct randomized and deterministic algorithms which provide approximations of this function. We report extensive simulations showing numerical comparisons between the stochastic, worst-case and probabilistic approaches, thus demonstrating the efficacy of the methods proposed in this paper.

关键词： Least-squares linear estimation optimal algorithms randomized algorithms system identification uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Randomized and quantum complexity of nonlinear two-point BVPs

引用

APPLIED MATHEMATICS AND COMPUTATION 2014年第0期245卷 357-371页

作者： Gocwin, Maciej AGH Univ Sci & Technol Fac Appl Math PL-30059 Krakow Poland

We deal with the complexity of nonlinear BVPs with nonlinear two-point boundary conditions. We consider the randomized and quantum models of computation. We assume that the right-hand side function is r times differentiable with all derivatives bounded by a constant. We show that the epsilon-complexity is roughly of order epsilon(-1/(r+1/2)) in the randomized setting, and epsilon(-1/(r+1)) in the quantum setting. We compare our results with known results in the deterministic setting. The speed-up of the randomized computations with respect to the deterministic computations is by 1/(r(2r + 1)) in the exponent of 1/epsilon, and the speed-up of the quantum computations by 1/(r(r +1)) in the exponent. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Boundary value problems Complexity optimal algorithms Randomized computing Quantum computing

来源：评论

学校读者我要写书评

暂无评论

A Framework for Automated Competitive Analysis of On-line Scheduling of Firm-Deadline Tasks 35

A Framework for Automated Competitive Analysis of On-line Sc...

引用

35th IEEE Real-Time Systems Symposium (RTSS)

作者： Chatterjee, Krishnendu Pavlogiannis, Andreas Koessler, Alexander Schmid, Ulrich IST Austria Inst Sci & Technol Austria Klosterneuburg Austria Vienna Univ Technol Embedded Comp Syst Grp Vienna Austria

ISBN: (纸本)9781479972876

We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm-deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D-over, that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application.

关键词： scheduling task analysis automated competitive analysis clairvoyant scheduler competitive ratio firm-deadline real-time tasks flexible framework labeled transition system limit-average constraints liveness multiobjective graphs online scheduling algorithms optimal algorithms optional safety Algorithm design and analysis Real-time systems Safety Schedules Scheduling Scheduling algorithms Vectors Scheduling algorithms elastic frame Optimization algorithms Algorithm design and analysis task analysis real-time systems Consumer safety safety IN-LINE

来源：评论

学校读者我要写书评

暂无评论

On the worst-case optimal multi-objective global optimization

引用

OPTIMIZATION LETTERS 2013年第8期7卷 1921-1928页

作者： Zilinskas, Antanas Inst Math & Informat LT-08663 Vilnius Lithuania

Multi-objective optimization problem with Lipshitz objective functions is considered. It is shown that the worst-case optimal passive algorithm can be reduced to the computation of centers of balls producing the optimal cover of a feasible region, where the balls are of equal minimum radius. It is also shown, that in the worst-case, adaptivity does not improve the guaranteed accuracy achievable by the passive algorithm.

关键词： Multi-objective optimization optimal algorithms Global optimization Lipshitz optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Probabilistic Approach to optimal Estimation - Part II: algorithms and Applications

A Probabilistic Approach to Optimal Estimation - Part II: Al...

引用

51st IEEE Annual Conference on Decision and Control (CDC)

作者： Dabbene, Fabrizio Sznaier, Mario Tempo, Roberto Politecn Torino CNR IEIIT Inst I-10129 Turin Italy Northeastern Univ Boston MA 02115 USA

ISBN: (纸本)9781467320665

In this paper, we develop randomized and deterministic algorithms for computing the probabilistic radius of information associated to an identification problem, and the corresponding optimal probabilistic estimate. To compute this estimate, in the companion paper [11] the concept of optimal violation function is introduced. Moreover, for the case of uniform distributions, it is shown how its computation is related to the solution of a (quasi) concave optimization problem, based on to the maximization of the volume of a specially constructed polytope. In this second paper, we move a step further and develop specific algorithms for addressing this problem. In particular, since the problem is NP-hard, we propose both randomized relaxations (based on a probabilistic volume oracle and stochastic optimization algorithms), and deterministic ones (based on semi-definite programming). Finally, we present a numerical example illustrating the performance of the proposed algorithms.

关键词： System identification optimal algorithms randomized algorithms uncertain systems

来源：评论

学校读者我要写书评

暂无评论

A Probabilistic Approach to optimal Estimation Part I: Problem Formulation and Methodology

A Probabilistic Approach to Optimal Estimation Part I: Probl...

引用

51st IEEE Annual Conference on Decision and Control (CDC)

作者： Dabbene, Fabrizio Sznaier, Mario Tempo, Roberto Politecn Torino CNR IEIIT Inst I-10129 Turin Italy Northeastern Univ Boston MA 02115 USA

ISBN: (纸本)9781467320665

The classical approach to system identification is based on statistical assumptions about the measurement error and provides estimates that have stochastic nature. Worst-case identification, on the other hand, only assumes the knowledge of deterministic error bounds and provides guaranteed estimates. The focal point of this paper is to provide a rapproachement between these two paradigms and propose a novel probabilistic framework for system identification. The main idea in this line of research is to "discard" sets of measure at most epsilon, where epsilon is a probabilistic accuracy, from the set of deterministic estimates. Therefore, we are decreasing the so-called worst-case radius of information at the expense of a given probabilistic "risk." The main results of the paper establish rigorous theoretical properties of a trade-off curve, called optimal violation function, which shows how the radius of information decreases as a function of the accuracy. In the companion paper [8], we develop algorithms (randomized and deterministic) which exploit these theoretical results for efficiently computing the optimal violation function.

关键词： System identification optimal algorithms uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Load-balancing spatially located computations using rectangular partitions

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2012年第10期72卷 1201-1214页

作者： Saule, Erik Bas, Erdeniz O. Catalyuerek, Uemit V. Ohio State Univ Dept Biomed Informat Columbus OH 43212 USA Ohio State Univ Dept Comp Sci & Engn Columbus OH 43212 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43212 USA

Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the load of the most loaded rectangle (processor) is minimized. Since finding the optimal arbitrary rectangle-based partition is an NP-hard problem, we investigate particular classes of solutions: rectilinear, jagged and hierarchical. We present a new class of solutions called m-way jagged partitions, propose new optimal algorithms for m-way jagged partitions and hierarchical partitions, propose new heuristic algorithms, and provide worst case performance analyses for some existing and new heuristics. Moreover, the algorithms are tested in simulation on a wide set of instances. Results show that two of the algorithms we introduce lead to a much better load balance than the state-of-the-art algorithms. We also show how to design a two-phase algorithm that reaches different time/quality tradeoffs. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Load balancing Spatial partitioning optimal algorithms Heuristics Dynamic programming Particle-in-cell Mesh-based computation Jagged partitioning Rectilinear partitioning Hierarchical partitioning

来源：评论

学校读者我要写书评

暂无评论

A space and time efficient algorithm for SimRank computation

引用

WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS 2012年第3期15卷 327-353页

作者： Yu, Weiren Zhang, Wenjie Lin, Xuemin Zhang, Qing Le, Jiajin Univ New S Wales Sch Comp Sci & Engn Sydney NSW 2052 Australia Australia CSIRO ICT Ctr E Hlth Res Ctr Herston Qld 4029 Australia Donghua Univ Sch Comp Sci & Technol Shanghai Peoples R China

SimRank has become an important similarity measure to rank web documents based on a graph model on hyperlinks. The existing approaches for conducting SimRank computation adopt an iteration paradigm. The most efficient deterministic technique yields O(n(3)) worst-case time per iteration with the space requirement O(n(2)), where n is the number of nodes (web documents). In this paper, we propose novel optimization techniques such that each iteration takes O(min {n . m . n(t)}) time and O(n + m) space, where m is the number of edges in a web-graph model and r <= log 7. In addition, we extend the similarity transition matrix to prevent random surfers getting stuck, and devise a pruning technique to eliminate impractical similarities for each iteration. Moreover, we also develop a reordering technique combined with an over-relaxation method, not only speeding up the convergence rate of the existing techniques, but achieving I/O efficiency as well. We conduct extensive experiments on both synthetic and real data sets to demonstrate the efficiency and effectiveness of our iteration techniques.

关键词： graph similarity SimRank link-based analysis optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：