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

12th IEEE International Conference on Software Testing, Verification and Validation (ICST)

作者： Lanus, Erin Colbourn, Charles J. Montgomery, Douglas C. Arizona State Univ Sch Comp Informat & Decis Syst Engn Tempe AZ 85281 USA

ISBN: (纸本)9781728108889

Locating arrays are designs used in combinatorial testing with the property that every set of d t-way interactions appears in a unique set of tests. Using a locating array to conduct fault testing ensures that faulty interactions can be located when there are d or fewer faults. Locating arrays are fairly new and few techniques have been explored for their construction. Most of the available work is limited to finding only one fault. Known general methods require a covering array of strength t+ d and produce many more tests than are needed. We present Partitioned Search with Column Resampling (PSCR), a randomized computational search algorithmic framework to verify if an array is ((d) over bar, t)-locating by partitioning the search space to decrease the number of comparisons. If a candidate array is not locating, random resampling is performed until a locating array is constructed or an iteration limit is reached. Results are compared against known locating array constructions from covering arrays of higher strength and against published results of mixed level locating arrays for parameters of real-world systems. The use of PSCR to build larger locating arrays from a variety of ingredient arrays is explored.

关键词： locating array fault location combinatorial testing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost 27

Correlation Clustering with Same-Cluster Queries Bounded by ...

引用

27th Annual European Symposium on algorithms (ESA)

作者： Saha, Barna Subramanian, Sanjay Univ Calif Berkeley Berkeley CA 94720 USA Allen Inst Artificial Intelligence Seattle WA USA

ISBN: (纸本)9783959771245

Several clustering frameworks with interactive (semi-supervised) queries have been studied in the past. Recently, clustering with same-cluster queries has become popular. An algorithm in this setting has access to an oracle with full knowledge of an optimal clustering, and the algorithm can ask the oracle queries of the form, "Does the optimal clustering put vertices u and v in the same cluster?" Due to its simplicity, this querying model can easily be implemented in real crowd-sourcing platforms and has attracted a lot of recent work. In this paper, we study the popular correlation clustering problem (Bansal et al., 2002) under the same-cluster querying framework. Given a complete graph G = (V, E) with positive and negative edge labels, correlation clustering objective aims to compute a graph clustering that minimizes the total number of disagreements, that is the negative intra-cluster edges and positive inter-cluster edges. In a recent work, Ailon et al. (2018b) provided an approximation algorithm for correlation clustering that approximates the correlation clustering objective within (1 + epsilon) with O(k(14) log n log k /epsilon(6)) queries when the number of clusters, k, is fixed. For many applications, k is not fixed and can grow with vertical bar V vertical bar. Moreover, the dependency of k(1)4 on query complexity renders the algorithm impractical even for datasets with small values of k. In this paper, we take a different approach. Let C-OPT be the number of disagreements made by the optimal clustering. We present algorithms for correlation clustering whose error and query bounds are parameterized by C-OPT rather than by the number of clusters. Indeed, a good clustering must have small C-OPT. Specifically, we present an efficient algorithm that recovers an exact optimal clustering using at most 2C(OPT) queries and an efficient algorithm that outputs a 2-approximation using at most C-OPT queries. In addition, we show under a plausible complexity assumption

关键词： Clustering Approximation algorithm Crowdsourcing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized Parameterized algorithms for the Kidney Exchange Problem

引用

algorithmS 2019年第2期12卷 50-50页

作者： Lin, Mugang Wang, Jianxin Feng, Qilong Fu, Bin Cent S Univ Sch Comp Sci & Engn Changsha 410083 Hunan Peoples R China Hengyang Normal Univ Sch Comp Sci & Technol Hengyang 421002 Peoples R China Hunan Prov Key Lab Intelligent Informat Proc & Ap Hengyang 421002 Peoples R China Univ Texas Rio Grande Valley Dept Comp Sci Edinburg TX 78539 USA

In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically 2 <= L <= 5), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases L = 3 and L >= 3, and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.

关键词： kidney exchange problem randomized algorithm parameterized algorithm random partitioning multilinear monomial detection

来源：评论

学校读者我要写书评

暂无评论

RaSMaLai: A randomized Switching algorithm for Maximizing Lifetime in Tree-based Wireless Sensor Networks

