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

Input-based adaptive randomized test case prioritization: A local beam search approach

JOURNAL OF SYSTEMS AND SOFTWARE 2015年 105卷 91-106页

作者： Jiang, Bo Chan, W. K. Beihang Univ Sch Comp Sci & Engn Beijing 100191 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

Test case prioritization assigns the execution priorities of the test cases in a given test suite. Many existing test case prioritization techniques assume the full-fledged availability of code coverage data, fault history, or test specification, which are seldom well-maintained in real-world software development projects. This paper proposes a novel family of input-based local-beam-search adaptive-randomized techniques. They make adaptive tree-based randomized explorations with a randomized candidate test set strategy to even out the search space explorations among the branches of the exploration trees constructed by the test inputs in the test suite. We report a validation experiment on a suite of four medium-size benchmarks. The results show that our techniques achieve either higher APFD values than or the same mean APFD values as the existing code-coverage-based greedy or search-based prioritization techniques, including Genetic, Greedy and ART, in both our controlled experiment and case study. Our techniques are also significantly more efficient than the Genetic and Greedy, but are less efficient than ART. (c) 2015 The Authors. Published by Elsevier Inc.

关键词： Regression testing Adaptive test case prioritization randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving the system of nonsingular tensor equations via randomized Kaczmarz-like method

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2023年 421卷

作者： Wang, Xuezhong Che, Maolin Mo, Changxin Wei, Yimin Hexi Univ Sch Math & Stat Zhangye 734000 Peoples R China Southwest Univ Finance & Econ Sch Math Chengdu 611130 Peoples R China Chongqing Normal Univ Sch Math Sci Chongqing 401331 Peoples R China Fudan Univ Sch Math Sci Shanghai 200433 Peoples R China Fudan Univ Key Lab Math Nonlinear Sci Shanghai 200433 Peoples R China

A great deal of attention has been paid to solve the system of tensor equations in recent years for its applications in various fields. In this paper, the Kaczmarz-like method, which is an effective approach for solving linear equations, is considered to deal with the system of tensor equations with nonsingular coefficient tensors. To reach this goal, two algorithms, i.e., the randomized Kaczmarz-like algorithm and its relaxed version, are proposed. The convergence analysis of these two approaches are given based on matrix SVD and the local tangential cone condition. Moreover, we present estimations of the convergence rate. Several numerical examples are presented to validate the theoretical results and reliability as well as effectiveness.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Kaczmarz method randomized algorithm The system of tensor equations Convergence rate Convergence analysis

来源：评论

学校读者我要写书评

暂无评论

Global value numbering using random interpretation 04

Global value numbering using random interpretation

引用

31st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

作者： Gulwani, S Necula, GC Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

ISBN: (纸本)9781581137293

We present a polynomial time randomized algorithm for global value numbering. Our algorithm is complete when conditionals are treated as non-deterministic and all operators are treated as uninterpreted functions. We are not aware of any complete polynomial-time deterministic algorithm for the same problem. The algorithm does not require symbolic manipulations and hence is simpler to implement than the deterministic symbolic algorithms. The price for these benefits is that there is a probability that the algorithm can report a false equality. We prove that this probability can be made arbitrarily small by controlling various parameters of the algorithm. Our algorithm is based on the idea of random interpretation, which relies on executing a program on a number of random inputs and discovering relationships from the computed values. The computations are done by giving random linear interpretations to the operators in the program. Both branches of a conditional are executed. At join points, the program states are combined using a random affine combination. We discuss ways in which this algorithm can be made more precise by using more accurate interpretations for the linear arithmetic operators and other language constructs.

关键词： global value numbering Herbrand equivalences random interpretation randomized algorithm uninterpreted functions

来源：评论

学校读者我要写书评

暂无评论

Certification Under Uncertainties of Control Methods for Multisource Elevators 1

引用

16th International Conference on Intelligent Systems Design and Applications (ISDA)

作者： Desdouits, Chloe Alamir, Mazen Giroudeau, Rodolphe Le Pape, Claude Univ Grenoble Alpes CNRS GIPSA Lab Domaine Univ F-38000 Grenoble France Univ Montpellier 2 LIRMM UMR 5506 CC477161 Rue Ada F-34095 Montpellier 5 France Schneider Elect Ind SAS 38 TEC Technopole37 Quai Paul Louis Merlin F-38050 Grenoble 09 France

