Faculty Publications

Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736

Publications by NITK Faculty

Browse

Subject: search.filters.subject.Approximation algorithms

Search Results

Now showing 1 - 4 of 4
  • No Thumbnail Available
    Item
    Stochastic dynamic programming model for optimal resource allocation in vehicular ad hoc networks
    (Springer India, 2018) Bhuvaneswari, M.; Paramasivan, B.; Kandasamy, A.
    Vehicular ad hoc network (VANET) is an emerging trend where vehicles communicate with each other and possibly with a roadside unit to assist various applications like monitoring, managing and optimizing the transportation system. Collaboration among vehicles is significant in VANET. Resource constraint is one of the great challenges of VANETs. Because of the absence of centralized management, there is pitfall in optimal resource allocation, which leads to ineffective routing. Effective reliable routing is quite essential to achieve intelligent transportation. Stochastic dynamic programming is currently employed as a tool to analyse, develop and solve network resource constraint and allocation issues of resources in VANET. We have considered this work as a geographical-angular-zone-based two-phase dynamic resource allocation problem with a homogeneous resource class. This work uses a stochastic dynamic programming algorithm based on relaxed approximation to generate optimal resource allocation strategies over time in response to past task completion status history. The second phase resource allocation uses the observed outcome of the first phase task completion to provide optimal viability in resulting decisions. The proposed work will be further extended for the scenario that deals with heterogeneous resource class. Simulation results show that the proposed scheme works significantly well for the problems with identical resources. © 2018, Indian Academy of Sciences.
  • No Thumbnail Available
    Item
    Influence maximisation in social networks
    (Inderscience Publishers, 2019) Tejaswi, V.; Bindu, P.V.; Santhi Thilagam, P.S.
    Influence maximisation is one of the significant research areas in social network analysis. It helps in identifying influential entities from social networks that can be used in marketing, election campaigns, outbreak detection and so on. Influence maximisation deals with the problem of finding a subset of nodes called seeds in the social network such that these nodes will eventually spread maximum influence in the network. This is an NP-hard problem. The aim of this paper is to provide a complete understanding of the influence maximisation problem. This paper focuses on providing an overview on the influence maximisation problem, and covers three major aspects: 1) different types of inputs required; 2) influence propagation models that map the spread of influence in the network; 3) the approximation algorithms proposed for seed set selection. In addition, we provide the state of the art and describe the open problems in this domain. © 2019 Inderscience Enterprises Ltd.
  • No Thumbnail Available
    Item
    Approximation algorithm for receiver interference problem in dual power Wireless Sensor Networks
    (Springer Verlag service@springer.de, 2019) Shetty D, D.; Lakshmi, M.P.
    The problem of assigning power levels to the nodes of a wireless sensor network from a given a set of two power levels is called Dual power management problem and the underlying network is called Dual power network. We consider the problem of minimizing the maximum receiver interference of such a network. The interference disrupts the communication and forces the data packets to be retransmitted. The motivation is to conserve the energy by minimizing the interference and maintaining the connectivity of the dual power network. Receiver interference problem is proved to be NP-hard. In this paper, an approximation algorithm is derived for minimizing the maximum receiver interference of a dual power network by utilizing the approximation algorithm for Dual Power Management Problem. The proposed algorithm is supported by the simulation results. We term this problem as Dual Power Receiver Interference Problem and show that it is NP-complete using a polynomial time reduction from Degree Constrained Minimum Spanning Tree problem. We also prove the NP-completeness of Dual Power Management Problem by a polynomial reduction from Vertex Cover Problem. © 2019, Korean Society for Computational and Applied Mathematics.
  • No Thumbnail Available
    Item
    Robust transmission using channel encoding towards 5G New Radio: A telemetry approach
    (Elsevier Ltd, 2021) Sharma, V.; Arya, R.K.; Kumar, S.
    This paper presents a robust channel encoding scheme under adaptive modulation and coding for a massive machine type communication device in 5G new radio. For the very first time, mode-selection and distance statistics algorithms have been simultaneously evaluated, in which together it provides the closest approximation of efficient adaptive modulation and coding with robust transmission. The prediction of optimum adaptive modulation and coding is based on the analysis of uplink packet using distance statistics, and downlink packet using mode-selection mechanism. The performance of 5G new radio by incorporating OFDM subcarrier has been evaluated using analytical as well as simulation approach. Mode-selection algorithm has been considered to predict the environmental condition under a fading channel while the distance statistics provide feedback of the previously transmitted channel condition. The result of both the approaches provide a better bit error rate for adaptive modulation & coding profile under 1/4, 1/18, 1/16 and 1/32 cyclic prefix. © 2021