RaSMaLai: A Randomized Switching Algorithm for Maximizing Li...

引用

32nd IEEE INFOCOM Conference

作者： Imon, Sk Kajal Arefin Khan, Adnan Di Francesco, Mario Das, Sajal K. Univ Texas Arlington Ctr Res Wireless Mobil & Networking Arlington TX 76019 USA

ISBN: (纸本)9781467359467

In most wireless sensor network (WSN) applications, data are typically gathered by the sensor nodes and reported to a data collection point, called the sink. In order to support such data collection, a tree structure rooted at the sink is usually defined. Based on different aspects, including the actual WSN topology and the available energy budget, the energy consumption of nodes belonging to different paths in the data collection tree may vary significantly. This affects the overall network lifetime, defined in terms of when the first node in the network runs out of energy. In this paper, we address the problem of lifetime maximization of WSNs in the context of data collection trees. In particular, we propose a novel and efficient algorithm, called randomized Switching for Maximizing Lifetime (RaSMaLai) that aims at maximizing the lifetime of WSNs through load balancing with a low time complexity. We further design a distributed version of our algorithm, called D-RaSMaLai. Simulation results show that both the proposed algorithms outperform several existing approaches in terms of network lifetime. Moreover, RaSMaLai offers lower time complexity while the distributed version, D-RaSMaLai, is very efficient in terms of energy expenditure.

关键词： Sensor Networks Load Balancing Data Collection Tree Network Lifetime randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Sublinear Message Bounds for randomized Agreement 18

Sublinear Message Bounds for Randomized Agreement

引用

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

作者： Augustine, John Molla, Anisur Rahaman Pandurangan, Gopal Indian Inst Technol Madras Dept Comp Sci & Engn Chennai Tamil Nadu India Natl Inst Sci Educ & Res Bhubaneswar Sch Comp Sci Khurja Odisha India Univ Houston Dept Comp Sci Houston TX 77204 USA

ISBN: (纸本)9781450357951

This paper focuses on understanding the message complexity of randomized agreement in synchronous distributed networks. We focus on the so-called implicit agreement problem where each node starts with an input value (0 or 1) and at the end one or more nodes should decide on a common input value which should be equal to some node's input value (there can be undecided nodes). Implicit agreement is a generalization of the fundamental agreement and leader election problems. We present sublinear (in n, where n is the number of nodes) algorithms and lower bounds on the message complexity of implicit agreement in fully-connected (i. e., complete) networks. Specifically our main results are: (1) We show that for any implicit agreement algorithm that succeeds with probability at least 1-epsilon, for some suitably small constant. > 0, needs at least Omega(n(0.5)) messages with constant probability. This bound holds regardless of the number of rounds used and applies to both LOCAL and CONGEST models. This lower bound is essentially tight for complete networks, as there exists a randomized agreement algorithm that uses only (O) over tilde (n(0.5)) messages1 with high probability2 and runs in O(1) rounds and succeeds with high probability. Both the upper and lower bounds assume that nodes have access to (only) private coins. (2) In contrast to the above bounds, if nodes have access to an unbiased global (shared) coin, we present a randomized algorithm which, with high probability, achieves implicit agreement, and uses (O) over tilde (n(0.4)) messages in expectation and runs in (O) over tilde (1) rounds (deterministically). This algorithm works in the CONGEST model as well. Our result shows the power of a global coin in significantly improving (by a polynomial factor) the message complexity of agreement. As another contrast, we show that the same benefit does not apply to leader election, i. e., even with access to a global coin, (O) over tilde (n(0.5)) messages (in expectation)

关键词： Distributed algorithm randomized algorithm Agreement Leader Election Global Coin Shared Randomness

来源：评论

学校读者我要写书评

暂无评论

FLIP-FLOP SPECTRUM-REVEALING QR FACTORIZATION AND ITS APPLICATIONS TO SINGULAR VALUE DECOMPOSITION

引用

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2019年 51卷 469-494页

作者： Feng, Yuehua Xiao, Jianwei Gu, Ming Shanghai Univ Engn Sci Sch Math Phys & Stat Shanghai Peoples R China Univ Calif Berkeley Dept Math Berkeley CA 94720 USA

