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

Work-Competitive Scheduling on Task Dependency Graphs

PARALLEL PROCESSING LETTERS 2015年第2期25卷 1550001-1550001页

作者： Kari, Chadi Russell, Alexander Shashidhar, Narasimha Univ Pacific Sch Engn & Comp Sci 3601 Pacific Ave Stockton CA 95211 USA Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA Sam Houston State Univ Dept Comp Sci Huntsville TX 77341 USA

A fundamental problem in distributed computing is the task of cooperatively executing a given set of t tasks by p asynchronous processors where the communication medium is dynamic and subject to failures. Also known as do-all, this problem been studied extensively in various distributed settings. In [2], the authors consider a partitionable network scenario and analyze the competitive performance of a randomized scheduling algorithm for the case where the tasks to be completed are independent of each other. In this paper, we study a natural extension of this problem where the tasks have dependencies among them. We present a simple randomized algorithm for p processors cooperating to perform t known tasks where the dependencies between them are defined by a k-partite task dependency graph and additionally these processors are subject to a dynamic communication medium. By virtue of the problem setting, we pursue competitive analysis where the performance of our algorithm is measured against that of the omniscient offline algorithm which has complete knowledge of the dynamics of the communication medium. We show that the competitive ratio of our algorithm is tight and depends on the dynamics of the communication medium viz. the computational width defined in [2] and also on the number of partitions of the task dependency graph.

关键词： On-line algorithms distributed computing randomized algorithms competitive analysis partitionable networks

来源：评论

学校读者我要写书评

暂无评论

DENOISING USING MULTI-STAGE randomized ORTHOGONAL MATCHING PURSUIT

DENOISING USING MULTI-STAGE RANDOMIZED ORTHOGONAL MATCHING P...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Koskinas, Stefanos Psaromiligkos, Ioannis McGill Univ Dept Elect & Comp Engn Montreal PQ Canada

ISBN: (纸本)9781479928934

Orthogonal Matching Pursuit (OMP) can denoise a signal by greedily approximating a least-squares (LS) estimate as a linear combination of elements (atoms) of a dictionary. OMP iteratively decomposes a signal through deterministic atom selections at each iteration step. Recently proposed randomized OMP algorithms employ random atom selections instead and have the potential to further improve denoising. Typically, the best approximation from these algorithms can be obtained only within a narrow range of iterations. In this paper, we propose a novel multi-stage randomized OMP (MS-ROMP) denoising approach that performs successive ROMP runs, each denoising the obtained estimate from the previous one. We show through simulations that, under certain conditions, this can significantly improve denoising performance by producing a good approximation after any number of iterations beyond the sparsity level.

关键词： Greedy approximation orthogonal matching pursuit randomized algorithms signal denoising

来源：评论

学校读者我要写书评

暂无评论

Performance Optimization and Regulation for Multitier Servers

Performance Optimization and Regulation for Multitier Server...

引用

IEEE Annual Conference on Decision and Control

作者： Jose Marcio Luna Chaouki T. Abdallah Gregory L. Heileman Department of Computer and Information Science University of Pennsylvania Philadelphia PA 19104 USA Department of Electrical and Computer Engineering University of New Mexico Albuquerque NM 87131 USA

ISBN: (纸本)9781479978878

In this paper we present a novel approach to optimize and regulate performance in a multitier server. By using a queueing network model, we optimize the values of the mean service rates at each tier in the server by applying randomized algorithms based on statistical learning theory. After the optimization process is carried out, an IPA algorithm is implemented to regulate the throughput of the system to the calculated optimal reference value in a closed loop. The case study of a server with three tiers is simulated to validate our approach.

关键词： Servers Optimization Procedure Standing Orders reference value Throughput Queuing Network Model randomized algorithms Queueing networks Case studies TIERING Statistical learning

来源：评论

学校读者我要写书评

暂无评论

TOWARD randomized TESTING OF q-MONOMIALS IN MULTIVARIATE POLYNOMIALS

引用

DISCRETE MATHEMATICS algorithms AND APPLICATIONS 2014年第2期6卷 np页

作者： Chen, Shenshi Chen, Yaqing Yang, Quanhai Univ Texas Pan Amer Dept Comp Sci Edinburg TX 78539 USA Northwest A&F Univ Coll Informat Engn Yangling 712100 Shaanxi Peoples R China

Given any fixed integer q >= 2, a q-monomial is of the format x (s1)(i1) x (s2)(i2) ... x (st)(it) such that 1 = 2 is prime. When q > 2 is not prime, it remains open whether the problem of testing q-monomials ca... 详细信息

