Implementation of Combinatorial Algorithms using Optimization Techniques
Journal Title: International Journal of Trend in Scientific Research and Development - Year 2019, Vol 3, Issue 3
Abstract
In theoretical computer science, combinatorial optimization problems are about finding an optimal item from a finite set of objects. Combinatorial optimization is the process of searching for maxima or minima of an unbiased function whose domain is a discrete and large configuration space. It often involves determining the way to efficiently allocate resources used to find solutions to mathematical problems. Applications for combinatorial optimization include determining the optimal way to deliver packages in logistics applications, determining taxis best route to reach a destination address, and determining the best allocation of jobs to people. Some common problems involving combinatorial optimizations are the Knapsack problem, the Job Assignment problem, and the Travelling Salesman problem. This paper proposes three new optimized algorithms for solving three combinatorial optimization problems namely the Knapsack problem, the Job Assignment problem, and the Traveling Salesman respectively. The Knapsack problem is about finding the most valuable subset of items that fit into the knapsack. The Job Assignment problem is about assigning a person to a job with the lowest total cost possible. The Traveling Salesman problem is about finding the shortest tour to a destination city through travelling a given set of cities. Each problem is to be tackled separately. First, the design is proposed, then the pseudo code is created along with analyzing its time complexity. Finally, the algorithm is implemented using a high level programming language. As future work, the proposed algorithms are to be parallelized so that they can execute on multiprocessing environments making their execution time faster and more scalable. by Youssef Bassil "Implementation of Combinatorial Algorithms using Optimization Techniques" Published in International Journal of Trend in Scientific Research and Development (ijtsrd), ISSN: 2456-6470, Volume-3 | Issue-3 , April 2019, URL: https://www.ijtsrd.com/papers/ijtsrd22925.pdf Paper URL: https://www.ijtsrd.com/computer-science/data-processing/22925/implementation-of-combinatorial-algorithms-using-optimization-techniques/youssef-bassil
Evolution of Quantitative Effects of Construction Changes on Labor Productivity, Time and Cost Control Using Building Information Modeling
In spite of the fact that the development business has been advancing for quite a long time and analysts have been looking for imaginative answers for quite a long time, different difficulties actually exist for making t...
Robo Maid Vacuum Cleaner
We live in a world filled with technologies. Robotics is one of the biggest advancements in it. The first digitally operated and programmable robot was invented by George Devol in 1954 and was ultimately called “the Unim...
Study of Mechanical Behavior for Tamarind Shell Powder and Coconut Coir Fiber Epoxy Composite for Aerospace Application
Now-a-days, the natural fibres from renewable natural resources offer the potential to act as a reinforcing material for polymer composites alternative to the use of glass, carbon and other man-made fibres. Among various...
Power Distribution - A Challange
In the course of recent years or thereabouts, India has taken quick walks in the improvement of the power part both regarding upgrading power age and also in making power accessible to broadly disseminated regions of the...
Essays of Francis Bacon: A Moral Perspective
Francis Bacon (1561-1626), the father of English essay, is a central figure in the entire history of English literature in general and in prose of the Jacobean period in particular. Bacons essays are the expression of a...