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

local computation algorithms for Graphs of Non-constant Degrees

ALGORITHMICA 2017年第4期77卷 971-994页

作者： Levi, Reut Rubinfeld, Ronitt Yodpinyanee, Anak Ecole Normale Super Paris France Univ Paris Diderot Paris France MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel

In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. Instead, we consider the case where parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence on d, while maintaining polylogarithmic dependence on n. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in d and polylogarithmic in n;for constant , a randomized LCA that provides a -approximation to maximum matching with high probability, whose time and space complexities are polynomial in d and polylogarithmic in n.

关键词： local computation algorithms Randomized algorithms Maximal independent set Maximum matching

来源：评论

学校读者我要写书评

暂无评论

New techniques and tighter bounds for local computation algorithms

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2016年第7期82卷 1180-1200页

作者： Reingold, Omer Vardi, Shai Samsung Res Amer Mountain View CA USA Weizmann Inst Sci Rehovot Israel Tel Aviv Univ IL-69978 Tel Aviv Israel

Given an input x and a search problem F, local computation algorithms (LCAs) implement access to specified locations of y in a legal output y is an element of F (x), using polylogarithmic time and space. Parnas and Ron [27] and Mansour et al. [19] showed how to convert certain distributed and online algorithms to LCAs, respectively. In this work, we expand on those lines of work and develop new techniques for designing LCAs and bounding their space and time complexity. (C) 2016 Elsevier Inc. All rights reserved.

关键词： local computation algorithms Sublinear algorithms Pseudorandomness

来源：评论

学校读者我要写书评

暂无评论

Constant-Time local computation algorithms

引用

THEORY OF COMPUTING SYSTEMS 2018年第2期62卷 249-267页

作者： Mansour, Yishay Patt-Shamir, Boaz Vardi, Shai Tel Aviv Univ Tel Aviv Israel Microsoft Res Tel Aviv Israel CALTECH Pasadena CA 91125 USA

local computation algorithms (LCAs) produce small parts of a single (possibly approximate) solution to a given search problem using time and space sublinear in the size of the input. In this work we present LCAs whose time complexity (and usually also space complexity) is independent of the input size. Specifically, we give (1) a (1 - oee-)-approximation LCA to the maximum weight acyclic edge set, (2) LCAs for approximating multicut and integer multicommodity flow on trees, and (3) a local reduction of weighted matching to any unweighted matching LCA, such that the running time of the weighted matching LCA is d times (where d is the maximal degree) the running time of the unweighted matching LCA, (and therefore independent of the edge weight function).

关键词： local computation algorithms Sublinear algorithms Approximation algorithms Maximal weight forest

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: local computation algorithms for Graphs of Non-Constant Degrees 27

Brief Announcement: Local Computation Algorithms for Graphs ...

引用

27th ACM symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Levi, Reut Rubinfeld, Ronitt Yodpinyanee, Anak Ecole Normale Super Paris France Univ Paris Diderot Paris France MIT CSAIL Cambridge MA 02139 USA Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel

ISBN: (纸本)9781450335881

In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. This key aspect of LCAs generalizes various other models such as parallel algorithms, local filters and reconstructors. For graph problems, design techniques for LCAs and distributed algorithms are closely related and have been proven useful in each other's context. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. We consider the case where the parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence on d, while maintaining polylogarithmic dependence on n. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasipolynomial in d and polylogarithmic in n;for constant epsilon > 0, a randomized LCA that provides a (1- epsilon)-approximation to maximum matching with high probability, whose time and space complexities are polynomial in d and polylogarithmic in n.

关键词： local computation algorithms Maximal Independent Set Maximum Matching

来源：评论

学校读者我要写书评

暂无评论

Simple local computation algorithms for the General Lovasz local Lemma 20

Simple Local Computation Algorithms for the General Lovasz L...

引用

32nd ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Achlioptas, Dimitris Gouleakis, Themis Iliopoulos, Fotis Natl & Kapodistrian Univ Athens Athens Greece Max Planck Inst Informat Berlin Germany Inst Adv Study Bengaluru India

ISBN: (纸本)9781450369350

We consider the task of designing local computation algorithms (LCA) for applications of the Lovasz local Lemma (LLL). LCA is a class of sublinear algorithms proposed by Rubinfeld et al. [38] that have received a lot of attention in recent years. The LLL is an existential, sufficient condition for a collection of sets to have non-empty intersection (in applications, often, each set comprises all objects having a certain property). The ground-breaking algorithm of Moser and Tardos [34] made the LLL fully constructive, following earlier results by Beck [7] and Alon [5] giving algorithms under significantly stronger LLL-like conditions. LCAs under those stronger conditions were given in [38], where it was asked if the Moser-Tardos algorithm can be used to design LCAs under the standard LLL condition. The main contribution of this paper is to answer this question affirmatively. In fact, our techniques yield LCAs for settings beyond the standard LLL condition.

关键词： Lovasz local Lemma local computation algorithms

来源：评论

学校读者我要写书评

暂无评论

local computation algorithms for Graphs of Non-Constant Degrees 15

Local Computation Algorithms for Graphs of Non-Constant Degr...

引用

Proceedings of the 27th ACM symposium on Parallelism in algorithms and Architectures