Given any fixed integer q >= 2, a q-monomial is of the format x (s1)(i1) x (s2)(i2) ... x (st)(it) such that 1 <= sj <= q -1, 1 <= j <= t. q-monomials are natural generalizations of multilinear monomials. Recent research on testing multilinear monomials and q-monomials for prime q in multivariate polynomials relies on the property that Z(q) is a field when q >= 2 is prime. When q > 2 is not prime, it remains open whether the problem of testing q-monomials can be solved in some compatible complexity. In this paper, we present a randomized O*(7.15(k)) algorithm for testing q-monomials of degree k that are found in a multivariate polynomial that is represented by a tree-like circuit with a polynomial size, thus giving a positive, affirming answer to the above question. Our algorithm works regardless of the primality of q and improves upon the time complexity of the previously known algorithm for testing q-monomials for prime q > 7.

关键词： Algebra complexity multivariate polynomials monomials monomial testing randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Combining Analytical Technique and randomized Algorithm in Safety Verification of Stochastic Hybrid Systems

Combining Analytical Technique and Randomized Algorithm in S...

引用

American Control Conference

作者： Julius, A. Agung D'Innocenzo, Alessandro Rensselaer Polytech Inst Dept Elect Comp & Syst Engn Troy NY 12180 USA

ISBN: (纸本)9781479932740

We consider the problem of probabilistic safety verification for stochastic hybrid systems. In particular, we propose a method that combines two existing approaches, namely, analytical techniques and randomized algorithms. Analytical techniques, such as using stochastic approximate bisimulation, are able to handle non-deterministic initial states. However, their practical applicability is limited to relatively simple stochastic dynamics. On the other hand, randomized algorithms are able to handle more complex dynamics. However, it typically requires running a large number of simulations, and cannot be used for non-deterministic initial states. Our combined approach basically uses an analytical technique when the stochastic dynamics is simple, and switches to a randomized algorithm when the dynamics is nonlinear. The main idea is that by using the analytical technique, we can bound the gaps between the probability density functions corresponding to the family of non-deterministic initial states. This, in turn, enables randomized algorithms that provide upperand lower-bounds on the safety and unsafety probabilities. We illustrate our approach with an example from air traffic management.

关键词： hybrid systems verification randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Power of d Choices for Large-Scale Bin Packing: A Loss Model 15

Power of d Choices for Large-Scale Bin Packing: A Loss Model

引用

Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

作者： Qiaomin Xie Xiaobo Dong Yi Lu Rayadurgam Srikant University of Illinois at Urbana-Champaign Urbana IL USA

ISBN: (纸本)9781450334860

We consider a system of $N$ parallel servers, where each server consists of B units of a resource. Jobs arrive at this system according to a Poisson process, and each job stays in the system for an exponentially distributed amount of time. Each job may request different units of the resource from the system. The goal is to understand how to route arriving jobs to the servers to minimize the probability that an arriving job does not find the required amount of resource at the server, i.e., the goal is to minimize blocking probability. The motivation for this problem arises from the design of cloud computing systems in which the jobs are virtual machines (VMs) that request resources such as memory from a large pool of servers. In this paper, we consider power-of-d-choices routing, where a job is routed to the server with the largest amount of available resource among d ≥ 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity and provide an explicit upper bound for the equilibrium blocking probability. We show that the upper bound exhibits different behavior as B goes to infinity depending on the relationship between the total traffic intensity λ and B. In particular, if (B -- λ)/√λ → α, the upper bound is doubly exponential in √λ and if (B -- λ)/logd λ → β, β > 1, the upper bound is exponential in λ. Simulation results show that the blocking probability, even for small B, exhibits qualitatively different behavior in the two traffic regimes. This is in contrast with the result for random routing, where the blocking probability scales as O(1/√λ) even if (B -- λ)/√λ → α.

关键词： resource allocation fluid limit analysis randomized algorithms virtual machine assignment loss model

来源：评论

学校读者我要写书评

暂无评论

Density and regularity theorems for semi-algebraic hypergraphs 15

Density and regularity theorems for semi-algebraic hypergrap...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Jacob Fox Janos Pach Andrew Suk Massachusetts Institute of Technology EPFL Lausanne and Courant Institute University of Illinois at Chicago

ISBN: (纸本)9781510813311

A k-uniform semi-algebraic hypergraph H is a pair (P, E), where P is a subset of R~d and E is a collection of k-tuples {p1,...,p_k} is contained in P such that (p_1,...,p_k) ∈ E if and only if the kd coordinates of the pi-s satisfy a boolean combination of a finite number of polynomial inequalities. The complexity of H can be measured by the number and the degrees of these inequalities and the number of variables (coordinates) kd. Several classical results in extremal hypergraph theory can be substantially improved when restricted to semialgebraic hypergraphs. Substantially improving a theorem of Fox, Gromov, Lafforgue, Naor, and Pach, we establish the following "polynomial regularity lemma": For any 0 < ε < 1/2, the vertex set of every k-uniform semi-algebraic hypergraph H = (P, E) can be partitioned into at most (1/ε)~c parts P_1, P_2,..., as equal as possible, such that all but at most an ε-fraction of the k-tuples of parts (P_(i_1),..., P_(i_k)) are homogeneous in the sense that either every k-tuple (p_(i_1),...p_(i_k)) ∈ P_(i_1) × ... × P_(i_k) belongs to E or none of them do. Here c > 0 is a constant that depends on the complexity of H. We also establish an improved lower bound, single exponentially decreasing in k, on the best constant δ > 0 such that the vertex classes P_1,..., P_k of every k-partite k-uniform semi-algebraic hypergraph H = (P_1 ∪...∪ P_k, E) with |E| ≥ εΠ_(j=1)~k |P_i| have, for 1 ≤ i ≤ k, δ|P_i|-element subsets P'_i is contained in P_i satisfying P'_1 × ... × P'_k is contained in E. The best previously known lower bound on δ due to Bukh and Hubard decreased double exponentially fast in k. We give three geometric applications of our results. In particular, we establish the following strengthening of the so-called same-type lemma of Barany and Valtr: Any disjoint finite sets P_1,..., P_k is contained in R~d (k > d) have for 1 ≤ i ≤ k subsets P'_i of size at least 2~(-O(d~3k log k))|P_i| with the property that every k-tuple formed by taking on

