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

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Englert, Matthias Raecke, Harald Stotz, Richard Univ Warwick DIMAP Coventry W Midlands England Univ Warwick Dept Comp Sci Coventry W Midlands England Tech Univ Munich Dept Informat Munich Germany

ISBN: (纸本)9781728149523

In the Generalized Reordering Buffer Management Problem (GRBM) a sequence of items located in a metric space arrives online, and has to be processed by a set of k servers moving within the space. In a single step the first b still unprocessed items from the sequence are accessible, and a scheduling strategy has to select an item and a server. Then the chosen item is processed by moving the chosen server to its location. The goal is to process all items while minimizing the total distance travelled by the servers. This problem was introduced in [Chan, Megow, Sitters, van Stee TCS 12] and has been subsequently studied in an online setting by [Azar, Englert, Gamzu, Kidron STACS 14]. The problem is a natural generalization of two very well-studied problems: the k-server problem for b = 1 and the Reordering Buffer Management Problem (RBM) for k = 1. In this paper we consider the GRBM problem on a uniform metric in the online version. We show how to obtain a competitive ratio of O (log k (log k + log log b)) for this problem. Our result is a drastic improvement in the dependency on b compared to the previous best bound of O (root/b log k), and is asymptotically optimal for constant k, because Omega (log k+log log b) is a lower bound for GRBM on uniform metrics.

关键词： Online computing randomized algorithms Reordering buffer management

来源：评论

学校读者我要写书评

暂无评论

Compressed randomized UTV Decompositions for Low-Rank Matrix Approximations

引用

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2018年第6期12卷 1155-1169页

作者： Kaloorazi, Maboud F. de Lamare, Rodrigo C. Pontifical Catholic Univ Rio de Janeiro Ctr Telecommun Studies CETUC BR-22451000 Rio De Janeiro Brazil Univ York Dept Elect York YO10 5DD N Yorkshire England

Low-rankmatrix approximations play a fundamental role in numerical linear algebra and signal processing applications. This paper introduces a novel rank-revealing matrix decomposition algorithm termed compressed randomized UTV (CoR-UTV) decomposition along with a CoR-UTV variant aided by the power method technique. CoR-UTV is primarily developed to compute an approximation to a low-rank input matrix by making use of random sampling schemes. Given a large and dense matrix of size m x n with numerical rank k, where k << min{m, n}, CoRUTV requires a few passes over the data, and runs in O(mnk) floating-point operations. Furthermore, CoR-UTV can exploit modern computational platforms and, consequently, can be optimized for maximum efficiency. CoR-UTV is simple and accurate, and outperforms reported alternative methods in terms of efficiency and accuracy. Simulations with synthetic data as well as real data in image reconstruction and robust principal component analysis applications support our claims.

关键词： Matrix computations low-rank approximations UTV decomposition randomized algorithms dimension reduction matrix decomposition image reconstruction robust PCA

来源：评论

学校读者我要写书评

暂无评论

Safe approximations of chance constrained sets by probabilistic scaling 18

Safe approximations of chance constrained sets by probabilis...

引用

18th European Control Conference (ECC)

作者： Alamo, Teodoro Mirasierra, Victor Dabbene, Fabrizio Lorenzen, Matthias Univ Seville Dept Ingn Sistemas & Automat Escuela Super Ingenieros Camino Descubrimientos S-N Seville 41092 Spain Politecn Torino Natl Res Council Italy CNR IEIIT Inst Elect Comp & Telecommun Engn I-10129 Corso Duca Degli Abruzzi Italy Univ Stuttgart Inst Syst Theory & Automat Control Stuttgart Germany

ISBN: (纸本)9783907144008

Motivated by problems arising in robust control, we develop a sampling-based methodology to obtain an inner approximation of the region of the design space that satisfies a given set of probabilistic constraints (chance constrained set). Given a set of manageable complexity centered at a point satisfying the probabilistic constraints, we show how to scale it around its center to obtain, with a user defined probability, a region that is included in the chance constrained set. The proposed approach does not require any assumption on the Vapnik-Chervonenkis dimension of the robust problem under consideration. Moreover, its sample complexity does not depend on the dimension of the design space. We show the advantages of the proposed approach by means of an illustrative example.

关键词： randomized algorithms probabilistic robustness uncertain systems statistical learning theory

来源：评论

学校读者我要写书评

暂无评论

Subspace-Orbit randomized Decomposition for Low-Rank Matrix Approximations

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2018年第16期66卷 4409-4424页

