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

A Novel Fiber Intrusion Signal Recognition Method for OFPS Based on SCN With Dropout

JOURNAL OF LIGHTWAVE TECHNOLOGY 2019年第20期37卷 5221-5230页

作者： Li, Wei Zeng, Zhiqiang Qu, Hongquan Sun, Chengbin North China Univ Technol Sch Informat Sci & Technol Beijing 100144 Peoples R China

Accurate and fast recognition of fiber intrusion signals has always been a fundamental task in the Optical Fiber Pre-warning System (OFPS). However, currently existing recognition models tend to focus on one aspect and lack a comprehensive approach. In this paper, a dropout-based Stochastic Configuration Network (SCN) optical fiber intrusion signal recognition model is first proposed, which is named DropoutSCN. By combining dropout with randomized algorithm models, it not only enhances the fast learning ability, but also improves the generalization performance of the recognition model. In the experiment, compared with traditional Artificial Neural Network (ANN), Random Vector Functional Link (RVFL), and original SCN models, the DropoutSCN model proposed in this paper has the lowest rootmean-square error (RMSE). In terms of time efficiency, it reduces the time delay by about 2.5 times compared with the traditional ANN. In addition, this paper applies dropout to SCN, which provides a feasible thinking and reference for the study of randomized algorithm models.

关键词： Dropout optical fiber pre-warning system randomized algorithm signal recognition stochastic configuration network

来源：评论

学校读者我要写书评

暂无评论

Pass-efficient truncated UTV for low-rank approximations

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2024年第1期43卷 1-18页

作者： Ji, Ying Feng, Yuehua Dong, Yongxin Shanghai Univ Engn Sci Sch Math Phys & Stat Shanghai 201620 Peoples R China East China Univ Polit Sci & Law Sch Law & Criminal Justice Shanghai 201620 Peoples R China

We propose the pass-efficient truncated UTV algorithm, a faster variant of the TUXV algorithm for low-rank approximations. Compared with the TUXV algorithm, data transfer and the complexity of the proposed algorithm are reduced. Therefore, our algorithm is suitable for large matrices stored out of memory or generated by streaming data. We also develop residual error upper bounds and singular value approximation error bounds for the pass-efficient truncated UTV algorithm. Numerical experiments are reported to demonstrate the efficiency and effectiveness of our algorithm.

关键词： SVD randomized algorithm Low-rank approximation UTV factorization Pass-efficient

来源：评论

学校读者我要写书评

暂无评论

A Property Tester for Tree-Likeness of Quartet Topologies

引用

THEORY OF COMPUTING SYSTEMS 2011年第3期49卷 576-587页

作者： Chang, Maw-Shang Lin, Chuang-Chieh Rossmanith, Peter Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan Rhein Westfal TH Aachen Dept Comp Sci D-52056 Aachen Germany

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property P and a parameter 0 0, and present the first property tester ... 详细信息

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property P and a parameter 0 < epsilon < 1, by examining function values of f over o(vertical bar D vertical bar) elements in D, determine whether f satisfies P or differs from any one which satisfies P in at least epsilon vertical bar D vertical bar elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f(Q), which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that fQ satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f(Q). In this paper, we prove the existence of a set of quartet topologies of error number at least c((n)(4)) for some constant c > 0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n(3)/epsilon) queries, and is of one-sided error and non-adaptive.

关键词： randomized algorithm Property testing Evolutionary tree Quartet method

来源：评论

学校读者我要写书评

暂无评论

ON THE POWER OF CHOICE FOR BOOLEAN FUNCTIONS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第3期36卷 1943-1954页

作者： Fraiman, Nicolas Lichev, Lyuben Mitsche, Dieter Univ N Carolina Chapel Hill NC 27599 USA Univ Lyon 1 Inst Camille Jordan Lyon France Univ Jean Monnet St Etienne France

