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

Revisiting a randomized algorithm for the minimum rainbow subgraph problem

THEORETICAL COMPUTER SCIENCE 2015年 593卷 154-159页

作者： Yuan, Chen Kan, Haibin Fudan Univ Shanghai Key Lab Intelligent Informat Proc Shanghai Peoples R China

The minimum rainbow subgraph problem arises in bioinformatics. The graph is given as an edge-colored undirected graph. Our goal is to find a subgraph with minimum number of vertices such that there is exactly one edge from each color class. The currently best approximation ratio achieved by a deterministic approximation algorithm is O(Delta). (Here Delta is the max degree of a graph.) In [4] he proposes a randomized algorithm which achieves an approximation ratio of O (root Delta ln Delta). However, we find that there is a flaw in his probability analysis which renders this approximation ratio invalid. We present a simple example to show why his analysis does not work. Instead, we propose an alternative analysis for his randomized algorithm. Our estimate shows that this randomized algorithm may achieve approximation ratio of O(Delta) in general. However, if the number of colors is Theta(n Delta(r)) for some positive r <= 1, his randomized algorithm can beat the bound of O(Delta). Moreover, through our analysis, we also find that if we impose an extra constraint on the color function, the bound O(root Delta ln Delta) still holds. (C) 2015 Elsevier B.V. All rights reserved.

关键词： randomized algorithm Minimum rainbow subgraph

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2015年第1期17卷 1-12页

作者： Cabello, Sergio Saumell, Maria Univ Ljubljana Dept Math IMFM Ljubljana 61000 Slovenia Univ Ljubljana FMF Ljubljana 61000 Slovenia Univ W Bohemia Dept Math Plzen Czech Republic Univ W Bohemia European Ctr Excellence NTIS Plzen Czech Republic

We present a randomized algorithm to compute a clique of maximum size in the visibility graph G of the vertices of a simple polygon P. The input of the problem consists of the visibility graph G, a Hamiltonian cycle describing the boundary of P, and a parameter delta is an element of (0, 1) controlling the probability of error of the algorithm. The algorithm does not require the coordinates of the vertices of P. With probability at least 1 - delta the algorithm runs in O (vertical bar E(G)vertical bar(2)/omega(G) log(1/delta)) time and returns a maximum clique, where omega(G) is the number of vertices in a maximum clique in G. A deterministic variant of the algorithm takes O (vertical bar E(G)vertical bar(2)) time and always outputs a maximum size clique. This compares well to the best previous algorithm by Ghosh et al. (2007) for the problem, which is deterministic and runs in O(vertical bar V(G)vertical bar(2) vertical bar E(G)vertical bar) time.

关键词： visibility graph maximum clique simple polygon randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for two-cluster partition of a set of vectors

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2015年第2期55卷 330-339页

作者： Kel'manov, A. V. Khandeev, V. I. Russian Acad Sci Sobolev Inst Math Siberian Branch Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

A randomized algorithm is substantiated for the strongly NP-hard problem of partitioning a finite set of vectors of Euclidean space into two clusters of given sizes according to the minimum-of-the sum-of-squared-distances criterion. It is assumed that the centroid of one of the clusters is to be optimized and is determined as the mean value over all vectors in this cluster. The centroid of the other cluster is fixed at the origin. For an established parameter value, the algorithm finds an approximate solution of the problem in time that is linear in the space dimension and the input size of the problem for given values of the relative error and failure probability. The conditions are established under which the algorithm is asymptotically exact and runs in time that is linear in the space dimension and quadratic in the input size of the problem.

关键词： partition set of vectors squared Euclidean distances NP-hardness randomized algorithm asymptotic accuracy

来源：评论

学校读者我要写书评

暂无评论

PORA: Proportion-Oriented randomized algorithm for Test Case Prioritization

PORA: Proportion-Oriented Randomized Algorithm for Test Case...

引用

IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C)

作者： Jiang, Bo Chan, W. K. Tse, T. H. Beihang Univ Sch Comp Sci & Engn Beijing Peoples R China City Univ Hong Kong Dept Comp Sci Tat Chee Ave Hong Kong Hong Kong Peoples R China Univ Hong Kong Dept Comp Sci Pokfulam Hong Kong Peoples R China

ISBN: (纸本)9781467379892

Effective testing is essential for assuring software quality. While regression testing is time-consuming, the fault detection capability may be compromised if some test cases are discarded. Test case prioritization is a viable solution. To the best of our knowledge, the most effective test case prioritization approach is still the additional greedy algorithm, and existing search-based algorithms have been shown to be visually less effective than the former algorithms in previous empirical studies. This paper proposes a novel Proportion-Oriented randomized algorithm (PORA) for test case prioritization. PORA guides test case prioritization by optimizing the distance between the prioritized test suite and a hierarchy of distributions of test input data. Our experiment shows that PORA test case prioritization techniques are as effective as, if not more effective than, the total greedy, additional greedy, and ART techniques, which use code coverage information. Moreover, the experiment shows that PORA techniques are more stable in effectiveness than the others.