作者： Kaloorazi, Maboud Farzaneh de lamare, Rodrigo C. Pontifical Univ Catholic Rio de Janeiro Ctr Telecommun Studies BR-22451000 Rio De Janeiro Brazil Univ York Dept Elect York YO10 5DD N Yorkshire England

An efficient, accurate, and reliable approximation of a matrix by one of lower rank is a fundamental task in numerical linear algebra and signal processing applications. In this paper, we introduce a newmatrix decomposition approach termed subspace-orbit randomized singular value decomposition (SOR-SVD), which makes use of random sampling techniques to give a low-rank approximation to an input matrix. Given a large and dense data matrix of sizem x n, the algorithm requires a few passes through data to compute a rank-k approximation in O(mnk) floating-point operations. Moreover, the SOR-SVD algorithm can utilize advanced computer architectures and, as a result, it can be optimized for maximum efficiency. The SOR-SVD algorithm is simple, accurate, and provably correct, and outperforms previously reported techniques in terms of accuracy and efficiency. Our numerical experiments support these claims.

关键词： Matrix computations dimension reduction low-rank approximation randomized algorithms robust PCA

来源：评论

学校读者我要写书评

暂无评论

Faster Minimum k-cut of a Simple Graph 60

Faster Minimum k-cut of a Simple Graph

引用

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Li, Jason Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

ISBN: (纸本)9781728149523

We consider the (exact, minimum) k-CUT problem: given a graph and an integer k, delete a minimum-weight set of edges so that the remaining graph has at least k connected components. This problem is a natural generalization of the global minimum cut problem, where the goal is to break the graph into k = 2 pieces. Our main result is a (combinatorial) k-CUT algorithm on simple graphs that runs in n((1+ o(1))k) time for any constant k, improving upon the previously best n((2 omega/3+o(1))k) time algorithm of Gupta et al. [FOCS'18] and the previously best n((1.981+o(1))k) time combinatorial algorithm of Gupta et al. [STOC'19]. For combinatorial algorithms, this algorithm is optimal up to o(1) factors assuming recent hardness conjectures: we show by a straightforward reduction that k-CUT on even a simple graph is as hard as (k-1)-clique, establishing a lower bound of n((1-o(1))k) for k-CUT. This settles, up to lower-order factors, the complexity of k-CUT on a simple graph for combinatorial algorithms.

关键词： minimum k-cut graph algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

The power of randomization by sex in multilocus genetic evolution

引用

BIOLOGY DIRECT 2020年第1期15卷 26-26页

作者： Vasylenko, Liudmyla Feldman, Marcus W. Livnat, Adi Univ Haifa Dept Evolutionary & Environm Biol 199 Aba Khoushy Ave IL-3498838 Haifa Israel Univ Haifa Inst Evolut 199 Aba Khoushy Ave IL-3498838 Haifa Israel Stanford Univ Dept Biol 371 Jane Stanford Way Stanford CA 94305 USA

Background Many hypotheses have been proposed for how sexual reproduction may facilitate an increase in the population mean fitness, such as the Fisher-Muller theory, Muller's ratchet and others. According to the recently proposed mixability theory, however, sexual recombination shifts the focus of natural selection away from favoring particular genetic combinations of high fitness towards favoring alleles that perform well across different genetic combinations. Mixability theory shows that, in finite populations, because sex essentially randomizes genetic combinations, if one allele performs better than another across the existing combinations of alleles, that allele will likely also perform better overall across a vast space of untested potential genotypes. However, this superiority has been established only for a single-locus diploid model. Results We show that, in both haploids and diploids, the power of randomization by sex extends to the multilocus case, and becomes substantially stronger with increasing numbers of loci. In addition, we make an explicit comparison between the sexual and asexual cases, showing that sexual recombination is the cause of the randomization effect. Conclusions That the randomization effect applies to the multilocus case and becomes stronger with increasing numbers of loci suggests that it holds under realistic conditions. One may expect, therefore, that in nature the ability of an allele to perform well in interaction with existing genetic combinations is indicative of how well it will perform in a far larger space of potential combinations that have not yet materialized and been tested. Randomization plays a similar role in a statistical test, where it allows one to draw an inference from the outcome of the test in a small sample about its expected outcome in a larger space of possibilities-i.e., to generalize. Our results are relevant to recent theories examining evolution as a learning process.

关键词： Random sampling Sex and recombination Epistasis randomized algorithms Multilocus models Interaction-based evolution

来源：评论

学校读者我要写书评

暂无评论

randomized LU decomposition

引用

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2018年第2期44卷 246-272页