In this paper we consider a variant of the well-known Achlioptas process for graphs adapted to monotone Boolean functions. Fix a number of choices r is an element of N and a sequence of increasing functions (f(n))(n >= 1) such that, for every n >= 1, f(n) : {0, 1}(n) (sic) {0, 1}. Given n bits which are all initially equal to 0, at each step r 0-bits are sampled uniformly at random and are proposed to an agent. Then, the agent selects one of the proposed bits and turns it from 0 to 1 with the goal to reach f(n)(-1) (1) as quickly as possible. We nearly characterize the conditions on (f(n))(n >= 1) under which an acceleration by a factor of r(1+ o(1)) is possible and underline the wide applicability of our results by giving examples from the fields of Boolean functions and graph theory.

关键词： Boolean function power of choice threshold hitting probability relevant variable Achlioptas process randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Memory optimal dispersion by anonymous mobile robots

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期340卷 171-182页

作者： Das, Archak Bose, Kaustav Sau, Buddhadeb Jadavpur Univ Dept Math 188 Raja SC Mallick Rd Kolkata 700032 W Bengal India Indian Stat Inst Adv Comp & Microelect Unit 203 B T Rd Kolkata 700108 W Bengal India

Consider a team of kappa <= n autonomous mobile robots initially placed at a node of an arbitrary graph G with n nodes. The dispersion problem asks for a distributed algorithm that allows the robots to reach a configuration in which each robot is at a distinct node of the graph. If the robots are anonymous, i.e., they do not have any unique identifiers, then the problem is not solvable by any deterministic algorithm. However, the problem can be solved even by anonymous robots if each robot is given access to a fair coin which they can use to generate random bits. In this setting, it is known that the robots require O(log.) bits of memory to achieve dispersion, where. is the maximum degree of G. On the other hand, the best known memory upper bound is min{Delta,max{log Delta, log D}} (D = diameter of G), which can be omega(log Delta), depending on the values of Delta and D. In this paper, we close this gap by presenting an optimal algorithm requiring O(log Delta) bits of memory. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Mobile robots Dispersion Depth first search Distributed algorithms randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

UTV decomposition of dual matrices and its applications

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2024年第1期43卷 1-18页

作者： Xu, Renjie Wei, Tong Wei, Yimin Yan, Hong Fudan Univ Sch Math Sci Shanghai 200433 Peoples R China Fudan Univ Inst Sci & Technol Brain Inspired Intelligence Shanghai 200433 Peoples R China Fudan Univ Sch Math Sci Shanghai Key Lab Contemporary Appl Math Shanghai 200433 Peoples R China City Univ Hong Kong Ctr Intelligent Multidimens Data Anal Dept Elect Engn Hong Kong Peoples R China

Matrix factorization in the context of dual numbers has found applications, in recent years, in fields such as kinematics and computer graphics. In this paper, we develop an efficient approach for handling large-scale data low-rank approximation problems using the UTV decomposition of dual matrices (DUTV). Theoretically, we propose an explicit expression for the DUTV and provide necessary and sufficient conditions for its existence. During this process, we also discovered that the general low-rank model for dual matrices can be solved by the Sylvester equation. In numerical experiments, the DUTV algorithm outperforms the dual matrix SVD algorithm in terms of speed and maintains effective performance in wave recognition. Subsequently, we utilize the DUTV algorithm to validate brain functional circuits in large-scale task-state functional magnetic resonance imaging data. Successfully identifying three types of wave signals, the DUTV method provides substantial empirical evidence for cognitive neuroscience theories.

关键词： Dual matrices UTV decomposition Low-rank approximation randomized algorithm Traveling wave identification Brain dynamics

来源：评论

学校读者我要写书评

暂无评论

Sequential function approximation with noisy data

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2018年 371卷 363-381页

作者： Shin, Yeonjong Wu, Kailiang Xiu, Dongbin Ohio State Univ Dept Math 231 W 18th Ave Columbus OH 43210 USA

We present a sequential method for approximating an unknown function sequentially using random noisy samples. Unlike the traditional function approximation methods, the current method constructs the approximation using one sample at a time. This results in a simple numerical implementation using only vector operations and avoids the need to store the entire data set. The method is thus particularly suitable when data set is exceedingly large. Furthermore, we present a general theoretical framework to define and interpret the method. Both upper and lower bounds of the method are established for the expectation of the results. Numerical examples are provided to verify the theoretical findings. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Approximation theory randomized algorithm Noisy data

