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

SIAM JOURNAL ON COMPUTING 2009年第2期39卷 445-460页

作者： Lotker, Zvi Patt-Shamir, Boaz Rosen, Adi Ben Gurion Univ Negev Dept Commun Syst Engn IL-84105 Beer Sheva Israel Tel Aviv Univ Dept Elect Engn IL-69978 Tel Aviv Israel Univ Paris 11 LRI F-91405 Orsay France CNRS F-91405 Orsay France

We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximation distributed algorithm for maximum weighted matching, whose running time is O(log n) for any constant epsilon > 0, where n is the number of nodes in the graph. This is, to the best of our knowledge, the first log-time distributed algorithm that achieves constant approximation for maximum weighted matching on general graphs. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give a distributed algorithm that maintains a (1 + epsilon)-approximation in O(1/epsilon) time for each node insertion or deletion for any constant epsilon > 0. For weighted dynamic graphs we give a constant-factor approximation distributed algorithm that runs in constant time for each insertion or deletion.

关键词： graph algorithms distributed algorithms maximum matching dynamic algorithms distributed approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Answering Conjunctive Queries under Updates 17

Answering Conjunctive Queries under Updates

引用

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

作者： Berkholz, Christoph Keppeler, Jens Schweikardt, Nicole Humboldt Univ Unter Linden 6 D-10099 Berlin Germany

ISBN: (纸本)9781450341981

We consider the task of enumerating and counting answers to k-ary conjunctive queries against relational databases that may be updated by inserting or deleting tuples. We exhibit a new notion of q-hierarchical conjunctive queries and show that these can be maintained efficiently in the following sense. During a linear time preprocessing phase, we can build a data structure that enables constant delay enumeration of the query results;and when the database is updated, we can update the data structure and restart the enumeration phase within constant time. For the special case of self-join free conjunctive queries we obtain a dichotomy: if a query is not q-hierarchical, then query enumeration with sublinear* delay and sublinear update time (and arbitrary preprocessing time) is impossible. For answering Boolean conjunctive queries and for the more general problem of counting the number of solutions of k-ary queries we obtain complete dichotomies: if the query's homomorphic core is q-hierarchical, then size of the the query result can be computed in linear time and maintained with constant update time. Otherwise, the size of the query result cannot be maintained with sublinear update time. All our lower bounds rely on the OMv-conjecture, a conjecture on the hardness of online matrix-vector multiplication that has recently emerged in the field of fine-grained complexity to characterise the hardness of dynamic problems. The lower bound for the counting problem additionally relies on the orthogonal vectors conjecture, which in turn is implied by the strong exponential time hypothesis. *) By sublinear we mean O(n(1-epsilon)) for some epsilon > 0, where n is the size of the active domain of the current database.

关键词： query evaluation constant delay enumeration counting complexity dichotomy dynamic algorithms online matrix-vector multiplication

来源：评论

学校读者我要写书评

暂无评论

Local Mending 1

引用

29th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Balliu, Alkida Hirvonen, Juho Melnyk, Darya Olivetti, Dennis Rybicki, Joel Suomela, Jukka Gran Sasso Sci Inst Laquila Italy Aalto Univ Espoo Finland IST Austria Klosterneuburg Austria

ISBN: (数字)9783031099939

ISBN: (纸本)9783031099939;9783031099922

In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to "patch a hole." We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log* n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Pi can be solved in O(log* n), there is always a restriction. Pi' subset of Pi that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Theta(log n), or Theta(n), while in general graphs the structure is much more diverse.

关键词： Mendability Fault tolerance LCL problems Distributed algorithms Parallel algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Chasing Positive Bodies 64

Chasing Positive Bodies

引用

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

作者： Bhattacharya, Sayan Buchbinder, Niv Levin, Roie Saranurak, Thatchaphol Univ Warwick Dept Comp Sci Warwick England Tel Aviv Univ Dept Stat & Operat Res Tel Aviv Israel Univ Michigan Comp Sci & Engn Div Ann Arbor MI USA

ISBN: (纸本)9798350318944

