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

DO LINEAR-PROBLEMS HAVE LINEAR optimal-algorithms

SIAM REVIEW 1988年第3期30卷 388-403页

作者： PACKEL, EW Lake Forest Coll IL United States

A selective introduction to the field of information-based complexity is presented in the context of the question raised in the title. After introducing some of the basic ideas of this relatively new area that interfaces mathematics and theoretical computer science, the article surveys results on the existence of linear optimal algorithms for linear problems. Several illustrative examples are given along with an indication of the variety of disciplines in which techniques of information-based complexity are being applied.

关键词： 41 A45 41A65 65J10 46B99 68C05 optimal algorithms complexity information-based complexity linear problems

来源：评论

学校读者我要写书评

暂无评论

MAXIMUM-LIKELIHOOD ESTIMATORS AND WORST CASE optimal-algorithms FOR SYSTEM-IDENTIFICATION

引用

SYSTEMS & CONTROL LETTERS 1988年第4期10卷 265-270页

作者： TEMPO, R WASILKOWSKI, GW POLITECN TORINO CENSCNRI-10129 TORINOITALY UNIV KENTUCKY DEPT COMP SCILEXINGTONKY 40506

For system identification problems with stochastic noise, maximum likelihood estimators are frequently used. If noise is deterministic, worst case optimal algorithms should be considered. In this paper we study the fo... 详细信息

关键词： System identification Noisy information Maximum likelihood estimators optimal algorithms Worst case

来源：评论

学校读者我要写书评

暂无评论

optimal algorithms for a Pursuit-Evasion Problem in Grids: 收藏
分享
引用; SIAM Journal on Discrete Mathematics 1989年第1期2卷 126-143页; 作者： Kazuo Sugihara Ichiro Suzuki; This paper discusses a problem of searching for and capturing a fugitive by a team of searchers in an N×Ngrid<span style="display: inline-block; position: relative; width: 1.489em; he; This paper discusses a problem of searching for and capturing a fugitive by a team of searchers in an $N \times N grid G_{N}$; 来源：评论; 学校读者我要写书评

暂无评论

Efficient and optimal algorithms for Contextual Dueling Bandits under Realizability 33

Efficient and Optimal Algorithms for Contextual Dueling Band...

引用

33rd International Conference on Algorithmic Learning Theory (ALT)

作者： Saha, Aadirupa Krishnamurthy, Akshay Microsoft Res New York NY 10012 USA

We study the K-armed contextual dueling bandit problem, a sequential decision making setting in which the learner uses contextual information to make two decisions, but only observes preference-based feedback suggesting that one decision was better than the other. We focus on the regret minimization problem under realizability, where the feedback is generated by a pairwise preference matrix that is well-specified by a given function class F. We provide a new algorithm that achieves the optimal regret rate for a new notion of best response regret, which is a strictly stronger performance measure than those considered in prior works. The algorithm is also computationally efficient, running in polynomial time assuming access to an online oracle for square loss regression over F. This resolves an open problem of Dudik et al. (2015) on oracle efficient, regret-optimal algorithms for contextual dueling bandits.

关键词： Contextual Dueling Bandits Preference-based learning Realizability Function approximation Regret analysis Best-Response Policy regret Regression oracles Efficient optimal algorithms Markov games Linear realizability Agnostic

来源：评论

学校读者我要写书评

暂无评论

optimal algorithms and approximation algorithms for replica placement with distance constraints in tree networks

Optimal algorithms and approximation algorithms for replica ...

引用

IEEE International Parallel & Distributed Processing Symposium

作者： A. Benoit H. Larchevêque P. Renaud-Goud LIP Ecole Normale Supérieure de Lyon France LABRI University of Bordeaux I France

ISBN: (纸本)9781467309752

In this paper, we study the problem of replica placement in tree networks subject to server capacity and distance constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The Single policy enforces that all requests of a client are served by a single server in the tree, while in the Multiple policy, the requests of a given client can be processed by multiple servers, thus distributing the processing of requests over the platform. For the Single policy, we prove that all instances of the problem are NP-hard, and we propose approximation algorithms. The problem with the Multiple policy was known to be NP-hard with distance constraints, but we provide a polynomial time optimal algorithm to solve the problem in the particular case of binary trees when no request exceeds the server capacity.

关键词： Replica placement distance constraints optimal algorithms approximation algorithms tree networks binary tree single vs multiple policy

来源：评论

学校读者我要写书评

暂无评论

ON THE KLEINROCK-NILSSON PROBLEM OF optimal SCHEDULING algorithms FOR TIME-SHARED SYSTEMS

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1986年第1期50卷 49-60页

作者： BARRON, EN JENSEN, R UNIV KENTUCKY LEXINGTONKY 40506 AT&T BELL LABS NAPERVILLEIL 60540

We seek to minimize the mean-squared deviation of a waiting time function from a desired response function over the class of waiting time functions satisfying the Kleinrock-Nilsson necessary conditions. We will characterize analytically the optimal policy as the minimum majorant in the appropriate class of the cumulative response to go. We will show that, in general, the monotonicity necessary condition results in optimal policies which depend in some sense on the future and are anticipating.

关键词： monotone policies optimal algorithms scheduling service time time sharing

来源：评论

