China
Africa
Explore chapters and articles related to this topic
Polynomial Time Algorithms
Published in Craig A. Tovey, Linear Optimization and Duality, 2020
The major distinction we make between algorithms is whether or not they take polynomial time. Most algorithms that are not polynomial are exponential, requiring more than cdL time in the worst case, for some constants c>1 and d>0. Any exponential function will eventually exceed any polynomial function as L increases. From a theoretical point of view, that is why polynomial time algorithms are preferred to exponential time algorithms. In practice, polynomial time algorithms are usually faster than exponential time algorithms on real cases.
Introduction
Published in A Vasuki, Nature-Inspired Optimization Algorithms, 2020
Optimizing a cost function that is defined on a set of independent variables is a combinatorial optimization problem since it involves finding the right set of independent variables that maximizes or minimizes the function. The problems which generally fall into this category can be divided into two classes – those which are easy to solve and take up less time (can be solved in polynomial time) and those which take up a large amount of time and are practically infeasible to solve, called NP-hard problems. The most famous problem in computer science under the category of NP-hard is the traveling salesman problem (TSP), and other similar problems in this category are the graph partitioning (coloring) problem, job scheduling problem, and network routing problem, to name a few. These combinatorial optimization problems could be solved by the classical optimization algorithms in an infinitely long time or by the heuristic/metaheuristic optimization algorithms in finite short time that produces an optimum solution that closely approximates the actual solution.
Mathematical Background
Published in Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 2018
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
Roughly speaking, polynomial-time algorithms can be equated with good or efficient algorithms, while exponential-time algorithms are considered inefficient. There are, however, some practical situations when this distinction is not appropriate. When considering polynomial-time complexity, the degree of the polynomial is significant. For example, even though an algorithm with a running time of O(nln ln n), n being the input size, is asymptotically slower that an algorithm with a running time of O(n100), the former algorithm may be faster in practice for smaller values of n, especially if the constants hidden by the big-O notation are smaller. Furthermore, in cryptography, average-case complexity is more important than worst-case complexity — a necessary condition for an encryption scheme to be considered secure is that the corresponding cryptanalysis problem is difficult on average (or more precisely, almost always difficult), and not just for some isolated cases.
A novel cloud manufacturing service composition platform enabled by Blockchain technology
Published in International Journal of Production Research, 2020
Ehsan Aghamohammadzadeh, Omid Fatahi Valilai
As discussed in the literature, every instance of the set covering problem which is a well-known NP-hard problem can be transferred into an instance of a simple service composition problem in polynomial time (Geyik, Szymanski, and Zerfos 2013; Jula, Sundararajan, and Othman 2014). Therefore, service composition issues in general categorised into NP-hard problems. NP-hard problems consider being the hardest optimisation issues in combinational problems which to the date, there has been no polynomial-time algorithm capable of solving the problems. In the worst-case scenario, any algorithm which tries to solve NP-hard problems may require exponential run time (Stützle 1998). As a result, by increasing the size of the NP-hard issue, the efficiency of these issues decreases significantly.
Multi-objective quasi oppositional Jaya algorithm to solve multi-objective solid travelling salesman problem with different aspiration level
Published in International Journal of Systems Science: Operations & Logistics, 2023
Aaishwarya Bajaj, Jayesh Dhodiya
The travelling salesman problem (TSP) is the most intensive problem in optimization. TSP has a wide range of applications such as in airline crew scheduling and courier delivery services. In courier services, minimizing time is important because it directly impacts the service and reputation of the companies. Reaching these goals requires a system capable of providing an optimal travel route so that the travel time is minimum. So it needs an application that can optimize the TSP solution. TSP was mathematically formulated in 1930 but became popular after the 1950s. TSP entails travelling to each city from the given list exactly once using the shortest possible route and return to the origin city. It is an NP-hard combinatorial optimization problem described by Liao et al. (2012). The decision version of TSP is an NP-Complete problem. NP-complete means no polynomial algorithm can obtain the best solution, i.e. it can not be reduced to any other polynomial-time problem. Hence, heuristic methods are used to solve this type of problem in a reasonable amount of time as discussed by Feng and Liao (2014). TSP is available in different types such as asymmetric TSP in which the travelling cost from node to is not equal for to . On the other hand, symmetric TSP is when travelling cost from node to is equal to the cost from to . Changdar et al. (2014) describe stochastic TSP which uses probability for the visited vertex to minimise the travelling cost. In time window TSP, every vertex is visited within the indicated window time. In double TSP, two salesmen are appointed to complete the tour, operating simultaneously. These different types of TSP were explored and solved by researchers during the last two decades.
Predicting quality parameters of denim fabrics using developed ANN based Artificial Bee Colony algorithm
Published in The Journal of The Textile Institute, 2023
Gözde Katırcıoğlu, Emel Kızılkaya Aydoğan, Yılmaz Delice, Esra Akgül
However, to the knowledge of the researchers, in the related literature, there is no work dealing with the optimization between quality parameters and production parameters of denim fabric. Actually, this problem is inherently NP (non-deterministic polynomial) hard problem. NP-hard refers to the complexity class of decision problems that we cannot prove to have a solution in polynomial time. These algorithms are expected to have an exponential complexity for their solutions. The solution time that can be spent on solving a problem is an important criterion in the selection of the optimization method to be used (Aaronson, 2005). The optimization issue of training a neural network is NP-hard and has several theoretical and technical drawbacks. Meta-heuristic algorithms can often be used to solve these NP-hard problems (Aydogan et al., 2019; Rojas-Delgado et al., 2019; Toledano-López et al., 2022). A kind of remarkable meta-heuristic algorithm ABC is used to optimize the NP-hard problems but it has not yet been used in the textile field. This algorithm is a powerful technique used for optimization with artificial neural networks in many fields. Evik et al., for instance, created an algorithm based on the fusion of ANN and ABC. The neuron connection weights of the ANN used to estimate power usage throughout time ranges from one hour to one week are optimized using this technique. Yusiong et al. used an ANN classifier trained using the ABC algorithm to solve the tomato ripeness classification problem. Xu et al. (2017) proposed an optimized back-propagation ANN with the ABC algorithm to obtain required voltage for the control of the Magnetorheological (MR) damper. Banharnsakun (2017) proposed a paving surface classification and threat detection system that uses a hybrid of the ABC-ANN algorithms. Paliwal et al. used a neural network-based model and ABC algorithm to predict customer churn in the telecommunications sector. Following, this method was compared with the GA, PSO, and ACO for showing the highest accuracy of ABC trained neural network. Yasen et al. (2017) proposed an NN optimized with the ABC optimization algorithm to predict thunderstorms.