ISBN: (数字)9783319534800

ISBN: (纸本)9783319534800;9783319534794

As the interest in regulating energy usage and participating in the demand-response market is growing, new energy management algorithms emerge. Energy consumption of elevators represents about 5% of the overall consumption of a building. Thus, improving energy performance of elevators becomes a relevant challenge. In this paper, a method is described to assist potential customers in choosing the most relevant storage units and control method for their multisource elevator. In order to obtain a certification on electricity cost savings and maximum power peaks, a randomized algorithm is designed. The best storage units design is found for a given use case, and a guarantee (with a fixed probability) is given that the elevator's consumption from the grid will not exceed a given power peak. Moreover, a similar guarantee is given on the minimum savings that could be achieved, choosing a given controller.

关键词： Energy optimization Robustness randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved Approximation algorithm for Knapsack Median Using Sparsification 23rd

An Improved Approximation Algorithm for Knapsack Median Usin...

引用

23rd Annual European Symposium on algorithms (ESA) as part of ALGO Conference

作者： Byrka, Jaroslaw Pensyl, Thomas Rybicki, Bartosz Spoerhase, Joachim Srinivasan, Aravind Khoa Trinh Univ Warsaw Inst Comp Sci PL-00325 Warsaw Poland Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Instute Adv Comp Studies College Pk MD 20742 USA

ISBN: (纸本)9783662483503;9783662483497

Knapsack median is a generalization of the classic k-median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known algorithms in several ways, including adding randomization and applying sparsification as a preprocessing step. The latter improvement produces the first LP for this problem with bounded integrality gap. The new algorithm obtains an approximation factor of 17.46. We also give a 3.05 approximation with small budget violation.

关键词： approximation algorithm combinatorial optimization randomized algorithm facility-location problems

来源：评论

学校读者我要写书评

暂无评论

Efficient Information Exchange in Single-Hop Multi-Channel Radio Networks

Efficient Information Exchange in Single-Hop Multi-Channel R...

引用

7th International Conference on Wireless algorithms, Systems, and Applications (WASA)

作者： Shi, Weijie Hua, Qiang-Sheng Yu, Dongxiao Wang, Yuexuan Lau, Francis C. M. Tsinghua Univ Inst Interdisciplinary Informat Sci Inst Theoret Comp Sci Beijing 100084 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

ISBN: (纸本)9783642318696

This paper studies the information exchange problem in single-hop multi-channel radio networks, which is to disseminate k messages stored in k arbitrary nodes to the entire network (with n nodes) with the fewest timeslots. By using Theta(root n) channels, the previous best result [9] showed that this problem can be solved in Theta(k) time slots with high probability even if k is unknown and no bounds on k are given. Under the same assumptions but by using Theta(n) channels, this paper presents a novel randomized distributed algorithm called Detect-and-Drop that can solve the information exchange problem in O(log k log log k) time slots with high probability. Thus by allowing using more channels, our proposed algorithm contributes an exponential improvement in running time compared to that in [9]. The simulation results corroborate the analysis result.

关键词： information exchange single hop multiple channels randomized algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Time-Optimal Construction of Overlay Networks 21

Time-Optimal Construction of Overlay Networks

引用

40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Goette, Thorsten Hinnenthal, Kristian Scheideler, Christian Werthmann, Julian Paderborn Univ Paderborn Germany

ISBN: (纸本)9781450385480

