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

2nd International Conference on Mathematics and Computers in Science and Engineering (MACISE)

作者： Jirina, Marcel Inst Comp Sci AS CR Dept Machine Learning Prague Czech Republic

ISBN: (纸本)9781728166957

Sorting with real number keys has time complexity n log n. This holds under the assumption that for all n samples a comparison sort is used. Here we propose to use the counting sort with just n cells for initial placement of samples. We resolve cases of groups of several samples placed into one cell by a comparison sort. Surprisingly, even this part has time complexity proportional to n. Numerical experiments confirm this finding and shows influence of the computing environment such as paging, and reflects a higher speed than the quicksort.

关键词： sorting algorithm sorting reals linear time complexity countingsort

来源：评论

学校读者我要写书评

暂无评论

linear, polynomial or exponential? complexity inference in polynomial time

Linear, polynomial or exponential? Complexity inference in p...

引用

4th Conference on Computability in Europe (CiE 2008)

作者： Ben-Amram, Amir M. Jones, Neil D. Kristiansen, Lars Tel Aviv Acad Coll Sch Comp Sci Tel Aviv Israel Univ Copenhagen DIKU DK-1168 Copenhagen Denmark Univ Oslo Dept Math N-0316 Oslo Norway

ISBN: (纸本)9783540694052

We present a new method for inferring complexity properties for imperative programs with bounded loops. The properties handled are: polynomial (or linear) boundedness of computed values, as a function of the input;and similarly for the running time. It is well known that complexity properties are undecidable for a Turing-complete programming language. Much work in program analysis overcomes this obstacle by relaxing the correctness notion: one does not ask for an algorithm that correctly decides whether the property of interest holds or not, but only for "yes" answers to be sound. In contrast, we reshaped the problem by defining a "core" programming language that is Turing-incomplete, but strong enough to model real programs of interest. For this language, our method is the first to give a certain answer;in other words, our inference is both sound and complete. The essence of the method is that every command is assigned a "complexity certificate", which is a concise specification of dependencies of output values on input. These certificates are produced by inference rules that are compositional and efficiently computable. The approach is inspired by previous work by Niggl and Wunderlich and by Jones and Kristiansen, but use a novel, more expressive kind of certificates.

关键词： implicit computational complexity polynomial time complexity linear time complexity static program analysis

来源：评论

学校读者我要写书评

暂无评论

Rare category exploration via wavelet analysis: Theory and applications

引用

EXPERT SYSTEMS WITH APPLICATIONS 2016年第0期63卷 173-186页

作者： Liu, Zhenguang Chiew, Kevin Zhang, Luming Zhang, Beibei He, Qinming Zimmermann, Roger Natl Univ Singapore Sch Comp Singapore 117417 Singapore Handal Indah Sdn Bhd Singapore 728789 Singapore Hefei Univ Technol Dept Comp & Informat Hefei 230009 Anhui Peoples R China Natl Univ Singapore Res Inst Suzhou 215123 Peoples R China Zhejiang Univ Coll Comp Sci Hangzhou 310027 Zhejiang Peoples R China

Rare category exploration (in short as RCE) aims to discover all the remaining data examples of a rare category from a known data example of the rare category. A few approaches have been proposed to address this problem. Most of them, however, are on quadratic or even cubic time complexities w.r.t data set size n. More importantly, the F-scores (harmonic mean of precision and recall) of the existing approaches are not satisfactory. Compared with the existing solutions to RCE, this paper proposes a novel approach with a linear time complexity and achieves a higher F-score of mining results. The key steps of our approach are to reduce search space by performing wavelet analysis on the data density function, and then refine the coarse mining result in the reduced search space via fine-grained metrics. A solid theoretical analysis is conducted to prove the feasibility of our solution, and extensive experiments on real data sets further verify its effectiveness and efficiency. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Rare category exploration Wavelet transform linear time complexity Bandwidth selection

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for the trust region subproblem based on hidden convexity

引用

OPTIMIZATION LETTERS 2017年第8期11卷 1639-1646页

作者： Wang, Jiulin Xia, Yong Beihang Univ State Key Lab Software Dev Environm LMIB Minist EducSch Math & Syst Sci Beijing 100191 Peoples R China

We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov's accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem.

关键词： Trust region subproblem Hidden convexity Proximal gradient algorithm linear time complexity

来源：评论

学校读者我要写书评

暂无评论

Singe Image Dehazing With Unsharp Masking and Color Gamut Expansion

引用

IEEE ACCESS 2022年 10卷 102462-102474页

作者： Ngo, Dat Lee, Gi-Dong Kang, Bongsoon Tech Support & Dev Ctr Display Device Convergence Busan 49315 South Korea Dong A Univ Dept Elect Engn Busan 49315 South Korea

Image dehazing is a fundamental problem in computer vision and has hitherto engendered prodigious amounts of studies. Recently, with the well-recognized success of deep learning techniques, this field has been dominated by deep dehazing models. However, deep learning is not always a panacea, especially for the practicalities of image dehazing, because high computational complexity, expensive maintenance costs, and high carbon emission are three noticeable problems. Computational efficiency is, therefore, a decisive factor in real-world circumstances. To cope with this growing demand, we propose a linear time algorithm tailored to three primitive parts: unsharp masking (pre-processing), dehazing, and color gamut expansion (post-processing). The first enhances the sharpness according to the local variance of image intensities. The second removes haze based on the improved color attenuation prior, and the third addresses a residual effect of color gamut reduction. Extensive experimental results demonstrated that the proposed method performed comparatively with popular benchmarks, notably deep dehazing models. With such a comparative performance, the proposed method is still fast and efficient, favoring real-world computer vision systems.

