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

On MATLAB experience in accelerating DIRECT-GLce algorithm for constrained global optimization through dynamic data structures and parallelization

引用

APPLIED MATHEMATICS AND COMPUTATION 2021年 390卷 125596-125596页

作者： Stripinis, Linas Zilinskas, Julius Casado, Leocadio G. Paulavicius, Remigijus Vilnius Univ Inst Data Sci & Digital Technol Akad 4 LT-08663 Vilnius Lithuania Univ Almeria CeiA3 Informat Dept Almeria Spain

In this paper, two different acceleration techniques for a deterministic DIRECT (DIviding RECTangles)-type global optimization algorithm, DIRECT-GLce, are considered. We adopt dynamic data structures for better memory usage in MATLAB implementation. We also study shared and distributed parallel implementations of the original DIRECT-GLce algorithm, and a distributed parallel version for the aggressive counterpart. The efficiency of DIRECT-type parallel versions is evaluated solving box- and generally constrained global optimizations problems with varying complexity, including a practical NASA speed reducer design problem. Numerical results show a good efficiency, especially for the distributed parallel version of the original DIRECT-GLce on a multi-core PC. (C) 2020 Elsevier Inc. All rights reserved.

关键词： DIRECT-type algorithm Derivative-free optimization dynamic data structures Parallel optimization Parallel MATLAB Parallel computing toolbox

来源：评论

学校读者我要写书评

暂无评论

dynamic Geometric data structures via Shallow Cuttings

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2020年第4期64卷 1235-1252页

作者： Chan, Timothy M. Univ Illinois Dept Comp Sci Urbana IL 61801 USA

We present new results on a number of fundamental problems about dynamic geometric data structures: (1) We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1-center of a 2D point set, (v) the number of maximal (i.e., skyline) points in a 3D point set. The update times are near n(11/12) for (i) and (ii), n(5/6) for (iii) and (iv), and n(2/3) for (v). Previously, sublinear bounds were known only for restricted "semi-online" settings (Chan in SIAM J. Comput.32(3), 700-716 (2003)). (2) We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is O(log(2)n), and the amortized update time is O(log(4)n) instead of O(log(5)n)(Chan in J. ACM57(3), # 16 (2010);Kaplan et al. in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495-2504. SIAM, Philadelphia (2017)). (3) We also improve previous fully dynamic data structures for maintaining the bichromatic closest pair between two 2D point sets and the diameter of a 2D point set. The amortized update time is O(log(4)n) instead of O(log(7)n) (Eppstein in Discrete Comput. Geom.13(1), 111-122 (1995);Chan in J. ACM57(3), # 16 (2010);Kaplan et al. in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495-2504. SIAM, Philadelphia (2017)).

关键词： dynamic data structures Convex hulls Nearest neighbor search Closest pair Shallow cuttings

来源：评论

学校读者我要写书评

暂无评论

DETERMINISTIC FULLY dynamic data structures FOR VERTEX COVER AND MATCHING

引用

SIAM JOURNAL ON COMPUTING 2018年第3期47卷 859-887页

作者： Bhattacharya, Sayan Henzinger, Monika Italiano, Giuseppe F. Univ Vienna Fac Comp Sci Vienna Austria Univ Warwick Coventry W Midlands England Univ Roma Tor Vergata Rome Italy

We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph G = (V, E), with vertical bar V vertical bar = n and vertical bar E vertical bar = m, in o(root m) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+epsilon) approximation in O(log n/epsilon(2)) amortized time per update. For maximum matching, we show how to maintain a (3+epsilon) approximation in O(min(root n/epsilon m(1/3)/epsilon(2)) amortized time per update and a (4 + epsilon) approximation in O(m1/3/epsilon(2)) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457-464].

关键词： fully dynamic algorithms minimum vertex conver maximum matching dynamic data structures primal-dual method

来源：评论

学校读者我要写书评

暂无评论

dynamic data structures for approximate Hausdorff distance in the word RAM

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2017年 60卷 37-44页

作者： Chan, Timothy M. Skrepetos, Dimitrios Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

We give a fully dynamic data structure for maintaining an approximation of the Hausdorff distance between two point sets in a constant dimension d, a standard problem in computational geometry. Our solution has an approximation factor of 1+epsilon for any constant epsilon > 0 and expected update time O (logU/loglogn), where U is the universe size, and n is the number of the points. The result of the paper greatly improves over the previous exact method, which required O (n(5/6)polylogn) time and worked only in a semi-online setting. The model of computation is the word RAM model. (C) 2016 Elsevier B.V. All rights reserved.

