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

streaming algorithms for Bin Packing and Vector Scheduling 1

17th International Workshop on Approximation and Online algorithms (WAOA)

作者： Cormode, Graham Vesely, Pavel Univ Warwick Dept Comp Sci Coventry W Midlands England

ISBN: (数字)9783030394790

ISBN: (纸本)9783030394790;9783030394783

Problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling, are fundamental tasks in combinatorial optimization. These are well understood in the traditional online and offline cases, but have been less well-studied when the volume of the input is truly massive, and cannot even be read into memory. This is captured by the streaming model of computation, where the aim is to approximate the cost of the solution in one pass over the data, using small space. As a result, streaming algorithms produce concise input summaries that approximately preserve the optimum value. We design the first efficient streaming algorithms for these fundamental problems in combinatorial optimization. For BIN PACKING, we provide a streaming asymptotic 1 + epsilon-approximation with (O) over tilde (1/epsilon) memory, where (O) over tilde hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming d + epsilon-approximation for VECTOR BIN PACKING in d dimensions, running in space (O) over tilde (d/epsilon). For the related VECTOR SCHEDULING problem, we show how to construct an input summary in space (O) over tilde (d(2). m/epsilon(2)) that preserves the optimum value up to a factor of 2 - 1/m + epsilon, where m is the number of identical machines.

关键词： streaming algorithms Bin Packing Scheduling

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Robust Distinct Elements 16

Streaming Algorithms for Robust Distinct Elements

引用

ACM SIGMOD International Conference on Management of Data

作者： Chen, Di Zhang, Qin Hong Kong Univ Sci & Technol Kowloon Hong Kong Peoples R China Indiana Univ Bloomington Bloomington IN 47401 USA

ISBN: (纸本)9781450335317

We study the problem of estimating distinct elements in the data stream model, which has a central role in traffic monitoring, query optimization, data mining and data integration. Different from all previous work, we study the problem in the noisy data setting, where two different looking items in the stream may reference the same entity (determined by a distance function and a threshold value), and the goal is to estimate the number of distinct entities in the stream. In this paper, we formalize the problem of robust distinct elements, and develop space and time-efficient streaming algorithms for datasets in the Euclidean space, using a novel technique we call bucket sampling. We also extend our algorithmic framework to other metric spaces by establishing a connection between bucket sampling and the theory of locality sensitive hashing. Moreover, we formally prove that our algorithms are still effective under small distinct elements ambiguity. Our experiments demonstrate the practicality of our algorithms.

关键词： streaming algorithms noisy data distinct elements

来源：评论

学校读者我要写书评

暂无评论

Multi-Pass streaming algorithms for Monotone Submodular Function Maximization

引用

THEORY OF COMPUTING SYSTEMS 2022年第1期66卷 354-394页

作者： Huang, Chien-Chung Kakimura, Naonori Ecole Normale Super CNRS Paris France Keio Univ Yokohama Kanagawa Japan

We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a small fraction of the data stored in primary memory. We propose the following streaming algorithms taking O(epsilon(-1)) passes: (1) a (1-e(-1)-epsilon)-approximation algorithm for the cardinality-constrained problem, (2) a (0.5 - epsilon)-approximation algorithm for the knapsack-constrained problem. Both of our algorithms run deterministically in O* (n) time, using O* (K) space, where n is the size of the ground set and K is the size of the knapsack. Here the term O* hides a polynomial of log K and epsilon(-1). Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes O (n epsilon(-1) log (epsilon(-1) log K)) time, improving on the algorithm of Badanidiyuru and Vondrak that takes O (n epsilon(-1)log (epsilon(-1) K)) time.

关键词： streaming algorithms Approximation algorithms Submodular function maximization

来源：评论

学校读者我要写书评

暂无评论

LOWER BOUNDS ON streaming algorithms FOR APPROXIMATING THE LENGTH OF THE LONGEST INCREASING SUBSEQUENCE

引用

SIAM JOURNAL ON COMPUTING 2010年第8期39卷 3463-3479页

作者： Gal, Anna Gopalan, Parikshit Univ Texas Austin Dept Comp Sci Austin TX 78712 USA Microsoft Res Silicon Valley Mountain View CA 94043 USA

We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space Omega(root n). This proves a conjecture made by Gopalan et al. [Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete algorithms, 2007, pp. 318-327] who proved a matching upper bound. Our results yield asymptotically tight lower bounds for all approximation factors, thus resolving the main open problem from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.

关键词： streaming algorithms communication complexity longest increasing subsequence direct sum problem

来源：评论

学校读者我要写书评

暂无评论

Multipass streaming algorithms for Regularized Submodular Maximization

引用

Tsinghua Science and Technology 2024年第1期29卷 76-85页

作者： Qinqin Gong Suixiang Gao Fengmin Wang Ruiqi Yang Beijing Institute for Scientific and Engineering Computing Beijing University of TechnologyBeijing 100124.China School of Mathematical Sciences University of Chinese Academy SciencesBeijing 100049China Beijing Jinghang Research Institute of Computing and Communication Beijing 100074China

In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular *** multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this *** this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in *** propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.

关键词： submodular optimization regularized model streaming algorithms threshold

来源：评论

学校读者我要写书评

暂无评论

Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2024年第4期16卷 1-38页