关键词： Image color analysis Deep learning Scattering Atmospheric modeling Degradation Cameras Image dehazing unsharp masking color gamut expansion linear time complexity

来源：评论

学校读者我要写书评

暂无评论

The generalized trust region subproblem: solution complexity and convex hull results

引用

MATHEMATICAL PROGRAMMING 2022年第2期191卷 445-486页

作者： Wang, Alex L. Kilinc-Karzan, Fatma Carnegie Mellon Univ Pittsburgh PA 15213 USA

We consider the generalized trust region subproblem (GTRS) ofminimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. Alifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this nonconvex set in terms of the generalized eigenvalues of an associated matrix pencil. This result may be of interest in building relaxations for nonconvex quadratic programs. Moreover, this result allows us to reformulate the GTRS as the minimization of two convex quadratic functions in the original space. Our next set of contributions is algorithmic: we present an algorithm for solving the GTRS up to an epsilon additive error based on this reformulation. We carefully handle numerical issues that arise from inexact generalized eigenvalue and eigenvector computations and establish explicit running time guarantees for these algorithms. Notably, our algorithms run in linear (in the size of the input) time. Furthermore, our algorithm for computing an epsilon-optimal solution has a slightly-improved running time dependence on epsilon over the state-of-the-art algorithm. Our analysis shows that the dominant cost in solving the GTRS lies in solving a generalized eigenvalue problem-establishing a natural connection between these problems. Finally, generalizations of our convex hull results allow us to apply our algorithms and their theoretical guarantees directly to equality-, interval-, and hollow-constrained variants of the GTRS. This gives the first linear-time algorithm in the literature for these variants of the GTRS.

关键词： Generalized trust region subproblem Convex hull linear time complexity

来源：评论

学校读者我要写书评

暂无评论

Recursive voids for identifying a nonconvex boundary of a set of points in the plane

引用

PATTERN RECOGNITION 2013年第12期46卷 3288-3299页

作者： Seref, Onur Zobel, Christopher W. Virginia Polytech Inst & State Univ Dept Business Informat Technol Blacksburg VA 24061 USA

We introduce a method that identifies the boundary of a nonconvex shape of a set of points in the plane. The boundary of the shape is explored through finding empty regions recursively within a shell that encapsulates all of the points. Our algorithm is output sensitive and runs in linear O(ln) time determined by the output parameter l, which is proportional to the length of the nonconvex boundary measured by a threshold unit distance. The recursive nature of our algorithm allows a tree structure that characterizes the empty regions, and by complementarity, the nonconvex shape itself. We use a distance measure based on lowest common ancestor of a pair of nodes in this tree and define the complexity of a shape as the average of the distances between all pairs. We present computational results on data size, threshold, shape complexity and noise on a set of different nonconvex shapes. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Nonconvex boundary linear time complexity Output sensitivity Computational geometry Lowest common ancestor

来源：评论

学校读者我要写书评

暂无评论

linear time algorithms on mirror trees

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第5期44卷 3495-3519页

作者： Quilliot, Alain Rebaine, Djamal Univ Clermont Auvergne Labex IMOBS3 LIMOS UMR CNRS 6158 Clermont Ferrand France Univ Quebec Chicoutimi Dept Informat & Math Chicoutimi PQ Canada

We address in this paper two problems on mirror graphs. The first is the recognition problem. While it is graph isomorphism complete, we show the analogous problem of recognizing mirror trees is solvable in linear time. The second problem we are tackling in this study is the linear ordering problem on mirror trees with respect to Directed Sum-Cut cost criterion for which a linear time algorithm is exhibited.

关键词： Mirror graphs Mirror trees Directed sum-cut linear ordering linear time complexity

来源：评论

学校读者我要写书评

暂无评论

Convex hulls of superincreasing knapsacks and lexicographic orderings

引用

DISCRETE APPLIED MATHEMATICS 2016年 201卷 150-163页

作者： Gupte, Akshay Clemson Univ Dept Math Sci Clemson SC 29631 USA

We consider bounded integer knapsacks where the weights and variable upper bounds together form a superincreasing sequence. The elements of this superincreasing knapsack are exactly those vectors that are lexicographically smaller than the greedy solution to optimizing over this knapsack. We describe the convex hull of this n-dimensional set with O(n) facets. We also establish a distributive property by proving that the convex hull of <=- and >=-type superincreasing knapsacks can be obtained by intersecting the convex hulls of <=- and >=-sets taken individually. Our proofs generalize existing results for the 0\1 case. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Superincreasing sequence Lexicographic ordering Greedy solution knapsack Convex hull linear time complexity

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for trust region problems

引用

MATHEMATICAL PROGRAMMING 2016年第1-2期158卷 363-381页

作者： Hazan, Elad Koren, Tomer Technion Israel Inst Technol IL-32000 Haifa Israel

We consider the fundamental problem of minimizing a general quadratic function over an ellipsoidal domain, also known as the trust region (sub)problem. We give the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving this problem. Specifically, our algorithm returns an -approximate solution in runtime of order N/, where N is the number of non-zero entries in the input. This matches the runtime of Nesterov's accelerated gradient descent, suitable for the special case in which the quadratic objective is convex, and the runtime of the Lanczos method which is applicable when the problem is purely quadratic.

关键词： Trust region subproblem Trust region methods Semidefinite programming linear time complexity Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：