We study the problem of chasing positive bodies in l(1): given a sequence of bodies K-t = {x(t) is an element of R-+(n) vertical bar C(t)x(t) >= 1, P(t)x(t) <= 1} revealed online, where C-t and P-t are nonnegative matrices, the goal is to (approximately) maintain a point x(t) is an element of K-t such that Sigma(t) parallel to x(t) - x(t-1)parallel to(1) is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching. We give an O(log d)-competitive algorithm for this problem, where d is the maximum row sparsity of any matrix C-t. This bvypasses and improves exponentially over the lower bound of root n known for general convex bodies. Our algorithm is based on iterated information projections, and, in contrast to general convex body chasing algorithms, is entirely memoryless. We also show how to round our solution dynamically to obtain the first fully dynamic algorithms with competitive recourse for all the stated problems above;i.e. their recourse is less than the recourse of every other algorithm on every update sequence, up to polylogarithmic factors. This is a significantly stronger notion than the notion of absolute recourse in the dynamic algorithms literature.

关键词： Convex Body Chasing dynamic algorithms Online algorithms Recourse

来源：评论

学校读者我要写书评

暂无评论

Lattice Data Analytics: The Poset of Irreducibles and the MacNeille Completion 10

Lattice Data Analytics: The Poset of Irreducibles and the Ma...

引用

10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems - Technology and Applications (IDAACS)

作者： Markowsky, George Markowsky, Linda Missouri Sci & Technol POB 1330 Rolla MO 65402 USA Univ Maine Orono ME 04469 USA

ISBN: (纸本)9781728140698

Automated and semi-automated systems that derive actionable information from massive, heterogeneous datasets are essential for many applications. The reasoning of such systems must be as clear as possible in order to earn our trust. Lattices have begun to play a key role in computer science finding applications in distributed computing, programming languages, concurrency theory, and data mining, thereby justifying G. C. Rota's belief that lattice theory will play an important role in 21st Century mathematics [1]. In some instances, researchers must deal with posets that are not necessarily lattices and the question arises how these posets can be embedded in lattices. A classic way to answer this question is to construct the MacNeille completion of the lattice, which is the most compact way to embed a poset into a lattice. In 1973 G. Markowsky introduced the poset of irreducibles construction in his dissertation and demonstrated that this was a very compact way to represent a lattice. In addition, the poset of irreducibles has many of the properties of the poset of join-irreducibles of distributive lattices that was introduced by G. Birkhoff and described in his book [2]. In this paper, we show how to construct the poset of irreducibles for the MacNeille completion of a poset efficiently. We conclude with some applications of these ideas.

关键词： poset of irreducibles lattice data analytics MacNeille completion dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Self-Adapting Scheduling for tasks with dependencies in stochastic environments

Self-Adapting Scheduling for tasks with dependencies in stoc...

引用

IEEE International Conference on Cluster Computing

作者： Riakotakis, I. Ciorba, F. M. Andronikos, T. Papakonstantinou, G. Natl Tech Univ Athens Dept Elect & Comp Engn Comp Syst Lab Zografou Campus GR-15773 Athens Greece

ISBN: (纸本)9781424403271

This paper addresses dynamic load balancing algorithms for non-dedicated heterogeneous clusters of workstations. We propose an algorithm called Self-Adapting Scheduling (SAS), targeted at nested loops with dependencies in a stochastic environment. This means that the load entering the system, not belonging to the parallel application under execution. follows an unpredictable pattern which can be modeled by a stochastic process. SAS takes into account the history of previous timing results and the load patterns in order to make accurate load balancing predictions. We studs, the performance of SAS in comparison with DTSS. We established in previous work that DTSS is the most efficient self-scheduling algorithm for loops with dependencies on heterogeneous clusters. We test our algorithm under the assumption that the interarrival times and life-times of incoming jobs are exponentially-distributed. The experimental results show that SAS significantly outper-forms DTSS especially with rapidly varying loads.

关键词： dynamic algorithms load balancing loops with dependencies stochastic environments

来源：评论

学校读者我要写书评

暂无评论

Decremental Single-Source Reachability in Planar Digraphs 2017

