Average Case Analysis of the MST-heuristic for the Power Assignment Problem: Special Cases
Journal Title: EAI Endorsed Transactions on Energy Web - Year 2016, Vol 3, Issue 10
Abstract
We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst-case approximation ratio of this heuristic is 2. We have the following results: (a) In the one-dimension-al case, with uniform [0, 1]-distributed distances, the expected approximation ratio is bounded above by $2 - 2/(\myp+2)$, where $\myp$ denotes the distance power gradient. (b) For the complete graph, with uniform [0, 1] distributed edge weights, the expected approximation ratio is bounded above by 2 − 1 / 2ζ(3), where ζ denotes the Riemann zeta function.
Authors and Affiliations
Maurits de Graaf, Richard Boucherie, Johann Hurink, Jan-Kees van Ommeren
Keywords
Related Articles
- EP ID EP45158
- DOI http://dx.doi.org/10.4108/eai.14-12-2015.2262699
- Views 231
- Downloads 0
Non-Recurring Improved Random Number Generator- a new step to improve cryptographic algorithms
The world is now behind technology transforming every terminology in daily life, like banking, cash, paper, shopping, communication and so on into, e-world terminologies. In this fast growing e-world efficiency of crypto...
BLAST: Battery Lifetime-constrained Adaptation with Selected Target in Mobile Devices
Mobile devices today contain many power hungry subsystems and execute different applications. Standard power management is not aware of the desired battery lifetime and has no visibility into which applications are execu...
Software-Defined Approach for Communication in Autonomous Transportation Systems
Autonomous driving technology offers a promising solution to reduce road accidents, traffic congestion, and fuel consumption. The management of vehicular networks is challenging as it demands mobility, location awareness...
A Survey of Key Negotiation and Authentication Systems in WSNs
Wireless Sensor Networks (WSNs) is a type of adhoc network that is use to sense some phenomena with the help of sensor nodes. The nodes have scarce resources like power, storage, processing power, sensing and communicati...
Comparative Analysis of Machine Learning Algorithms on IVR data
We aim to classify IVR data (Interactive Voice Response) and provide a detailed summary of the methods and techniques we employed to create a classifier model of reasonably high accuracy. This model is built to process l...