关键词： Test case prioritization randomized algorithm proportional sampling strategy multi-objective optimization

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for Multilinear UTV Decomposition

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2025年第1期32卷

作者： Liu, Guimin Zhao, Ruijuan Zheng, Bing Yang, Fanyin Lanzhou Univ Sch Math & Stat Lanzhou Peoples R China Lanzhou Univ Finance & Econ Sch Informat Engn & Artificial Intelligence Lanzhou Peoples R China

Truncated multilinear UTV decomposition (TMLUTVD) is an efficient method to extract the most dominant features of a given tensor in various practical applications, such as tensor tracking. However, the computation of TMLUTVD can be time-consuming, especially for large-scale data. randomized methods are known for their ability to reduce computational costs, particularly when dealing with the low-rank approximation of large tensors. Therefore, in this paper, we develop randomized algorithms for computing the multilinear UTV decomposition. Specifically, we propose randomized versions of TMLUTVD using randomized sampling schemes and the power method technique, which is an extension of the existing randomized matrix method. They are more efficient when applied to very large datasets compared with deterministic methods, and a detailed probabilistic error analysis of these algorithms is provided. We further introduce two novel variants of these randomized algorithms, based on distinct computational challenges inherent in processing large-scale datasets. The first variant can adaptively find a low-rank representation that satisfies a given tolerance when the target rank is not known in advance. The second variant preserves the original tensor structure and is particularly effective for managing large-scale sparse tensors that are challenging to load into memory. Some numerical results are presented to illustrate the efficiency and effectiveness of the proposed methods.

关键词： low multilinear rank approximation multilinear UTV decomposition randomized algorithm tensors

来源：评论

学校读者我要写书评

暂无评论

Fault Detection for Non-Gaussian Stochastic Distribution Systems Based on randomized algorithms

引用

IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT 2022年 71卷 1页

作者： Zhao, Zhen Liu, Peter Xiaoping Gao, Jinfeng Zhejiang Sci Tech Univ Sch Mech Engn & Automat Hangzhou 310018 Peoples R China Carleton Univ Dept Syst & Comp Engn Ottawa ON K1S 5B6 Canada

This article presents a new fault detection scheme for stochastic distribution systems with non-Gaussian variables based on a probabilistic framework. The available information is the output probability density function (pdf) rather than the measured outputs themselves. The square-root B-spline function is utilized to formulate the output pdfs. Probabilistic parameter models are developed to characterize system uncertainties and faults. An observer is designed to detect the multiplicative and additive faults. The randomized algorithm is adopted to design the threshold to achieve an optimal balance between the false alarm rate (FAR) and the fault detection rate (FDR). The effectiveness of the proposed method is demonstrated and compared against existing work by utilizing a continuous stirred tank reactor system.

关键词： Uncertainty Probabilistic logic Fault detection Stochastic processes Probability density function Robustness Mathematical models Fault detection non-Gaussian stochastic system probabilistic robustness randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for Computation of Tucker Decomposition and Higher Order SVD (HOSVD)

引用

IEEE ACCESS 2021年 9卷 28684-28706页

作者： Ahmadi-Asl, Salman Abukhovich, Stanislav Asante-Mensah, Maame G. Cichocki, Andrzej Phan, Anh Huy Tanaka, Tohishisa Oseledets, Ivan Skolkovo Inst Sci & Technol SKOLTECH CDISE Moscow 121205 Russia Tokyo Univ Agr & Technol Inst Global Innovat & Res Tokyo 1848588 Japan

Big data analysis has become a crucial part of new emerging technologies such as the internet of things, cyber-physical analysis, deep learning, anomaly detection, etc. Among many other techniques, dimensionality reduction plays a key role in such analyses and facilitates feature selection and feature extraction. randomized algorithms are efficient tools for handling big data tensors. They accelerate decomposing large-scale data tensors by reducing the computational complexity of deterministic algorithms and the communication among different levels of memory hierarchy, which is the main bottleneck in modern computing environments and architectures. In this article, we review recent advances in randomization for computation of Tucker decomposition and Higher Order SVD (HOSVD). We discuss random projection and sampling approaches, single-pass and multi-pass randomized algorithms and how to utilize them in the computation of the Tucker decomposition and the HOSVD. Simulations on synthetic and real datasets are provided to compare the performance of some of best and most promising algorithms.