作者： Shabat, Gil Shmueli, Yaniv Aizenbud, Yariv Averbuch, Amir Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Math Sci Dept Appl Math IL-69978 Tel Aviv Israel

randomized algorithms play a central role in low rank approximations of large matrices. In this paper, the scheme of the randomized SVD is extended to a randomized LU algorithm. Several error bounds are introduced, that are based on recent results from random matrix theory related to subgaussian matrices. The bounds also improve the existing bounds of already known randomized SVD algorithm. The algorithm is fully parallelized and thus can utilize efficiently GPUs without any CPU GPU data transfer. Numerical examples, which illustrate the performance of the algorithm and compare it to other decomposition methods, are presented. (C) 2016 Elsevier Inc. All rights reserved.

关键词： LU decomposition Matrix factorizations Random matrices randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Online Resource Allocation with Matching Constraints 18

Online Resource Allocation with Matching Constraints

引用

18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

作者： Dickerson, John P. Sankararaman, Karthik Abinav Sarpatwar, Kanthi Kiran Srinivasan, Aravind Wu, Kun-Lung Xu, Pan Univ Maryland College Pk MD 20742 USA IBM Res AI Yorktown Hts NY USA

ISBN: (纸本)9781450363099

Matching markets with historical data are abundant in many applications, e.g., matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, and jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (e.g., candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi-Budgeted Online Assignment with Known Adversarial Distributions. In this model, we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type j arrives. Assigning this job to a server i yields a profit w(i,) (j) while consuming a(e) is an element of[0, 1](K) quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristics adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it.

关键词： Online Scheduling Online Matching randomized algorithms Fairness

来源：评论

学校读者我要写书评

暂无评论

Declarative Implementations of Genetic algorithms in Control Network Programming 19

Declarative Implementations of Genetic Algorithms in Control...

引用

20th Bulgarian International Computer Science and Technologies Conference (CompSysTech)

作者： Golemanova, Emilia Golemanov, Tzanko Ruse Univ Comp Syst & Technol Ruse Bulgaria

ISBN: (纸本)9781450371490

The paper describes how the built-in tools for stochastic dynamic control of the computation process in a programming paradigm, named Control Network Programming (CNP), could be used to achieve declarative (non-procedural) implementations of a genetic algorithm. As these implementations are very intuitive and easily programmed, CNP can be used as an excellent approach for teaching, learning and programming the basic model of the genetic algorithms. They are presented on the well-known 8-queens problem often used as an example problem for various programming techniques, including non-traditional approaches such as genetic algorithms. More specifically, the emphasis is on automatic, non-procedural modelling of certain selection operators such as roulette wheel selection and rank selection, as well as the Bernoulli trial, used in crossover and mutation operators.

关键词： Control Network Programming declarative programming graphical programming genetic algorithm roulette wheel selection rank selection randomized algorithms probabilistic computation

来源：评论

学校读者我要写书评

暂无评论

Locality-Preserving Oblivious RAM 38th

Locality-Preserving Oblivious RAM

引用

38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT)

作者： Asharov, Gilad Chan, T. -H. Hubert Nayak, Kartik Pass, Rafael Ren, Ling Shi, Elaine Cornell Cornell Tech New York NY 10044 USA Univ Hong Kong Pok Fu Lam Hong Kong Peoples R China Univ Maryland College Pk MD 20742 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9783030176563;9783030176556

Oblivious RAMS, introduced by Goldreich and Ostrovsky [JACM'96], compile any RAM program into one that is "memory oblivious", i.e., the access pattern to the memory is independent of the input. All previous ORAM schemes, however, completely break the locality of data accesses (for instance, by shuffling the data to pseudorandom positions in memory). In this work, we initiate the study of locality-preserving ORAMs-ORAMs that preserve locality of the accessed memory regions, while leaking only the lengths of contiguous memory regions accessed. Our main results demonstrate the existence of a locality-preserving ORAM with poly-logarithmic overhead both in terms of bandwidth and locality. We also study the tradeoff between locality, bandwidth and leakage, and show that any scheme that preserves locality and does not leak the lengths of the contiguous memory regions accessed, suffers from prohibitive bandwidth. To the best of our knowledge, before our work, the only works combining locality and obliviousness were for symmetric searchable encryption [e.g., Cash and Tessaro (EUROCRYPT'14), Asharov et al. (STOC'16)]. Symmetric search encryption ensures obliviousness if each keyword is searched only once, whereas ORAM provides obliviousness to any input program. Thus, our work generalizes that line of work to the much more challenging task of preserving locality in ORAMs.

关键词： Oblivious RAM Locality randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：