来源：评论

学校读者我要写书评

暂无评论

A new approach to the minimum cut problem

引用

JOURNAL OF THE ACM 1996年第4期43卷 601-640页

作者： Karger, DR Stein, C DARTMOUTH COLL HANOVER NH 03755 USA

This paper presents a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in O(n(2)log(3)n) time, a significant improvement over the previous (O) over tilde(mn) time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in RNC with n(2) processors;this gives the first proof that the minimum cut problem can be solved in RNC. The algorithm does more than find a single minimum cut;it finds all of them. With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of cu of the minimum cut's in expected (O) over tilde(n(2 alpha)) time, or in RNC with n(2 alpha) processors. The problem of finding a minimum multiway cut of a graph into r pieces is solved in expected (O) over tilde(n(2(r-1))) time, or in RNC with n(2(r-1)) processors. The ''trace'' of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representation for minimum cuts.

关键词： graph algorithm minimum cut network reliability parallel computing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Tight approximations for resource constrained scheduling and bin packing

引用

DISCRETE APPLIED MATHEMATICS 1997年第1-3期79卷 223-245页

作者： Srivastav, A Stangier, P UNIV COLOGNE ZENTRUM PARALLELES RECHNEND-50931 COLOGNEGERMANY

We consider the following resource constrained scheduling problem. We are given m identical processors, s resources R-1, ..., R-s with upper bounds b(1), ..., b(s), n independent jobs T-1, ..., T-n of unit length, where each job T-j has a start time r(j) is an element of N, requires one processor and an amount R-i(j) is an element of {0, 1} of resource R-i, i = 1, ..., s. The optimization problem is to schedule the jobs at discrete times in N subject to the processor, resource and start-time constraints so that the latest scheduling time is minimum. Multidimensional bin packing is a special case of this problem. Resource constrained scheduling can be relaxed in a natural way when one allows the scheduling of fraction of jobs. Let C-opt (resp. C) be the minimum schedule size for the integral (resp. fractional scheduling). While the computation of C-opt is a NP-hard problem, C can be computed by linear programming in polynomial time. In case of zero start times Rock and Schmidt (1983) showed for the integral problem a polynomial-time approximation within (m/2)C-opt and de la Vega and Lueker (1981), improving a classical result of Garey et al. (1976), gave for every is an element of > 0 a linear time algorithm with an asymptotic approximation guarantee of (s + epsilon)C-opt. The main contributions of this paper include the first polynomial-time algorithm approximating C-opt for every epsilon is an element of(0, 1) within a factor of 1 + epsilon for instances with b(i) = Omega(epsilon(-2)log(Cs)) for all i and m = Omega(epsilon(-2) logC), and a proof that the achieved approximation under the given conditions is best possible, unless P = NP. Furthermore, in some cases we give for every fixed alpha > 1 a parallel 2 alpha-factor approximation algorithm.

关键词： resource constrained scheduling multidimensional bin packing randomized algorithm derandomization approximation algorithm chromatic index

来源：评论

学校读者我要写书评

暂无评论

A primal-dual online algorithm for the κ-server problem on weighted HSTs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第4期34卷 1133-1146页

作者： Chen, Wenbin Li, Fufang Wang, Jianxiong Qi, Ke Tang, Maobin Wang, Xiuni Guangzhou Univ Dept Comp Sci Guangzhou Guangdong Peoples R China Guangzhou Univ Guangdong Prov Engn Technol Res Ctr Math Educ Sof Guangzhou Guangdong Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China

In this paper, we show that there is a 5/2 l .ln(1+ kappa)-competitive randomized algorithm for the kappa-sever problem on weighted Hierarchically Separated Trees (HSTs) with depth l when n = kappa + 1 where n is the number of points in the metric space, which improved previous best competitive ratio 12l ln(1 + 4l (1 + k)) by Bansal et al. (FOCS, pp 267-276, 2011).

关键词： kappa-server problem Online algorithm Primal-dual method randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：