We show how to construct an overlay network of constant degree and diameter O(log n) in time O(log n) starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of and establish new connections by sending node identifiers. If the initial network's graph is weakly connected and has constant degree, then our algorithm constructs the desired topology with each node sending and receiving only O(log n) messages in each round in time O(log n), w.h.p., which beats the currently best O(log(3/2) n) time algorithm of [Gotte et al., SIROCCO'19]. Since the problem cannot be solved faster than by using pointer jumping for O(log n) rounds (which would even require each node to communicate Omega(n) bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of [Kwok and Lau, APPROX' 14]. Additionally, we show how our algorithm can be used to efficiently solve graph problems in hybrid networks [Augustine et al., SODA'20]. Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the initial edges is unrestricted. In contrast, only polylogarithmically many messages can be communicated over edges that have been established throughout an algorithm's execution. For an (undirected) graph G with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in time O (log n), w.h.p. Furthermore, we show how to compute an MIS in time O(log d + log log n), w.h.p., where d is the initial degree of G.

关键词： Distributed Protocol Peer-to-Peer Network randomized algorithm Expander

来源：评论

学校读者我要写书评

暂无评论

Low-Rank Tucker Approximation of a Tensor from Streaming Data

引用

SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE 2020年第4期2卷 1123-1150页

作者： Sun, Yiming Guo, Yang Luo, Charlene Tropp, Joel Udell, Madeleine Cornell Univ Dept Stat & Data Sci Ithaca NY 14853 USA Univ Wisconsin Madison Dept Comp Sci Madison WI 53706 USA Columbia Univ New York NY 10027 USA CALTECH Dept Comp Math Sci Pasadena CA 91125 USA Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

This paper describes a new algorithm for computing a low-Tucker-rank approximation of a tensor. The method applies a randomized linear map to the tensor to obtain a sketch that captures the important directions within each mode, as well as the interactions among the modes. The sketch can be extracted from streaming or distributed data or with a single pass over the tensor, and it uses storage proportional to the degrees of freedom in the output Tucker approximation. The algorithm does not require a second pass over the tensor, although it can exploit another view to compute a superior approximation. The paper provides a rigorous theoretical guarantee on the approximation error. Extensive numerical experiments show that the algorithm produces useful results that improve on the state-of-the-art for streaming Tucker decomposition.

关键词： Tucker decomposition tensor compression dimension reduction sketching method randomized algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

ONLINE SET PACKING

引用

SIAM JOURNAL ON COMPUTING 2012年第4期41卷 728-746页

作者： Emek, Yuval Halldorsson, Magnus M. Mansour, Yishay Patt-Shamir, Boaz Radhakrishnan, Jaikumar Rawitz, Dror ETH Comp Engn & Networks Lab CH-8092 Zurich Switzerland Reykjavik Univ Sch Comp Sci IS-103 Reykjavik Iceland Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Tata Inst Fundamental Res Sch Technol & Comp Sci Bombay 400005 Maharashtra India

In online set packing (OSP), elements arrive online, announcing which sets they belong to, and the algorithm needs to assign each element, upon arrival, to one of its sets. The goal is to maximize the number of sets that are assigned all their elements: a set that misses even a single element is deemed worthless. This is a natural online optimization problem that abstracts allocation of scarce compound resources, e.g., multipacket data frames in communication networks. We present a randomized competitive online algorithm for the weighted case with general capacity (namely, where sets may have different values, and elements arrive with different multiplicities). We prove a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximum set size and the maximum number of sets an element belongs to. We also present refined bounds that depend on the uniformity of these parameters.

关键词： online set packing competitive analysis randomized algorithm packet fragmentation multipacket frames

来源：评论

学校读者我要写书评

暂无评论

Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services

引用

PERFORMANCE EVALUATION 2011年第11期68卷 1056-1071页

作者： Lu, Yi Xie, Qiaomin Kliot, Gabriel Geller, Alan Larus, James R. Greenberg, Albert Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA Microsoft Res Extreme Comp Grp Redmond WA USA

The prevalence of dynamic-content web services, exemplified by search and online social networking, has motivated an increasingly wide web-facing front end. Horizontal scaling in the Cloud is favored for its elasticity, and distributed design of load balancers is highly desirable. Existing algorithms with a centralized design, such as Join-the-Shortest-Queue (JSQ), incur high communication overhead for distributed dispatchers. We propose a novel class of algorithms called Join-Idle-Queue (JIQ) for distributed load balancing in large systems. Unlike algorithms such as Power-of-Two, the JIQ algorithm incurs no communication overhead between the dispatchers and processors at job arrivals. We analyze the JIQ algorithm in the large system limit and find that it effectively results in a reduced system load, which produces 30-fold reduction in queueing overhead compared to Power-of-Two at medium to high load. An extension of the basic JIQ algorithm deals with very high loads using only local information of server load. Published by Elsevier B.V.

关键词： Load balancing Queueing analysis randomized algorithm Cloud computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：