学校读者我要写书评

暂无评论

optimal online algorithms for multidimensional packing problems

引用

SIAM JOURNAL ON COMPUTING 2005年第2期35卷 431-448页

作者： Epstein, L Van Stee, R Univ Haifa Dept Math IL-31905 Haifa Israel Univ Karlsruhe Fak Informat D-76128 Karlsruhe Germany

We solve an open problem in the literature by providing an online algorithm for multidimensional bin packing that uses only bounded space. To achieve this, we introduce a new technique for classifying the items to be packed. We show that our algorithm is optimal among bounded space algorithms for any dimension d > 1. Its asymptotic performance ratio is (Pi(infinity))(d), where Pi(infinity) approximate to 1.691 is the asymptotic performance ratio of the one-dimensional algorithm Harmonic. A modified version of this algorithm for the case where all items are hypercubes is also shown to be optimal. Its asymptotic performance ratio is sublinear in d. Furthermore, we extend the techniques used in these algorithms to give optimal algorithms for online bounded space variable-sized packing and resource augmented packing.

关键词： multidimensional bin packing online algorithms optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Testing k-Modal Distributions: optimal algorithms via Reductions 13

Testing k-Modal Distributions: Optimal Algorithms via Reduct...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Constantinos Daskalakis Ilias Diakonikolas Rocco A. Servedio Gregory Valiant Paul Valiant MIT UC Berkeley Columbia University Microsoft Brown University

ISBN: (纸本)9781611972511

We give highly efficient algorithms, and almost matching lower bounds, for a range of basic statistical problems that involve testing and estimating the L_1 (total variation) distance between two k-modal distributions p and q over the discrete domain {1,..., n}. More precisely, we consider the following four problems: given sample access to an unknown k-modal distribution p, TESTING IDENTITY TO A KNOWN OR UNKNOWN DISTRIBUTION: 1. Determine whether p = q (for an explicitly given k- modal distribution q) versus p is ε-far from q; 2. Determine whether p = q (where q is available via sample access) versus p is ε-far from q; ESTIMATING L_1 DISTANCE ("TOLERANT TESTING") AGAINST A KNOWN OR UNKNOWN DISTRIBUTION: 3. Approximate d_(TV) (p, q) to within additive ∈ where q is an explicitly given k-modal distribution q; 4. Approximate d_(TV) (p, q) to within additive ∈ where q is available via sample access.

关键词： Testing k-Modal Distributions optimal algorithms via Reductions Optimization algorithms test problem sample complexity Unknown Access

来源：评论

学校读者我要写书评

暂无评论

optimal GEOMETRIC algorithms FOR DIGITIZED IMAGES ON FIXED-SIZE LINEAR ARRAYS AND SCAN-LINE ARRAYS

引用

DISTRIBUTED COMPUTING 1991年第2期5卷 55-65页

作者： ALNUWEIRI, HM PRASANNA, VK UNIV SO CALIF DEPT EE SYSTLOS ANGELESCA 90089

Linear arrays are characterized by a small communication bandwidth and a large communication diameter rendering them unsuited to the implementation of global computations. This paper presents efficient data movement and partitioning techniques to overcome several shortcomings of linear arrays. These techniques are used to derive optimal parallel algorithms for several geometric problems on n x n images using a fixed-size linear array with p processors, where 1 less-than-or-equal-to p less-than-or-equal-to n. O(n2/p) time solutions are presented for labeling connected image regions, computing the convex hull of each region, and computing nearest neighbors. Consequently, a linear array with n processors can solve several image problems in O(n) time which is the same time taken by a two dimensional mesh-connected computer with n2 processors. Limitations of linear arrays are analyzed by presenting a class of image problems which can be solved sequentially in O(n2) time, but require OMEGA-(n2) time on a linear array, irrespective of the number of processors used and the partitioning of the input image among the processors. An alternate communication-efficient fixed-size organization with p processors is proposed to solve such problems in O(n2/p) time, for 1 less-than-or-equal-to p less-than-or-equal-to n.

关键词： LINEAR ARRAYS IMAGE PROCESSING optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

optimal PARALLEL algorithms FOR PROBLEMS MODELED BY A FAMILY OF INTERVALS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1992年第3期3卷 364-374页

作者： OLARIU, S SCHWING, JL ZHANG, JY Department of Computer Science Old Dominion University Norfolk VA USA

A family of intervals on the real line provides a natural model for a vast number of scheduling and VLSI problems. Recently, a number of parallel algorithms to solve a variety of practical problems on such a family of intervals have been proposed in the literature. We develop computational tools and show how they can be used for the purpose of devising cost-optimal parallel algorithms for a number of interval-related problems including finding a largest subset of pairwise nonoverlapping intervals, a minimum dominating subset of intervals, along with algorithms to compute the shortest path between a pair of intervals and, based on the shortest path, a parallel algorithm to find the center of the family of intervals. More precisely, with an arbitrary family of n intervals as input, all our algorithms run in O(log n) time using O(n) processors in the EREW-PRAM model of computation.

关键词： EREW-PRAM EULER-TOUR TECHNIQUE FACILITY-LOCATION INTERVALS LIST RANKING optimal algorithms PARALLEL algorithms SCHEDULING VLSI

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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