We present the Flip-Flop Spectrum-Revealing QR (Flip-Flop SRQR) factorization, a significantly faster and more reliable variant of the QLP factorization of Stewart for low-rank matrix approximations. Flip-Flop SRQR uses SRQR factorization to initialize a partial column-pivoted QR factorization and then computes a partial LQ factorization. As observed by Stewart in his original QLP work, Flip-Flop SRQR tracks the exact singular values with "considerable fidelity". We develop singular value lower bounds and residual error upper bounds for the Flip-Flop SRQR factorization. In situations where singular values of the input matrix decay relatively quickly, the low-rank approximation computed by Flip-Flop SRQR is guaranteed to be as accurate as the truncated SVD. We also perform a complexity analysis to show that Flip-Flop SRQR is faster than the randomized subspace iteration for approximating the SVD, the standard method used in the Matlab tensor toolbox. We additionally compare Flip-Flop SRQR with alternatives on two applications, a tensor approximation and a nuclear norm minimization, to demonstrate its efficiency and effectiveness.

关键词： QR factorization randomized algorithm low-rank approximation approximate SVD higher-order SVD nuclear norm minimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Optimization of Resource Distribution and Encryption for Data Storage in the Cloud

引用

IEEE TRANSACTIONS ON CLOUD COMPUTING 2018年第2期6卷 428-439页

作者： Luna, Jose Marcio Abdallah, Chaouki T. Heileman, Gregory L. Univ Penn Dept Comp & Informat Sci 200 S 33Rd St Philadelphia PA 19104 USA Univ New Mexico Dept Elect & Comp Engn Albuquerque NM 87131 USA

In this paper, we develop a decentralized probabilistic method for performance optimization of cloud services. We focus on Infrastructure-as-a-Service where the user is provided with the ability of configuring virtual resources on demand in order to satisfy specific computational requirements. This novel approach is strongly supported by a theoretical framework based on tail probabilities and sample complexity analysis. It allows not only the inclusion of performance metrics for the cloud but the incorporation of security metrics based on cryptographic algorithms for data storage. To the best of the authors' knowledge this is the first unified approach to provision performance and security on demand subject to the Service Level Agreement between the client and the cloud service provider. The quality of the service is guaranteed given certain values of accuracy and confidence. We present some experimental results using the Amazon Web Services, Amazon Elastic Compute Cloud service to validate our probabilistic optimization method.

关键词： Cloud computing IaaS performance security optimization randomized algorithm cryptography

来源：评论

学校读者我要写书评

暂无评论

Matrix completion with capped nuclear norm via majorized proximal minimization

引用

NEUROCOMPUTING 2018年 316卷 190-201页

作者： Kuang, Shenfen Chao, Hongyang Li, Qia Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou Guangdong Peoples R China Shaoguan Univ Sch Math & Stat Shaoguan Peoples R China CVTE Res Guangzhou Guangdong Peoples R China Sun Yat Sen Univ Minist Educ Key Lab Machine Intelligence & Adv Comp Guangzhou Guangdong Peoples R China

We investigate the problem of matrix completion with capped nuclear norm regularization. Different from most existing regularizations that minimize all the singular values simultaneously, capped nuclear norm only penalties the singular values smaller than certain threshold. Due to its non-smoothness and non-convexity, by formulating with Majorization Minimization (MM) approach, we develop a fast Majorized Proximal Minimization Impute (MPM-Impute) algorithm. At each iteration, the sub-problem is relaxed to a surrogate (upper bound) function and solved via proximal minimization with closed form solution. Though it requires singular value decompositions (SVD) at each iteration, by incorporating with the randomized algorithm, we propose the randomized Truncated Singular Value Thresholding (RTSVT) operator to lower the computational cost. In addition, in contrast with most MM approaches, our algorithm is guaranteed to converge to the stationary points. Experimental results on synthetic data, image inpainting show that the completion results exceed or achieve comparable performance than state-of-the-art, yet several times faster. (C) 2018 Published by Elsevier B.V.

关键词： Capped nuclear norm Non-convex regularization Majorization minimization randomized algorithm Matrix completion

来源：评论

学校读者我要写书评

暂无评论

An Improved Approximation algorithm for Knapsack Median Using Sparsification

引用

algorithmICA 2018年第4期80卷 1093-1114页

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

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：