作者： Reut Levi Ronitt Rubinfeld Anak Yodpinyanee École Normale Supérieure and Université Paris Diderot Paris France CSAIL MIT Cambridge MA USA

ISBN: (纸本)9781450335881

In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. This key aspect of LCAs generalizes various other models such as parallel algorithms, local filters and reconstructors. For graph problems, design techniques for LCAs and distributed algorithms are closely related and have been proven useful in each other's context. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. We consider the case where the parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence on d, while maintaining polylogarithmic dependence on n. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasi-polynomial in d and polylogarithmic in n; for constant eps > 0, a randomized LCA that provides a (1-ε)-approximation to maximum matching with high probability, whose time and space complexities are polynomial in d and polylogarithmic in n.

关键词： local computation algorithms maximum matching maximal independent set

来源：评论

学校读者我要写书评

暂无评论

The Randomized local computation Complexity of the Lovasz local Lemma 21

The Randomized Local Computation Complexity of the Lovasz Lo...

引用

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

作者： Brandt, Sebastian Grunau, Christoph Rozhon, Vaclav Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450385480

The local computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of one node to determine that node's output. In this paper we show that the randomized LCA complexity of the Lovasz local Lemma (LLL) on constant degree graphs is Omega(log n). The lower bound follows by proving an Q (log n) lower bound for the Sinkless Orientation problem introduced in [Brandt et al. STOC 2016]. This answers a question of [Rosenbaum, Suomela PODC 2020]. Additionally, we show that every randomized LCA algorithm for a locally checkable problem with a probe complexity of o (root log n) can be turned into a deterministic LCA algorithm with a probe complexity of O(log* n). This improves exponentially upon the currently best known speed-up result from o (log log n) to O (log* n) implied by the result of [Chang, Pettie FOCS 2017] in the local model. Finally, we show that for every fixed constant c >= 2, the deterministic VOLUME complexity of c-coloring a bounded degree tree is Theta (n), where the VOLUME model is a close relative of the LCA model that was recently introduced by [Rosenbaum, Suomela PODC 2020].

关键词： local computation algorithms Lovasz local Lemma VOLUME Model Gap Result

来源：评论

学校读者我要写书评

暂无评论

local computation of Maximal Independent Set 63

Local Computation of Maximal Independent Set

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Ghaffari, Mohsen MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781665455190

We present a randomized local computation Algorithm (LCA) with query complexity poly(Delta) center dot log n for the Maximal Independent Set (MIS) problem. That is, the algorithm determines whether each node is in the computed MIS or not using poly(Delta) center dot log n queries to the adjacency lists of the graph, with high probability, and this can be done for different nodes simultaneously and independently. Here Delta and n denote the maximum degree and the number of nodes. This algorithm resolves a key open problem in the study of local computations and sublinear algorithms (attributed to Rubinfeld).

关键词： sublinear algorithms local computation algorithms maximal independent set

来源：评论

学校读者我要写书评

暂无评论

local computation Mechanism Design

引用

ACM Transactions on Economics and computation 2016年第4期4卷 1–24页

作者： Avinatan Hassidim Yishay Mansour Shai Vardi Bar Ilan University Ramat Gan Israel Tel Aviv University Ramat Aviv Israel

We introduce the notion of local computation mechanism design—designing game-theoretic mechanisms that run in polylogarithmic time and space. local computation mechanisms reply to each query in polylogarithmic time and space, and the replies to different queries are consistent with the same global feasible solution. When the mechanism employs payments, the computation of the payments is also done in polylogarithmic time and space. Furthermore, the mechanism needs to maintain incentive compatibility with respect to the allocation and *** present local computation mechanisms for two classical game-theoretical problems: stable matching and job scheduling. For stable matching, some of our techniques may have implications to the global (non-LCA (local computation Algorithm)) setting. Specifically, we show that when the men’s preference lists are bounded, we can achieve an arbitrarily good approximation to the stable matching within a fixed number of iterations of the Gale-Shapley algorithm.

关键词： local computation algorithms mechanism design stable matching

来源：评论

学校读者我要写书评

暂无评论

New Partitioning Techniques and Faster algorithms for Approximate Interval Scheduling

引用

ALGORITHMICA 2024年第9期86卷 2997-3026页

作者： Compton, Spencer Mitrovic, Slobodan Rubinfeld, Ronitt Stanford Univ Comp Sci Dept 353 Jane Stanford Way Stanford CA 94305 USA Univ Calif Davis Comp Sci Dept Kemper Hall Davis CA 95616 USA MIT CSAIL 32 Vassar St Cambridge MA 02139 USA

Interval scheduling is a basic algorithmic problem and a classical task in combinatorial optimization. We develop techniques for partitioning and grouping jobs based on their starting/ending times, enabling us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in a dynamic setting produces several new results. For (1+epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1+\varepsilon )$$\end{document}-approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with O(logn epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\nicefrac {\log {n}}{\varepsilon })$$\end{document} update and O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log {n})$$\end{document} query worst-case time. Our techniques are also applicable in a setting where jobs have weights. We design a fully dynamic deterministic algorithm whose worst-case update and query times are poly(logn,1 epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {poly} (\log n,\frac{1}{\varepsilon })$$\end{document}. This is the first algorithm that maintains a (1+epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath

关键词： Interval scheduling Job scheduling Dynamic algorithms local computation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：