作者： Arunachalam, Srinivasan Doriguello, Joao f. IBM Corp Yorktown Hts NY 10598 USA Alfred Reny Inst Math Budapest Hungary Natl Univ Singapore Ctr Quantum Technol Singapore Singapore

We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets. In order to do so, we prove a generalization of the powerful 2-uniform convexity inequality for trace norms of Ball, Carlen, Lieb (Inventiones Mathematicae'94). Using our hypercontractive inequality, we present upper and lower bounds for the communication complexity of the Hidden Hypermatching problem defined over large alphabets. We then consider streaming algorithms for approximating the value of Unique Games on a hypergraph with t-size hyperedges. By using our communication lower bound, we show that every streaming algorithm in the adversarial model achieving an (r - pound )-approximation of this value requires Omega( n 1-2 / t ) quantum space, where r is the alphabet size. We next present a lower bound for locally decodable codes (LDC) Z n r -> Z N r over large alphabets with recoverability probability at least 1/r + pound . Using hypercontractivity, we give an exponential lower bound N = 2 Omega(epsilon 4 n/r 4 ) for 2-query (possibly non-linear) LDCs over Z r and using the non-commutative Khintchine inequality we prove an improved lower bound of N = 2 Omega(epsilon 2 n/r 2 ) .

关键词： streaming algorithms locally decodable codes quantum communication complexity hypercontractivity Max-Cut unique games

来源：评论

学校读者我要写书评

暂无评论

Quantum Online streaming algorithms with Logarithmic Memory

引用

INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS 2021年第2期60卷 608-616页

作者： Khadiev, Kamil Khadieva, Aliya Smart Quantum Technol Ltd Kazan Russia Kazan Fed Univ Kazan Russia Univ Latvia Fac Comp Riga Latvia

We consider quantum and classical (deterministic or randomize) streaming online algorithms with respect to competitive ratio. We show that there is a problem that can be solved by a quantum online streaming algorithm better than by classical ones in the case of logarithmic memory. The problem is an online version of the Disjointness problem (Checking weather two sets are disjoint or not).

关键词： Quantum computation Online algorithms Logarithmic space streaming algorithms Online minimization problems OBDD Computational complexity

来源：评论

学校读者我要写书评

暂无评论

A Framework for Adversarially Robust streaming algorithms

引用

JOURNAL OF THE ACM 2022年第2期69卷 1-33页

作者： Ben-Eliezer, Omri Jayaram, Rajesh Woodruff, David P. Yogev, Eylon MIT 77 Massachusetts Ave Cambridge MA 02139 USA Google Res New York NY USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Bar Ilan Univ Ramat Gan Israel Tel Aviv Univ Tel Aviv Israel Harvard Univ Cambridge MA 02138 USA

We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms;on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertiononly model, including distinct elements and more generally F-p-estimation, F-p-heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1 + epsilon)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(log n.1/epsilon) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a non-robust streaming algorithm into a robust one in various scenarios.

关键词： streaming algorithms adversarial model distinct elements robust streaming adaptive inputs

来源：评论

学校读者我要写书评

暂无评论

Exploration with Limited Memory: streaming algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits 2020

Exploration with Limited Memory: Streaming Algorithms for Co...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Assadi, Sepehr Wang, Chen Rutgers Univ New Brunswick Piscataway NJ 08854 USA

ISBN: (纸本)9781450369794

Consider the following abstract coin tossing problem: Given a set of n coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time. Motivated by applications to processing massive datasets, we study the space complexity of solving this problem with optimal number of coin tosses in the streaming model. In this model, the coins are arriving one by one and the algorithm is only allowed to store a limited number of coins at any point - any coin not present in the memory is lost and can no longer be tossed or compared to arriving coins. Prior algorithms for the coin tossing problem with optimal sample complexity are based on iterative elimination of coins which inherently require storing all the coins, leading to memory-inefficient streaming algorithms. We remedy this state-of-affairs by presenting a series of improved streaming algorithms for this problem: we start with a simple algorithm which require storing only O(log n) coins and then iteratively refine it further and further, leading to algorithms with O(log log (n)) memory, O(log*(n)) memory, and finally a one that only stores a single extra coin in memory - the same exact space needed to just store the best coin throughout the stream. Furthermore, we extend our algorithms to the problem of finding the k most biased coins as well as other exploration problems such as finding top-k elements using noisy comparisons or finding an e-best arm in stochastic multi-armed bandits, and obtain efficient streaming algorithms for these problems.

关键词： streaming algorithms Pure Exploration Memory-efficient algorithms Noisy Comparison Multi-Armed Bandits

来源：评论

学校读者我要写书评

暂无评论

A Framework for Adversarially Robust streaming algorithms 20

A Framework for Adversarially Robust Streaming Algorithms

引用

39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Ben-Eliezer, Omri Jayaram, Rajesh Woodruff, David P. Yogev, Eylon Tel Aviv Univ Tel Aviv Israel Carnegie Mellon Univ Pittsburgh PA 15213 USA Boston Univ Boston MA 02215 USA

ISBN: (纸本)9781450371087

We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms;on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertion-only model, including distinct elements and more generally Fp-estimation, Fp-heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1 + e)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(logn, 1/e) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a nonrobust streaming algorithm into a robust one in various scenarios.

关键词： Adversarial robustness streaming algorithms Frequency moments Distinct elements Heavy hitters Databases

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：