关键词： dynamic data structures Hausdorff distance Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic data structures for approximate Hausdorff distance in the word RAM 27

Dynamic data structures for approximate Hausdorff distance i...

引用

27th Canadian Conference on Computational Geometry

作者： Chan, Timothy M. Skrepetos, Dimitrios Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

关键词： dynamic data structures Hausdorff distance Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Compressed dynamic Range Majority and Minority data structures

引用

ALGORITHMICA 2020年第7期82卷 2063-2086页

作者： Gagie, Travis He, Meng Navarro, Gonzalo CeBiB Ctr Biotechnol & Bioengn Santiago Chile Dalhousie Univ Fac Comp Sci Halifax NS Canada Millennium Inst Foundat Res Data Santiago Chile Univ Chile Dept Comp Sci Santiago Chile

In the range alpha-majority query problem, we are given a sequence S[1 horizontal ellipsis n] and a fixed threshold alpha is an element of(0,1), and are asked to preprocess S such that, given a query range [i horizontal ellipsis j], we can efficiently report the symbols that occur more than alpha(j-i+1) times in S[i horizontal ellipsis j], which are called the range alpha-majorities. In this article we describe the first compressed dynamic data structure for range alpha-majority queries. It represents S in compressed space-nHk+o(nlg sigma) bits for any k=o(lg sigma n), where sigma is the alphabet size and Hk <= H0 <= lg sigma is the kth order empirical entropy of S-and answers queries in amortized time. We then show how to modify our data structure to receive some beta >=alpha at query time and report the range beta-majorities in time, without increasing the asymptotic space or update-time bounds. The best previous dynamic solution has the same query and update times as ours, but it occupies O(n) words and cannot take advantage of being given a larger threshold beta at query time. We also design the first dynamic data structure for range alpha-minority-i.e., find a non-alpha-majority that occurs in a range-and obtain space and time bounds similar to those for alpha-majorities. We extend the structure to find Theta(1/alpha)-minorities at the same space and time cost. By giving up updates, we obtain static data structures with query time O((1/alpha)lglgw sigma) for both problems, on a RAM with word size w=omega(lgn) bits, without increasing our space bound. Static alternatives reach time O(1/alpha), but they compress S only to zeroth order entropy (H0) or they only handle small values of alpha, that is, lg(1/alpha)=o(lg sigma).

关键词： Range majority and minority dynamic data structures Compact data structures

来源：评论

学校读者我要写书评

暂无评论

How fast can we play Tetris greedily with rectangular pieces?

引用

THEORETICAL COMPUTER SCIENCE 2024年 992卷

作者： Dallant, Justin Iacono, John Univ Libre Bruxelles Gosselies Belgium

Consider a variant of Tetris played on a board of width �� and infinite height, where the pieces are axis -aligned rectangles of arbitrary integer dimensions, the pieces can only be moved before letting them drop, and a row does not disappear once it is full. Suppose we want to follow a greedy strategy: let each rectangle fall where it will end up the lowest given the current state of the board. To do so, we want a data structure which can always suggest a greedy move. In other words, we want a data structure which maintains a set of ��(��) rectangles, supports queries which return where to drop the rectangle, and updates which insert a rectangle dropped at a certain position and return the height of the highest point in the updated set of rectangles. We show via a reduction from the Multiphase problem [Patra,scu, 2010] that on a board of width �� = 0(��), if the OMv conjecture [Henzinger et al., 2015] is true, then both operations cannot be supported in time ��(��1/2-��) simultaneously. The reduction also implies polynomial bounds from the 3 -SUM conjecture and the APSP conjecture. On the other hand, we show that there is a data structure supporting both operations in ��(��1/2 log3/2 ��) time on boards of width ��(1) , matching the lower bound up to an �� (1) factor.

关键词： Tetris Fine-grained complexity dynamic data structures Axis-aligned rectangles

来源：评论

学校读者我要写书评

暂无评论

data structures for Computing Unique Palindromes in Static and Non-Static Strings

引用

ALGORITHMICA 2024年第3期86卷 852-873页

作者： Mieno, Takuya Funakoshi, Mitsuru Univ Electrocommun Dept Comp & Network Engn 1-5-1 Chofugaoka Chofu 1828585 Japan Kyushu Univ Dept Informat 744 Motooka Nishi Ku Fukuoka 8190395 Japan Japan Soc Promot Sci 5-3-1 KojimachiChiyoda Ku Tokyo 1020083 Japan