关键词： hypergraph Hydrogen CIRCUIT TO PRESSURE CONVERTER Theorem instruction type randomized algorithms inequalities

来源：评论

学校读者我要写书评

暂无评论

IMPROVED MATRIX algorithms VIA THE SUBSAMPLED randomized HADAMARD TRANSFORM

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2013年第3期34卷 1301-1340页

作者： Boutsidis, Christos Gittens, Alex IBM TJ Watson Res Ctr Dept Math Sci Yorktown Hts NY 10598 USA CALTECH Appl & Computat Math Dept Pasadena CA 91125 USA

Several recent randomized linear algebra algorithms rely upon fast dimension reduction methods. A popular choice is the subsampled randomized Hadamard transform (SRHT). In this article, we address the efficacy, in the Frobenius and spectral norms, of an SRHT-based low-rank matrix approximation technique introduced by Woolfe, Liberty, Rohklin, and Tygert. We establish a slightly better Frobenius norm error bound than is currently available, and a much sharper spectral norm error bound (in the presence of reasonable decay of the singular values). Along the way, we produce several results on matrix operations with SRHTs (such as approximate matrix multiplication) that may be of independent interest. Our approach builds upon Tropp's in "Improved Analysis of the Subsampled randomized Hadamard Transform" [Adv. Adaptive Data Anal., 3 (2011), pp. 115-126].

关键词： low-rank approximation least-squares regression Hadamard transform sampling randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity 15

A polylogarithmic space deterministic streaming algorithm fo...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Timothy Naumovitz Michael Saks Department of Mathematics Rutgers University

ISBN: (纸本)9781510813311

The distance to monotonicity of a sequence of n numbers is the minimum number of entries whose deletion leaves an increasing sequence. We give the first deterministic streaming algorithm that approximates the distance to monotonicity within a 1 + ε factor for any fixed ε > 0 and runs in space polylogarithmic in the length of the sequence and the range of the numbers. The best previous deterministic algorithm achieving the same approximation factor required space Ω(n~(1/2)) [9]. Previous polylogarithmic space algorithms were either randomized [10], or had approximation factor no better than 2 [8]. We also present space lower bounds for this problem: Any deterministic streaming algorithm that gets a 1 + ε approximation requires space Ω(1/ε log~2(n)) and any randomized algorithm requires space Ω(1/ε(log~2(n))/(log log(n))).

关键词： monotonicity Streaming increasing sequence deterministic randomized algorithms Lower bound algorithms total number of arm entries approximation entry

来源：评论

学校读者我要写书评

暂无评论

Competitive router scheduling with structured data

引用

THEORETICAL COMPUTER SCIENCE 2014年 530卷 12-22页

作者： Mansour, Yishay Patt-Shamir, Boaz Rawitz, Dror Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

We consider the task of transmitting structured information over bounded-capacity links. Our information model is a stream of basic units called superpackets that are broken into k packets each. To model the possible structure and redundancy of the superpackets, we assume that for each superpacket there is a collection of minimal subsets of packets whose delivery makes the superpacket useful. This very general model encompasses, for example. MPEG streams, where one can think of a group of pictures (GoP) as a superpacket. The fundamental difficulty is that networks can forward only the primitive packets, but applications can use only superpackets, and thus if no minimal subset is delivered, the whole superpacket becomes useless. Our aim is to maximize goodput (number of useful superpackets) in the face of overloaded communication links, where we are forced to drop some packets. Specifically, we assume that an arbitrary stream of packets arrives at a router with multiple bounded-capacity outgoing links. An online algorithm needs to decide, for each superpacket, which outgoing link to use (all packets of the same superpacket must use the same link) and, in case of an overload at a link, which packets to drop and which to transmit so as to maximize goodput. We analyze a simple randomized competitive algorithm for the general case and provide a nearly matching lower bound on the competitive ratio of any randomized online algorithm. (C) 2014 Elsevier By. All rights reserved.

关键词： Competitive analysis Packet fragmentation randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：