Decremental Single-Source Reachability in Planar Digraphs

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Italiano, Giuseppe F. Karczmarz, Adam Lacki, Jakub Sankowski, Piotr Univ Roma Tor Vergata Rome Italy Univ Warsaw Warsaw Poland Google Res New York NY USA

ISBN: (纸本)9781450345286

In this paper we show a new algorithm for the decremental single-source reachability problem in directed planar graphs. It processes any sequence of edge deletions in O(n log(2) n log log n) total time and explicitly maintains the set of vertices reachable from a fixed source vertex. Hence, if all edges are eventually deleted, the amortized time of processing each edge deletion is only O(log(2) n log log n), which improves upon a previously known O(root n) solution. We also show an algorithm for decremental maintenance of strongly connected components in directed planar graphs with the same total update time. These results constitute the first almost optimal (up to polylogarithmic factors) algorithms for both problems. To the best of our knowledge, these are the first dynamic algorithms with polylogarithmic update times on general directed planar graphs for non-trivial reachability-type problems, for which only polynomial bounds are known in general graphs.

关键词： dynamic algorithms Planar Graphs Reachability

来源：评论

学校读者我要写书评

暂无评论

Load Balancing Techniques in Software-Defined Cloud Computing: an overview 7

Load Balancing Techniques in Software-Defined Cloud Computin...

引用

7th International Conference on Software Defined Systems (SDS)

作者： AlKhatib, Ahmad A. A. Sawalha, Thaer AlZu'bi, Shadi Al Zaytoonah Univ Jordan Comp Informat Syst Dept Amman Jordan

ISBN: (纸本)9781728172194

With the expansion of the network and increasing their users, as well as emerging new technologies, such as cloud computing and big data, managing traditional networks is difficult, where the VM load has increased as well as the required task processing time. Therefore, it is necessary to change the traditional network architecture. Lately, to address this issue, a notion named software-defined network (SDN) has been proposed, which makes network management more conformable. Network resources limitations and requirements fulfilment leads to the important need of load balancing that helps in distributing traffic via several resources to improve network resources efficiency and reliability. Many researchers have worked previously on this task, proposing several algorithms with advantages and disadvantages. This paper focuses on cloud computing load balancing concepts, and represents benefits and some weaknesses regarding to the selected load balancing algorithms and investigates the metrics of their algorithms. In addition, the important challenges of these algorithms have been reviewed to provide future researchers with better load balancing techniques.

关键词： Cloud computing Load Balancing Software-Defined Network Static algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Three techniques for parallel maintenance of a minimum spanning tree under batch of updates

引用

Parallel Processing Letters 1996年第2期6.0卷 213-222页

作者： Ferragina, Paolo Dipartimento di Informatica Università di Pisa Pisa Italy

In this paper we provide three simple techniques to maintain in parallel the minimum spanning tree of an undirected graph under single or batch of edge updates (i.e., insertions and deletions). Our results extend the use of the sparsification data structure to the EREW PRAM model. For proper values of the batch size, our algorithms require less time and work than the best known dynamic parallel algorithms. © World Scientific Publishing Company.

关键词： dynamic algorithms EREW PRAM Minimum spanning tree Sparsification

来源：评论

学校读者我要写书评

暂无评论

Space Efficient Incremental Betweenness Algorithm for Directed Graphs 23rd

Space Efficient Incremental Betweenness Algorithm for Direct...

引用

23rd Iberoamerican Congress on Pattern Recognition (CIARP)

作者： Gil-Pons, Reynaldo CERPAMID Santiago De Cuba Cuba

ISBN: (纸本)9783030134686;9783030134693

Betweenness is one of the most popular centrality measures in the analysis of social networks. Its computation has a high computational cost making it implausible for relatively large networks. The dynamic nature of many social networks opens up the possibility of developing faster algorithms for the dynamic version of the problem. In this work we propose a new incremental algorithm to compute the betweenness centrality of all nodes in directed graphs extracted from social networks. The algorithm uses linear space, making it suitable for large scale applications. Our experimental evaluation on a variety of real-world networks have shown our algorithm is faster than recalculation from scratch and competitive with recent approaches.

关键词： Social network analysis Betweenness centrality dynamic algorithms dynamic graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：