This note presents a more efficient algorithm for finding the largest element in a circular list of processors when messages can be passed in either direction. It passes 2N*floor(lg N) + 3N messages in the worst case,...
详细信息
This note presents a more efficient algorithm for finding the largest element in a circular list of processors when messages can be passed in either direction. It passes 2N*floor(lg N) + 3N messages in the worst case, compared to Chang and Roberts' N(N + 1)/2 and Hirschberg and Sinclair's 8N + 8*ceiling(N lg N) messages. The technique is a selective elimination of possible processes, which then merely relay future messages between the remaining contenders.
This paper mainly presents a concept, framework and decentralized algorithms for a vehicle-based centralized/decentralized hybrid route guidance system. In the hybrid route guidance, the vehicle senses, transmits and ...
详细信息
ISBN:
(纸本)9787900719706
This paper mainly presents a concept, framework and decentralized algorithms for a vehicle-based centralized/decentralized hybrid route guidance system. In the hybrid route guidance, the vehicle senses, transmits and receives network real-time traffic information, and acts as a computer and user of guidance. A hybrid framework was presented, in which guidance information is computed in the predictive, centralized sub-system using special traffic information and model, and revised in a decentralized vehicle-level sub-system taking into account real-time, local data.
Emergency Response Management (ERM) is a critical problem faced by communities across the globe. Despite this, it is common for ERM systems to follow myopic decision policies in the real world. Principled approaches t...
详细信息
ISBN:
(纸本)9781450375184
Emergency Response Management (ERM) is a critical problem faced by communities across the globe. Despite this, it is common for ERM systems to follow myopic decision policies in the real world. Principled approaches to aid ERM decision-making under uncertainty have been explored but have failed to be accepted into real systems. We identify a key issue impeding their adoption --- algorithmic approaches to emergency response focus on reactive, post-incident dispatching actions, i.e. optimally dispatching a responder after incidents occur. However, the critical nature of emergency response dictates that when an incident occurs, first responders always dispatch the closest available responder to the incident. We argue that the crucial period of planning for ERM systems is not post-incident, but between incidents. This is not a trivial planning problem --- a major challenge with dynamically balancing the spatial distribution of responders is the complexity of the problem. An orthogonal problem in ERM systems is planning under limited communication, which is particularly important in disaster scenarios that affect communication networks. We address both problems by proposing two partially decentralized multi-agent planning algorithms that utilize heuristics and exploit the structure of the dispatch problem. We evaluate our proposed approach using real-world data, and find that in several contexts, dynamic re-balancing the spatial distribution of emergency responders reduces both the average response time as well as its variance.
Inter-cell Interference Coordination (ICIC) is one of the key technologies in the multi-cell radio resource management. With radio access networks in LTE/LTE-Advanced more heterogeneous and .at, decentralized ICIC alg...
详细信息
Inter-cell Interference Coordination (ICIC) is one of the key technologies in the multi-cell radio resource management. With radio access networks in LTE/LTE-Advanced more heterogeneous and .at, decentralized ICIC algorithms are more adaptable than centralized algorithms. This paper presents a decentralized subcarrier collision arbitrating algorithm among adjacent cells, which is proved to be distributed and collisionfree. Based on this algorithm, we propose an ideal synchronous ICIC method and a more practical asynchronous ICIC method, which utilize the information exchange capability among adjacent cells provided by the new systems. The simulation results show that this scheme can allocate subcarriers among adjacent cells in a distributed manner, and it is fair and adaptive to traf.c loads. The target of interference coordination is achieved, and a good spatial multiplexing *** can be attained.
This paper investigates the behavior of the Min-Sum message passing scheme to solve systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. Voltage and flow problems involve the ...
详细信息
This paper investigates the behavior of the Min-Sum message passing scheme to solve systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. Voltage and flow problems involve the minimization of quadratic functions and are fundamental primitives that arise in several domains. algorithms that have been proposed are typically centralized and involve multiple graph-theoretic constructions or sampling mechanisms that make them difficult to implement and analyze. On the other hand, message passing routines are distributed, simple, and easy to implement. In this paper we establish a framework to analyze Min-Sum to solve voltage and flow problems. We characterize the error committed by the algorithm on general weighted graphs in terms of hitting times of random walks defined on the computation trees that support the operations of the algorithms with time. For d-regular graphs with equal weights, we show that the convergence of the algorithms is controlled by the total variation distance between the distributions of non-backtracking random walks defined on the original graph that start from neighboring nodes. The framework that we introduce extends the analysis of Min-Sum to settings where the contraction arguments previously considered in the literature (based on the assumption of walk summability or scaled diagonal dominance) can not be used, possibly in the presence of constraints.
暂无评论