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

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

来源：评论

学校读者我要写书评

暂无评论

Move-optimal arbitrary pattern formation by mobile robots on rectangular grid using near-optimal spatial area

引用

THEORETICAL COMPUTER SCIENCE 2025年 1038卷

作者： Sharma, Avisek Ghosh, Satakshi Goswami, Pritam Sau, Buddhadeb Jadavpur Univ Dept Math Kolkata 700032 West Bengal India Int Inst Informat Technol IIIT Bhubaneswar Dept Basic Sci & Humanities Bhubaneswar 751003 Odisha India Sister Nivedita Univ Dept Comp Sci & Engn Kolkata 700156 West Bengal India

Arbitrary pattern formation (APF) is a well-studied problem in swarm robotics. To the best of our knowledge, the problem has been considered in two different settings: one in a euclidean plane and another in an infinite grid. This work deals with the problem in an infinite rectangular grid setting. The previous works in literature dealing with the APF problem in an infinite grid had a fundamental issue. These deterministic algorithms use a lot of spatial area in the grid to solve the problem, mainly to maintain the asymmetry of the configuration and avoid any collision. These solution techniques cannot be useful if there is a spatial constraint in the application field. In this work, we consider luminous robots (each robot equipped with a light that can take three colors) to avoid symmetry, but we carefully designed a deterministic algorithm that solves the APF problem using the minimal required spatial area in the grid if the initial pattern is asymmetric. The robots are autonomous, identical, and anonymous, and they operate in Look-Compute-Move cycles under a fully-asynchronous scheduler. The APF algorithm proposed in [1] by Bose et al. can be modified using luminous robots so that it uses minimal spatial area, but that algorithm is not move-optimal. The algorithm proposed in this paper not only uses minimal spatial area but is also asymptotically move-optimal.

关键词： Distributed algorithms Arbitrary pattern formation Rectangular grid Robot with lights optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

optimal AND SUBLOGARITHMIC TIME RANDOMIZED PARALLEL SORTING algorithms

引用

SIAM JOURNAL ON COMPUTING 1989年第3期18卷 594-607页

作者： RAJASEKARAN, S REIF, JH Harvard Univ MA United States

This paper assumes a parallel RAM (random access machine) model which allows both concurrent reads and concurrent writes of a global memory.

关键词： 68Q25 randomized algorithms parallel sorting parallel random access machines random permutations radix sort prefix sum optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

optimal PARALLEL INITIALIZATION algorithms FOR A CLASS OF PRIORITY-QUEUES

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1991年第4期2卷 423-429页

作者： OLARIU, S WEN, ZF ZHONGSHAN UNIV DEPT COMP SCIZHONGSHANPEOPLES R CHINA

We present an adaptive parallel algorithm for inducing a priority queue structure upon an n-element array. We also extend the technique of our algorithm to provide optimal parallel construction algorithms for three other heap-like structures useful in implementing double-ended priority queues, namely min-max heaps, deaps, and min-max-pair heaps. As it turns out, an n-element array can be made into a heap, a deap, a min-max heap, or a min-max-pair heap in O(logn + (n/p)) time using p(1 less-than-or-equal-to p less-than-or-equal-to inverted left perpendicular n/logn inverted right perpendicular) processors in the EREW-PRAM model.

关键词： DEAPS DISTRIBUTED SIMULATION DOUBLE-ENDED PRIORITY QUEUES EREW-PRAM FAULT-TOLERANCE HEAPS MIN-MAX HEAPS MIN-MAX-PAIR HEAPS optimal algorithms PARALLEL algorithms PRIORITY QUEUES

来源：评论

学校读者我要写书评

暂无评论

optimal sublogarithmic time parallel algorithms on rooted forests

引用

ALGORITHMICA 2000年第2期27卷 187-197页

作者： Sajith, G Saxena, S Indian Inst Technol Kanpur 208016 Uttar Pradesh India

The problem of finding a sublogarithmic time optimal parallel algorithm for 3-colouring rooted forests has been open for long. We settle this problem by obtaining an O ((log log n) log*(log* n)) time optimal parallel algorithm on a TOLERANT Concurrent Read Concurrent Write (CRCW) Parallel Random Access Machine (PRAM). Furthermore, we show that if f(n) is the running time of the best known algorithm for 3-colouring a rooted forest on a COMMON or TOLERANT CRCW PRAM, a fractional independent set of the rooted forest can be found in O(f(n)) time with the same number of processors, on the same model. Using these results, it is shown that decomposable top-down algebraic computation a,nd, hence, depth computation (ranking), 2-colouring and prefix summation on rooted forests can be done in O (log n) optimal time on a TOLERANT CRCW PRAM. These algorithms have been obtained by proving a result of independent interest, one concerning the self-simulation property of TOLERANT: an N-processor TOLERANT CRCW PRAM that uses an address space of size O (N) only, can be simulated on an n-processor TOLERANT PRAM in O (N/n) time, with no asymptotic increase in space or cost, when n = O (N/log log N).