A palindromic substring T [i.. j] of a string T is said to be a shortest unique palindromic substring (SUPS) in T for an interval [ p, q] if T [i.. j] is a shortest palindromic substring such that T [i.. j] occurs only once in T, and [i, j] contains [p, q]. The SUPS problem is, given a string T of length n, to construct a data structure that can compute all the SUPSs for any given query interval. It is known that any SUPS query can be answered in O(alpha) time after O(n)-time preprocessing, where a is the number of SUPSs to output (Inoue in J Discrete Algorithms 52-53:122-132, 2018). In this paper, we first show that a is at most 4, and the upper bound is tight. We also show that the total sum of lengths of minimal unique palindromic substrings of string T, which is strongly related to SUPSs, is O(n). Then, we present the first O(n)-bits data structures that can answer any SUPS query in constant time. Also, we present an algorithm to solve the SUPS problem for a sliding window that can answer any query in O(log logW) time and update data structures in amortized O(log s + log logW) time, where W is the size of the window, and s is the alphabet size. Furthermore, we consider the SUPS problem in the after-edit model and present an efficient algorithm. Namely, we present an algorithm that uses O(n) time for preprocessing and answers any k SUPS queries in O(log n log log n + k log log n) time after single character substitution. Finally, as a by-product, we propose a fully-dynamic data structure for range minimum queries (RmQs) with a constraint where the width of each query range is limited to poly-logarithmic. The constrained RmQ data structure can answer such a query in constant time and support a single-element edit operation in amortized constant time.

关键词： String algorithms Palindromes Shortest unique palindromic substrings Range minimum queries dynamic data structures Compact data structures

来源：评论

学校读者我要写书评

暂无评论

Identifying dynamic data structures by Learning Evolving Patterns in Memory

Identifying Dynamic Data Structures by Learning Evolving Pat...

引用

19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS) Held as Part of the European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： White, David H. Luettgen, Gerald Univ Bamberg Software Technol Grp Bamberg Germany

ISBN: (纸本)9783642367427;9783642367410

We investigate whether dynamic data structures in pointer programs can be identified by analysing program executions only. This paper describes a first step towards solving this problem by applying machine learning and pattern recognition techniques to analyse executions of C programs. By searching for repeating temporal patterns in memory caused by multiple invocations of data-structure operations, we are able to first locate and then identify these operations. Applying a prototypic tool implementing our approach to pointer programs that employ, e.g., lists, queues and stacks, we show that the identified operations can accurately determine the data structures used.

关键词： Program comprehension pointer programs dynamic data structures machine learning pattern recognition

来源：评论

学校读者我要写书评

暂无评论

SSRD: Shapes and Summaries for Race Detection in Concurrent data structures 23

SSRD: Shapes and Summaries for Race Detection in Concurrent ...

引用

23rd ACM SIGPLAN International Symposium on Memory Management (ISMM)

作者： Sun, Xiaofan Gupta, Rajiv Univ Calif Riverside Riverside CA 92521 USA

ISBN: (纸本)9798400706158

Concolic testing combines concrete execution with symbolic execution to automatically generate test inputs that exercise different program paths and deliver high code coverage. This approach has been extended to multithreaded programs for exposing data races. Multithreaded programs frequently rely upon concurrent dynamic data structures whose implementations may contain data races that manifest only when certain dynamic data structure shapes, program paths, and thread interleavings are exercised. The lack of support for exploring different data structure shapes compromises the detection of races. This paper presents a summarization-guided approach for concolic testing capable of efficiently exploring different dynamic data structure shapes to expose data races. Via unit testing of key functions, function summaries are generated that capture data structure shapes that cause various function paths to be exercised. The shapes are captured in the form of pointer-pointee relations among symbolic pointers. By reusing function summaries during concolic testing, much of the overhead of handling symbolic pointers and dynamic objects in summarized functions is avoided. The summary also contains symbolic memory accesses and synchronization events that guide application-level concolic testing first to identify and then confirm potential data races. We demonstrate the efficiency and efficacy of our approach via experiments with multithreaded programs performing concurrent operations on four widely used dynamic data structures - Skip List, Unrolled Linked List, Priority Queue, and AVL Tree. It increases the number of races detected from 34 to 74 in total in comparison to Cloud9, and reduces both constraints solving time and number of constraints needed to be solved via summarization.

关键词： concolic testing dynamic data structures summarization data race detection

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：