China
Africa
Explore chapters and articles related to this topic
Signature Generation Algorithms for Polymorphic Worms
Published in Mohssen Mohammed, Al-Sakib Khan Pathan, Automatic Defense Against Zero-day Polymorphic Worms in Communication Networks, 2016
Mohssen Mohammed, Al-Sakib Khan Pathan
Overlapping subproblems mean that the space of subproblems must be small; that is, any recursive algorithm solving the problem should solve the same subproblems repeatedly, rather than generating new subproblems. For example, let us consider the recursive formulation for generating the Fibonacci series: Fi = Fi-1 + Fi-2, with base case F1 = F2 = 1. Then, F43 = F42 + F41, and F42 = F41 + F40. Now, F41 is being solved in the recursive subtrees of both F43 and F42. Even though the total number of subproblems is actually small (only 43 of them), we end up solving the same problems repeatedly if we adopt a naive recursive solution such as this. Dynamic programming takes account of this fact and solves each subproblem only once. It should be noted here that the subproblems must be only slightly smaller (typically taken to mean a constant additive factor) than the larger problem; when they are a multiplicative factor smaller, the problem is no longer classified as dynamic programming.
Basic Algorithmic Techniques
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
Vishal Khandelwal, Ankur Srivastava
Although the Fibonacci example is not an optimization problem, it illustrates the concept behind DP quite well. DP is essentially a divide-and-conquer approach in which larger complex problems are subdivided in simpler subproblems. The existence of the optimal substructure property ensures that optimality of the overall problem will be maintained. Furthermore, overlapping subproblems could be stored in memory (memoization) for improving the runtime complexity of the algorithm. DP-based approaches for a given problem could be developed as follows: Express the overall problem in the form of subproblems.Investigate if the optimal substructure property holds.Investigate the existence of overlapping subproblems.Develop a memoization-based approach in which the solutions to overlapping subproblems are stored in memory, hence improving the computational complexity.
Resilient healthcare network for simultaneous product allocations during supply chain disruptions
Published in Supply Chain Forum: An International Journal, 2023
Pratik Maheshwari, Sachin S. Kamble, Amine Belhadi, Shivam Gupta, Sachin Kumar Mangla
In their study, Ensafian et al. (2023) argue that the preference for a suitable solution mainly influences optimising the objective function (such as distance, minimising cost, and time) and discovering the most satisfactory solution for the SPD. Koç, Laporte, and Tükenmez (2020) performed a comprehensive review of various SPD solution approaches in light of this. They suggested that optimal SPD techniques should be competent in streamlining complex problems into smaller subproblems and optimising them, which makes such strategies valuable for effectively handling SPD challenges and assessing aspects such as scalability, flexibility, and time complexity. In this paper, Table 3 resembles the characteristics of different solution approaches, including ALR, MTC, MTD, NLGSM, NPSO, TSP, BM, CPA, DP, EM, MBA, MHA, and TWC. However, Vincent et al. (2023) and Koç, Laporte, and Tükenmez (2020) emphasise that DP offers a unique approach to problem-solving such as optimal substructure, overlapping subproblems, recursion or iteration, state representation, optimal value function, memoization or tabulation, time-sensitive decisions, and space complexity. Recently, COVID-19 has brought new constraints and considerations, such as social distancing, sanitisation protocols, restricted areas, and varying demand patterns. Therefore, DP allows for incorporating these changing constraints and adapting the pickup and delivery plans accordingly; meanwhile, it can dynamically adjust routes, consider alternative pickup or delivery points, and optimise the overall plan to meet evolving requirements. Therefore, this approach often gives it an edge over other methods, especially in the context of SPD.