关键词： parallel algorithms optimal algorithms CRCW model maximal independent set tree colouring

来源：评论

学校读者我要写书评

暂无评论

optimal CONVEX-HULL algorithms ON ENHANCED MESHES

引用

BIT 1993年第3期33卷 396-410页

作者： OLARIU, S SCHWING, JL ZHANG, J OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set of n points in the plane in O(log n) time on a mesh with multiple broadcasting of size n x n. The second algorithm shows that the same problem can be solved in O(1) time on a reconfigurable mesh of size n x n. Both algorithms achieve time lower bounds for their respective model of computation.

关键词： SORTING MESHES WITH MULTIPLE BROADCASTING RECONFIGURABLE MESHES CONVEX HULLS optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Finding optimal Chudnovsky-Chudnovsky Multiplication algorithms 5

引用

5th International Workshop on the Arithmetic of Finite Fields (WAIFI)

作者： Rambaud, Matthieu Telecom ParisTech F-75013 Paris France

ISBN: (纸本)9783319162768;9783319162775

The Chudnovsky-Chudnovsky method provides today's best known upper bounds on the bilinear complexity of multiplication in large extension of finite fields. It is grounded on interpolation on algebraic curves: we give a theoretical lower threshold for the smallest bounds that one can expect from this method (with exceptions). This threshold appears often reachable: we moreover provide an explicit method for this purpose. We also provide new bounds for the multiplication in small-dimensional algebras over F-2. Building on these ingredients, we: explain how far elliptic curves can provide upper bounds for the multiplication over F-2;using these curves, improve the bounds for the multiplication in the NIST-size extensions of F-2;thus, turning to curves of higher genus, further improve these bounds with the well known family of classical modular curves. Although illustrated only over F-2, the techniques introduced apply to all characteristics.

关键词： Elliptic modular curves Finite field arithmetic Chudnovsky-Chudnovsky interpolation Tensor rank optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

optimal Worst-Case Tuning of Smoothing algorithms

引用

IFAC Proceedings Volumes 1994年第8期27卷 527-532页

作者： Roberto Tempo CENS-CNR Politecnico di Torino Corso Duca degli Abruzzi 24 10129 Torino Italy

In this paper, we study robust parametric identification of uncertain systems in a deterministic setting. We assume that the problem data y and the linearly parametrized system model M(θ) are given. In the presence of apriori information and norm-bounded output noise, we design robust and optimal worst-case algorithms. In particular, we study the interplay between classical identification tools and nonstandard techniques frequently used in approximation theory. Indeed, we combine the robustness of smoothing algorithms (often called constrained least squares) with the optimality of interpolatory algorithms. We demonstrate that the optimal tuning of these algorithms can be easily performed via a singular value decomposition of the matrix M .

关键词： System Parameter Identification Worst-Case Tuning optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

optimal EXPECTED-TIME algorithms FOR CLOSEST POINT PROBLEMS

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 1980年第4期6卷 563-580页

作者： BENTLEY, JL WEIDE, BW YAO, AC OHIO STATE UNIV DEPT COMP & INFORMAT SCI COLUMBUS OH 43210 USA STANFORD UNIV DEPT COMP SCI STANFORD CA 94305 USA

Geometric closest potnt problems deal with the proxLmity relationships in k-dimensional point sets. Examples of closest point problems include building minimum spanning trees, nearest neighbor searching, and triangulation constructmn Shamos and Hoey [17] have shown how the Voronoi dtagram can be used to solve a number of planar closest point problems in optimal worst case tune. In this paper we extend thmr work by giving optimal *** algorithms for solving a number of closest point problems in k-space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimum spanning trees. In addition to establishing theoretical bounds, the algorithms in this paper can be implemented to solve practical problems very efficiently. © 1980, ACM. All rights reserved.

关键词： closest point problems computational geometry minunum spanning trees nearest neighbor searching optimal algorithms probabfllstm analysis of algo Voronoi diagrams

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：