关键词： Tensors Matrix decomposition Signal processing algorithms Approximation algorithms Memory management Licenses Probability distribution randomized algorithm tensor decomposition random projection sampling unfolding Tucker decomposition HOSVD

来源：评论

学校读者我要写书评

暂无评论

Online randomized interpolative decomposition with a posteriori error estimator for temporal PDE data reduction

引用

COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING 2025年 434卷

作者： Li, Angran Becker, Stephen Doostan, Alireza Univ Colorado Boulder Smead Aerosp Engn Sci Boulder CO 80309 USA Univ Colorado Boulder Appl Math Boulder CO 80309 USA

Traditional low-rank approximation is a powerful tool for compressing large data matrices that arise in simulations of partial differential equations (PDEs), but suffers from high computational cost and requires several passes over the PDE data. The compressed data may also lack interpretability thus making it difficult to identify feature patterns from the original data. To address these issues, we present an online randomized algorithm to compute the interpolative decomposition (ID) of large-scale data matrices in situ. Compared to previous randomized IDs that used the QR decomposition to determine the column basis, we adopt a streaming ridge leverage score-based column subset selection algorithm that dynamically selects proper basis columns from the data and thus avoids an extra pass over the data to compute the coefficient matrix of the ID. In particular, we adopt a single-pass error estimator based on the non- adaptive Hutch++ algorithm to provide real-time error approximation for determining the best coefficients. As a result, our approach only needs a single pass over the original data and thus is suitable for large and high-dimensional matrices stored outside of core memory or generated in PDE simulations. A strategy to improve the accuracy of the reconstructed data gradient, when desired, within the ID framework is also presented. We provide numerical experiments on turbulent channel flow and ignition simulations, and on the NSTX Gas Puff Image dataset, comparing our algorithm with the offline ID algorithm to demonstrate its utility in real-world applications.

关键词： Low-rank approximation Single-pass algorithm Interpolative decomposition Column subset selection randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Column-randomized Linear Programs: Performance Guarantees and Applications

引用

OPERATIONS RESEARCH 2025年第3期73卷 iii-viii, 1151-1722, C2-C3页

作者： Akchen, Yi-Chun Misic, Velibor V. UCL Sch Management London E14 5AB England Univ Calif Los Angeles UCLA Anderson Sch Management Los Angeles CA 90095 USA

We propose a randomized method for solving linear programs with a large number of columns but a relatively small number of constraints. Because enumerating all the columns is usually unrealistic, such linear programs are commonly solved by column generation, which is often still computationally challenging because of the intractability of the subproblem in many applications. Instead of iteratively introducing one column at a time as in column generation, our proposed method involves sampling a collection of columns according to a user-specified randomization scheme and solving the linear program consisting of the sampled columns. Although similar methods for solving large-scale linear programs by sampling columns (or, equivalently, sampling constraints in the dual) have been proposed in the literature, in this paper we derive an upper bound on the optimality gap that holds with high probability. This bound converges to the optimality gap of a linear program related to the sampling distribution at a rate inversely proportional to the square root of the number of sampled columns. We analyze the gap of this latter linear program, which we dub the distributional counterpart, and derive conditions under which this gap will be small. Finally, we numerically demonstrate the effectiveness of the proposed method in the cutting-stock problem and in nonparametric choice model estimation.

关键词： linear programming column generation constraint sampling randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized quaternion tensor UTV decompositions for color image and color video processing

引用

PATTERN RECOGNITION 2025年 165卷

作者： Yang, Liqiao Miao, Jifei Jiang, Tai-Xiang Zhang, Yanlin Kou, Kit Ian Southwestern Univ Finance & Econ Res Inst Digital Econ & Interdisciplinary Sci Sch Comp & Artificial Intelligence Chengdu 611130 Peoples R China Univ Macau Fac Sci & Technol Dept Math Macau 999078 Peoples R China

In this paper, we propose novel quaternion matrix UTV (QUTV) and quaternion tensor UTV (QTUTV) decomposition methods, specifically designed for color image and video processing. We begin by defining both QUTV and QTUTV decompositions and provide detailed algorithmic descriptions. To enhance computational efficiency, we introduce randomized versions of these decompositions using random sampling from the quaternion normal distribution, which results in cost-effective and interpretable solutions. Extensive numerical experiments demonstrate that the proposed algorithms significantly improve computational efficiency while maintaining relative errors comparable to existing decomposition methods. These results underscore the strong potential of quaternion-based decompositions for real-world color image and video processing applications. Theoretical findings further support the robustness of the proposed methods, providing a solid foundation for their widespread use in practice.

关键词： Quaternion UTV randomized algorithm Quaternion tensor Color image processing Low-rank approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：