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

Annual ACM-SIAM Symposium on Discrete algorithms

作者： Mohsen Ghaffari Bernhard Haeupler MIT CMU

ISBN: (纸本)9781611974331

This paper introduces the concept of low-congestion shortcuts for (near-)planar networks, and demonstrates their power by using them to obtain near-optimal distributed algorithms for problems such as Minimum Spanning Tree (MST) or Minimum Cut, in planar networks. Consider a graph G = (V, E) and a partitioning of V into subsets of nodes S_1, ..., S_N, each inducing a connected subgraph G[S_i]. We define an α-congestion shortcut with dilation β to be a set of subgraphs H_1, ..., H_N {is contained in} G, one for each subset S_i, such that 1. For each i ∈ [1, N], the diameter of the subgraph G[S_i] + H_i is at most β. 2. For each edge e ∈ E, the number of subgraphs G[S_i] + H_i containing e is at most α. We prove that any partition of a D-diameter planar graph into individually-connected parts admits an O(D log D)-congestion shortcut with dilation O(DlogD), and we also present a distributed construction of it in O(D) rounds. We moreover prove these parameters to be near-optimal;i.e., there are instances in which, unavoidably, max{α, β} = Ω(D (log D)/(log log D)). Finally, we use low-congestion shortcuts, and their efficient distributed construction, to derive O(D)-round distributed algorithms for MST and Min-Cut, in planar networks. This complexity nearly matches the trivial lower bound of Ω(D). We remark that this is the first result bypassing the well-known Ω(D+{the square root of}n) existential lower bound of general graphs (see Peleg and Rubinovich [FOCS'99];Elkin [STOC'04];and Das Sarma et al. [STOC'11]) in a family of graphs of interest.

关键词： distributed algorithms Shortcuts dividing and cutting machine planar network partitions Planar

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Multirobot Task Assignment With Task Deadline Constraints

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2015年第3期12卷 876-888页

作者： Luo, Lingzhi Chakraborty, Nilanjan Sycara, Katia Carnegie Mellon Univ Sch Comp Sci Inst Robot Pittsburgh PA 15213 USA SUNY Stony Brook Dept Mech Engn Stony Brook NY 11794 USA

We present distributed algorithms for multirobot task assignment where the tasks have to be completed within given deadlines. Each robot has a limited battery life and thus there is an upper limit on the amount of time that it has to perform tasks. Performing each task requires certain amount of time (called the task duration) and each robot can have different payoffs for the tasks. Our problem is to assign the tasks to the robots such that the total payoff is maximized while respecting the task deadline constraints and the robot's battery life constraints. Our problem is NP-hard since a special case of our problem is the classical generalized assignment problem (which is NP-hard). There are no known algorithms (distributed or centralized) for this problem with provably good guarantees of performance. We present a distributed algorithm for solving this problem and prove that our algorithm has an approximation ratio of 2. For the special case of constant task duration we present a distributed algorithm that is provably almost optimal. Our distributed algorithms are polynomial in the number of robots and the number of tasks. We also present simulation results to depict the performance of our algorithms. Note to Practitioners-In this paper, we present provably good multirobot task assignment algorithms, while considering practical constraints like task deadlines and limited battery life of robots. Such constraints are relevant in many applications including parts movement by robots in manufacturing, delivery of goods by unmanned vehicles, and search and rescue operations. Our solution is applicable to a group of heterogeneous robots with different suitability (i.e., payoffs) for different tasks. Our distributed approach is independent of the underlying robot communication network topology, and thus can be applied to a wide range of robot network deployments. Finally, our approach is easy to implement, has low communication requirements, and it is scalable, since its ru

关键词： Auction algorithms distributed algorithms generalized assignment multi-agent coordination multirobot task allocation task deadline

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Resource Allocation in Wireless Mesh Networks

Distributed Algorithms for Resource Allocation in Wireless M...

引用

ICOF 2016;19th International Conference on OFDM and Frequency Domain Techniques

作者： Daniel Horovitz M. Priesler A. Reichman Ariel University Ruppin Academic Center

ISBN: (纸本)9783800742530

A wireless network using a mesh topology is offered as an alternative to a star topology in a dynamic mobile network. A great challenge for a mobile mesh network is the ability to share resources between nodes to allow connectivity throughout the network. As the network is dynamic, it is proposed that the algorithm for resource sharing be distributed and be easily adaptable to changes. This research suggests two distributive algorithms for resource allocation and compares the results to the minimal distribution in one predetermined scenario, and to a in random scenarios. The research assumes the ability to perform frequency and time division, and also suggests a method for resource allocation when using orthogonal subbands.

关键词： Wireless mesh networks Resource allocation distributed management OFDMA Cognitive radio Wireless ad hoc network Resource utilization Wireless mesh networks Mobile ad hoc networks OFDMA management of resources Cognitive radio distributed algorithms distributed management Mesh networks Wireless networks Time division Resource sharing

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Multi-Robot Incident Response Victim Extraction

Distributed Algorithms for Multi-Robot Incident Response Vic...

引用

European Control Conference

作者： Maria Pia Fanti Agostino Marcello Mangini Giovanni Pedroncelli Edward Tunstel Walter Ukovich the Departiment of Electric and Information Engineering Polytechnic of Bari Bari Italy the Department of Engineering and Architecture University of Trieste Trieste Italy the Department of Electric and Information Engineering Polytechnic of Bari Bari Italy the Research and Exploratory Development Department The Johns Hopkins University Applied Physics Laboratory Laurel MD 20723 USA

ISBN: (纸本)9781509025923

This paper addresses the problem of robotic task allocation for incident response. In particular, we propose a solution for the distributed dynamic assignment of ground robots for the extraction of victims within an incident scene. Aerial robots communicate among them in order to assign tasks to the ground robots for victim extraction in the shortest possible time. Aerial robots perform two consecutive distributed algorithms: the first one aims at correctly detecting in a completely cooperative manner the exact positions and criti-cality of the victims of the incident;the second one consists of distributed multi-agent optimizations in order to reach a common assignment of the victims needing to be extracted. Finally, the efficiency of the method is shown by an illustrative example.

关键词： distributed algorithms Multi-Robot Incident Response Victim Extraction

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Content Caching in Mobile Backhaul Networks

Distributed Algorithms for Content Caching in Mobile Backhau...

引用

International Teletraffic Congress, ITC 21

作者： Valentino Pacifici Slađana Jošilo György Dán ACCESS Linnaeus Center Royal Institute of Technology Stockholm Sweden

The growing popularity of mobile multimedia content and the increase of wireless access bitrates are straining backhaul capacity in mobile networks. A cost-effective solution to reduce the strain, enabled by emerging all-IP 4G and 5G mobile backhaul architectures, could be in-network caching of popular content during times of peak demand. In this paper we formulate the problem of content caching in a mobile backhaul as a binary integer programming problem, and we propose a 2- approximation algorithm for the problem. The 2-approximation requires full information about the network topology and the link costs, as well as about the content demands at the different caches, we thus propose two distributed algorithms that are based on limited information on the content demands. We show that the distributed algorithms terminate in a finite number of steps, and we provide analytical results on their approximation ratios. We use simulations to evaluate the proposed algorithms in terms of the achieved approximation ratio and computational complexity on realistic mobile backhaul topologies.

关键词： Mobile communication Topology Network topology distributed algorithms Approximation algorithms Mobile computing Prediction algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for the Operator Placement Problem

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2015年第4期2卷 182-196页

作者： Tziritas, Nikos Loukopoulos, Thanasis Khan, Samee U. Xu, Cheng-Zhong Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Univ Thessaly Dept Comp Sci & Biomed Informat Lamia 35100 Greece North Dakota State Univ Dept Elect & Comp Engn Fargo ND 58102 USA Wayne State Univ Dept Elect & Comp Engn Detroit MI 48202 USA

Operator placement plays a key role in reducing the aggregate network overhead within a wireless sensor network (WSN) to extend battery life and the longevity of the network. Consequently, optimal algorithms for the operator placement problem (OPP) are of paramount importance to WSN performance. Unfortunately, the OPP becomes NP-complete when capacity constraints on the WSN nodes are taken into account. There are many algorithms in the literature that tackle the OPP;however, most of them consider tree-structured query graphs without limitations regarding the operators hosted by the WSN nodes. Therefore, there is a need to propose sophisticated approaches such that the problem is solved in an effective fashion. In this paper, we propose a fully distributed approach that takes into account the WSN node capacity constraints. The proposed approach is thoroughly evaluated through simulations and the results reveal that the proposed approach is superior to several state-of-the-art algorithms, such as DRA, DBA, MCFA, dFNS, and GRAL* found in the literature.

关键词： Agent placement distributed algorithms in-network processing operator placement

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for Finding Local Clusters Using Heat Kernel Pagerank 12th

Distributed Algorithms for Finding Local Clusters Using Heat...

引用

12th International Workshop on algorithms and Models for the Web-Graph (WAW)

作者： Chung, Fan Simpson, Olivia Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

ISBN: (纸本)9783319267845;9783319267838

We consider the problem of computing local clusters in large graphs distributed across nodes in a network using two different models of distributed computation. We give a distributed algorithm that computes a local cluster in time that depends only logarithmically on the size of the graph in the CONGEST model. In particular, when the conductance of the optimal local cluster is known, the algorithm runs in time entirely independent of the size of the graph and depends only on error bounds for approximation. We also show that the local cluster problem can be computed in the k-machine distributed model in sublinear time. The speedup of our local cluster algorithms is mainly due to the use of our distributed algorithm for heat kernel pagerank.

关键词： distributed algorithms Local cluster Sparse cut Heat kernel pagerank Heat kernel Random walk

来源：评论

学校读者我要写书评

暂无评论

A Refinement-Based Approach for Proving distributed algorithms on Evolving Graphs

A Refinement-Based Approach for Proving Distributed Algorith...

引用

IEEE International Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises (WET ICE)

作者： Faten Fakhfakh Mohamed Tounsi Ahmed Hadj Kacem Mohamed Mosbah ReD CAD Laboratory University of Sfax FSEGS Tunisia LaBRI Laboratory University of Bordeaux France

Proving the correctness of distributed algorithms in dynamic networks is a hard task due to the time complexity and the highly dynamic behavior. In the literature, the existing solutions lack a consensus about their developments and their proofs. Moreover, the proofs which have been presented are done manually. In this paper, we propose a reuse based approach for specifying and proving distributed algorithms in dynamic networks. It consists in developing a formal pattern using Event-B method, based on refinement techniques. The proposed pattern allows to handle topological events in dynamic networks and to characterize the concept of time. Our solution relies on evolving graphs as a powerful model to record the evolution of a network topology. To illustrate it, we present an example of a distributed counting algorithm. The proof statistics related to the development of the pattern and the algorithm show the efficiency of our solution.

关键词： distributed algorithms Heuristic algorithms Context Vehicle dynamics Network topology Concrete Time complexity

来源：评论

学校读者我要写书评

暂无评论

Stochastic communication-efficient distributed algorithms for solving linear algebraic equations

Stochastic communication-efficient distributed algorithms fo...

引用

IEEE Conference on Control Technology and Applications (CCTA)

作者： Xiaobin Gao Ji Liu Tamer Başar Coordinated Science Laboratory University of Illinois at Urbana-Champaign Urbana IL

In this paper, we propose two stochastic distributed algorithms for solving linear algebraic equations in the form of Ax = b among a network of m > 1 agents. Each agent knows only a subset of the rows of the partitioned matrix [A b]. Each agent recursively updates its estimate of a solution based on the messages received only from its neighbors. The neighbor relationships among the agents are captured by a directed graph whose vertices correspond to agents and whose arcs characterize neighbor relationships. To reduce the communication load and the memory used, each agent partitions its vector of estimate into multiple blocks, and randomly chooses and broadcasts one block at each iteration. Under some technical conditions, we show that for any linear equation admitting a unique solution and any strongly connected neighbor graph, all agents are almost surely able to compute ultimately the unique solution to the linear equation by applying the proposed algorithms.

关键词： Partitioning algorithms distributed algorithms Symmetric matrices Manganese Random variables Convex functions Memory management

来源：评论

学校读者我要写书评

暂无评论

A Tutorial on distributed Optimization for Cooperative Robotics: From Setups and algorithms to Toolboxes and Research Directions

引用

PROCEEDINGS OF THE IEEE 2025年第1期113卷 40-65页

作者： Testa, Andrea Carnevale, Guido Notarstefano, Giuseppe Univ Bologna Dept Elect Elect & Informat Engn I-40136 Bologna Italy

Several interesting problems in multirobot systems can be cast in the framework of distributed optimization. Examples include multirobot task allocation, vehicle routing, target protection, and surveillance. While the theoretical analysis of distributed optimization algorithms has received significant attention, its application to cooperative robotics has not been investigated in detail. In this article, we show how notable scenarios in cooperative robotics can be addressed by suitable distributed optimization setups. Specifically, after a brief introduction on the widely investigated consensus optimization (most suited for data analytics) and on the partition-based setup (matching the graph structure in the optimization), we focus on two distributed settings modeling several scenarios in cooperative robotics, i.e., the so-called constraint-coupled and aggregative optimization frameworks. For each one, we consider use-case applications, and we discuss tailored distributed algorithms with their convergence properties. Then, we revise state-of-the-art toolboxes allowing for the implementation of distributed schemes on real networks of robots without central coordinators. For each use case, we discuss its implementation in these toolboxes and provide simulations and real experiments on networks of heterogeneous robots.

关键词： Optimization Robots Multi-robot systems Robot kinematics Surveillance Resource management distributed algorithms Tutorials Formation control Vehicle routing Cooperating robots distributed optimization distributed robot systems optimization and optimal control

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：