Algorithm Design | Approximation Algorithm | Traveling Salesman Problem with Triangle Inequality

Summary

This video script delves into the Traveling Salesman Problem (TSP), focusing on an approximation algorithm technique using the triangular inequality. It explains the TSP, where a salesman must visit a set of cities and return to the origin, and introduces the concept of Hamiltonian cycles. The script discusses the complexity of TSP, which is part of NP-complete problems, and outlines an approach to simplify the problem using the triangular inequality to create an approximation algorithm. The method involves creating a minimum spanning tree (MST) using Prim's algorithm, then refining the solution by applying the triangular inequality to reduce the cost. The script also covers the theoretical aspect, explaining how the approximation algorithm provides a solution that is at most twice the optimal cost, hence a 2-approximation algorithm. The time complexity of the algorithm is polynomial, making it a feasible approach to solving TSP.

Takeaways

• 🧳 The video discusses the Traveling Salesman Problem (TSP) and its solution using an approximation algorithm based on the triangular inequality.
• 🔍 TSP is a well-known problem in computer science that is part of the NP-complete class, implying that finding an exact solution can be computationally intensive.
• 📚 The approximation algorithm uses the concept of triangular inequality to simplify the problem and make it more approachable in polynomial time.
• 📈 The script introduces the concept of a Hamiltonian cycle, which is a closed loop on a graph that visits each vertex exactly once and returns to the starting vertex.
• 🌐 The algorithm starts by selecting any vertex as a root and then constructs a minimum spanning tree (MST) using Prim's algorithm, which is efficient and suitable for this purpose.
• 📝 The definition of the cost of a cycle in TSP is given as the sum of the costs of all edges within the cycle, and the goal is to minimize this cost.
• 📉 The triangular inequality states that for any three vertices u, v, and w, the direct cost from u to v should be less than or equal to the cost of going from u to w and then w to v.
• 🔄 The script explains that by applying the triangular inequality, the algorithm iteratively removes edges that do not contribute to the optimal solution, thus approximating the TSP.
• 📊 The video references a theorem that the approximation algorithm provides a solution that is at most twice the cost of the optimal solution (2-approximation).
• 🕒 The time complexity of the algorithm is polynomial, specifically O(e log V) or O(V + e log V), where e is the number of edges and V is the number of vertices, making it computationally feasible.

Q & A

What is the Traveling Salesman Problem (TSP)?

The Traveling Salesman Problem (TSP) is an algorithmic problem where a salesman is given a list of cities and must determine the shortest possible route that allows him to visit each city once and return to his original city. It is a well-known problem in the field of combinatorial optimization and is known to be NP-hard.

Why is the TSP considered a part of NP complete or NP hard?

The TSP is considered NP hard because it is a problem whose solutions can be verified in polynomial time, but finding the solution is computationally intensive and requires exponential time in the worst case, making it infeasible to solve for large instances.

What is a Hamiltonian cycle and how is it related to TSP?

A Hamiltonian cycle is a closed loop on a graph where every node (city, in the context of TSP) is visited exactly once. It is related to TSP because the goal of TSP is to find the shortest Hamiltonian cycle that visits all given cities and returns to the starting city.

What is the purpose of using the triangular inequality in the TSP approximation algorithm?

The triangular inequality is used to simplify the problem and make it easier to solve in polynomial time. It helps in creating an approximation algorithm for TSP by ensuring that the direct distance between two points is less than or equal to the sum of the distances through any third point, thus avoiding inefficient routes.

How does the approximation algorithm using triangular inequality work in the context of TSP?

The approximation algorithm starts by selecting any vertex as a root and then creating a minimum spanning tree (MST) from that vertex. After the MST is formed, a Hamiltonian cycle is constructed by visiting each vertex in pre-order and applying the triangular inequality to ensure the shortest paths are chosen, resulting in an approximate solution to the TSP.

What is the significance of the minimum spanning tree (MST) in the approximation algorithm for TSP?

The minimum spanning tree is significant because it connects all the vertices with the minimum possible total edge weight. It serves as a foundation for the approximation algorithm by providing a starting point for constructing a Hamiltonian cycle that aims to be as close to the optimal TSP solution as possible.

What does the term 'full work' refer to in the context of the TSP approximation algorithm?

In the context of the TSP approximation algorithm, 'full work' refers to the process of traversing all the vertices in a pre-ordered manner, effectively creating a cycle that visits each vertex twice. This is used to apply the triangular inequality and find a more optimal path.

What is the meaning of a 'two-approximation algorithm' for TSP?

A 'two-approximation algorithm' for TSP is an algorithm that provides a solution that is at most twice the cost of the optimal solution. It means the algorithm guarantees that the path length it finds will not be more than twice as long as the shortest possible path.

How is the time complexity of Prim's algorithm relevant to the TSP approximation algorithm?

The time complexity of Prim's algorithm, which is used to create the minimum spanning tree in the TSP approximation algorithm, is relevant because it indicates the efficiency of the algorithm. Prim's algorithm has a time complexity of O(E log V) or O(V^2), making it a polynomial time algorithm suitable for the approximation approach.

What are the naming conventions used for different components of the TSP approximation algorithm as described in the script?

The naming conventions used in the script are as follows: 'H*' denotes the optimal tour, 'CT' represents the cost of the minimum spanning tree, 'CW' is the cost of the full work, and 'CH' represents the approximate cost of the Hamiltonian cycle obtained after applying the triangular inequality.

Outlines

00:00

🧳 Introduction to the Traveling Salesman Problem and Approximation Algorithm

The video introduces the Traveling Salesman Problem (TSP), a classic algorithmic problem in the field of computer science. The speaker discusses using an approximation algorithm to simplify the TSP, which is known to be NP-hard. The approximation algorithm leverages the triangular inequality to find a solution in polynomial time. The concept of a Hamiltonian cycle, a closed loop that visits each vertex once and returns to the origin, is also explained as fundamental to solving the TSP.

05:02

📏 Applying Triangular Inequality in Approximation Algorithms

This paragraph delves into the specifics of using the triangular inequality to create an approximation algorithm for the TSP. The triangular inequality principle is explained, where the direct distance between two points (U to V) is compared with the sum of the distances via an intermediary point (U to W and W to V). The algorithm selects the shorter path, which aids in finding a near-optimal solution for the TSP. The paragraph also references Cormen's 'Introduction to Algorithms' as a resource for further understanding.

10:03

🌳 Constructing a Minimum Spanning Tree for TSP Approximation

The speaker outlines the process of creating a minimum spanning tree (MST) as part of the approximation algorithm for TSP. Starting with an arbitrary vertex as the root, the algorithm extends the tree by adding edges, ensuring the total weight is minimized. Two algorithms for MST, Prim's and Kruskal's, are mentioned, with Prim's algorithm being chosen for its sequential edge addition, which aligns with the step-by-step nature of the approximation process.

15:03

🔄 Full Work and Triangular Inequality in TSP

The concept of 'full work' is introduced, which involves visiting each vertex in a pre-order sequence, effectively creating a cycle. This cycle is then optimized using the triangular inequality to remove less efficient paths, thus improving the approximation's accuracy. The paragraph emphasizes the iterative nature of this process, where the full work is refined to better approximate the optimal TSP solution.

20:04

📊 Theoretical Foundation of the 2-Approximation Algorithm

The video script provides a detailed explanation of the theoretical underpinnings of the 2-approximation algorithm for TSP. It presents mathematical models and proofs to demonstrate that the cost of the approximate solution is at most twice the cost of the optimal solution. The notation used in the script, such as H* for the optimal tour and CT for the minimum spanning tree, helps to formalize the proof and establish the efficiency of the approximation method.

25:05

🔢 Time Complexity and Conclusion of the Approximation Method

The final paragraph wraps up the discussion by emphasizing the polynomial time complexity of the approximation algorithm, which is crucial for its practical application. The speaker mentions the time complexity of Prim's algorithm as O(e log V), where e is the number of edges, and V is the number of vertices. The use of triangular inequality is highlighted as a key factor in achieving this polynomial time complexity, concluding the explanation of the approximation method for the TSP.

Keywords

💡Traveling Salesman Problem (TSP)

The Traveling Salesman Problem (TSP) is a classic algorithmic problem in the field of computer science and operations research. It focuses on finding the shortest possible route for a salesman who needs to visit a set of cities and return to his original city, traveling through each city exactly once. In the video's context, TSP is central to the discussion as the problem for which an approximation algorithm is being developed using the concept of triangular inequality.

💡Approximation Algorithm

An approximation algorithm is a type of algorithm that finds a solution that is close to the optimal solution but does not necessarily guarantee the best possible outcome. In the video, the approximation algorithm is used to simplify the TSP by leveraging the triangular inequality, making it more computationally feasible to solve within polynomial time, which is crucial for NP-hard problems like TSP.

💡Triangular Inequality

Triangular inequality is a principle from geometry stating that the direct distance between two points is always less than or equal to the sum of the distances from those points to a third point. In the script, triangular inequality is used to create an approximation algorithm for TSP, helping to determine the most efficient path by eliminating longer routes that can be replaced by shorter direct paths.

💡NP-Complete

NP-Complete is a complexity class in computer science that includes decision problems which are at least as hard as the hardest problems in NP. The term is used in the script to describe the difficulty of the TSP, indicating that it is a particularly challenging problem to solve optimally due to its computational complexity.

💡Hamiltonian Cycle

A Hamiltonian cycle is a concept from graph theory where a closed loop in a graph visits each vertex exactly once. In the video, the Hamiltonian cycle is integral to understanding TSP, as the goal is to find such a cycle that represents the shortest possible route for the salesman to travel.

💡Minimum Spanning Tree (MST)

A Minimum Spanning Tree is a subset of the edges of a connected, undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. In the script, the creation of an MST is a step in the approximation algorithm for TSP, helping to establish a baseline for the shortest connections between cities.

💡Prim's Algorithm

Prim's Algorithm is a greedy algorithm used to find the minimum spanning tree for a connected, undirected graph. In the video, Prim's Algorithm is specifically mentioned as the method used to create the MST, which is a foundational step in the approximation algorithm for solving TSP.

💡Pre-order Traversal

Pre-order traversal is a tree traversal method where the node is visited before its children, following a specific order: the node itself, then its left subtree, and finally its right subtree. In the script, pre-order traversal is used in the context of constructing the Hamiltonian cycle for the TSP solution.

💡Full Work

In the script, 'full work' seems to refer to the process of visiting each vertex in a way that respects the triangular inequality, ensuring that no unnecessary detours are made. It is a step in the approximation algorithm where all possible routes are considered before applying the triangular inequality to simplify the path.

💡Time Complexity

Time complexity is a measure of how long an algorithm takes in terms of the amount of input. It is often expressed using Big O notation. In the video, the time complexity of Prim's Algorithm, which is used to create the MST, is discussed as being polynomial time, indicating that the approximation algorithm for TSP is efficient and can be solved in a reasonable amount of time.

Highlights

Introduction to the Traveling Salesman Problem (TSP) with triangular inequality using approximation algorithm technique.

Explanation of approximation algorithm and its application to simplify TSP to a polynomial time problem.

TSP's classification as part of NP-complete, highlighting its computational complexity.

Overview of Hamiltonian cycle concept and its relevance to TSP.

Detailed description of the TSP, emphasizing the need to return to the starting city after visiting all others.

Introduction of triangular inequality as a method to create an approximation algorithm for TSP.

Example of applying triangular inequality to choose the most cost-effective path in TSP.

The selection process for any vertex as a starting point in the approximation algorithm.

Creation of a minimum spanning tree (MST) as a step in the approximation algorithm using Prim's algorithm.

Explanation of the list of vertices and their order based on pre-order traversal.

Concept of full work in TSP to ensure all vertices are visited according to triangular inequality.

Process of completing the triangle inequality to approximate the TSP solution.

Real-life example of approximation versus optimal solution in delivery scenarios.

Theorem and proof of the 2-approximation algorithm for TSP using triangular inequality.

Mathematical models and expressions used to prove the approximation algorithm's effectiveness.

Discussion on the time complexity of Prim's algorithm and its polynomial nature.

Final summary of the approximation methodology using triangular inequality for TSP.

Transcripts

hello everyone welcome to edil in this

video we are going to discuss about

traveling salesman problem with

triangular inequality using

approximation algorithm technique okay

the approximation basically we are using

is using triangular unquality how to

find the traveling salesman problem to

be easier towards some polinomial time

how do we expect okay because traveling

salesman is a part of NP complete or

somewh you can find it out in NP hard

also so but in general you can say it

lies between NP hard to NP complete but

maximum uh Network stops I found like

it's a part of NP complete okay so those

who are new kindly watch the previous

videos uh next we'll start with the

traveling salesman problem so your

traveling salesman problem is a problem

through which I must tell you like uh we

have already completed reduction in

detail so Hamilton Cy

we should introduce what is this suppose

you start with uh

vertex I'm just starting with a b c and

d okay suppose this is undirected graph

because in general whenever you say uh

traveling salesman problem so each

Vortex is considered as a CT okay so a

person is going to travel all the city

and when he or she started from a

position he or she should have to come

back to that particular position this is

what the traveling salesman problem is

so why we introduce hamiltonan cycle

this is I'm just repeating but this part

you can the full detail video is there

in reduction you can check that one and

you can understand like how the

traveling salesman is working fine okay

so for we introduced hamiltonan cycle or

hamiltonan circuit you can say suppose

you started from a you can reach B you

can reach C then you can reach D again

you can reach a this is one point or you

can start because though it is

undirectional undirected means it's a

bidirectional okay so you can start with

a to d d to C D to b or you can switch

to uh B to a clear there are two ways

you can definitely start from a and

start end at a also okay so for that

reason we are introducing hamiltonan

cycle okay or Hamilton circuit this is

what we have already discussed now our

main target is then why we use for

approximation the the basic question

okay so uh this is the definition as for

the definition which it is written like

for a suppose you are trying to you you

just converted a cycle like here it is

started and you just trying to convert

that one up to you know you try to count

this a this is what a is okay a cycle is

created now the cost cost if you want to

find out C stands for the cost which is

a sigma because all the uh ages

whichever you have connected like with

certain u and v with the vertices

whatever the edes you have connected or

might be within the cycle you just count

that one or you just some add that one

and this addition of all the cost of

Ages is called as the small that should

be minimum the

minimum it should be minimum okay

then only you can say this is your tsp

okay but this is sometime hard for us to

find out in case of reduction we have

set some rule here it is written and uh

if you are not restricted the tsp

restricted in the sense like if you have

not certain if have not framed any rules

for that one tsp is too hard to find out

okay so in in reduction we said all the

distance should be one then hamiltonian

cycle we run and we get it within a poal

time so this is what exactly we studied

like uh that is what we are trying to

find out the minimum with the problem

exactly what exactly we focused here we

are not keeping all the distance as one

or two or some same distance is not

there here the distance could be

different but we are introducing

triangular or triangle inequality okay

triangle inequality we are using through

which we are creating an approximation

algorithm for tsp to get the optimal

solution for it okay next triangle

inequality means for this example I've

just kept one example here suppose you

want to move from U to V there is one

way another way also this one clear so

how do you pick which one is good for

you like suppose u2v cost u2v means

direct uh you have two options like from

direct you have to check whether it is

less than Cost U to W and cost this cost

and this cost it represents okay so

whether it is equal less than equal to

this one or not if it is less than this

so we will pick UV instead of U to W and

W to V this is what the triangle

inequality if it is more if the distance

is more so definitely we'll pick this

one like U to V we will come and sorry U

to W then W to V we are reaching if you

will find it out by comparing this one

so definitely stop accepting this row

and we will pick this one CLE this is

what a triangle inequality it represents

it uh then using triangle uh inequality

can we reduce or can we give such

approximation algorithm or not that is

our aim and objective here clear so you

can check approximation algorithm we are

going to use so I'll start from this

book I'm following the book uh written

by Corman introduction to algorithm you

can check in the description also the

book and uh the textbook and the

reference book everything I have

mentioned there next uh what text are

select any vertex you this is not always

mandatory no you should start from the

end you can start from the bottom

nothing you you can start any vertex

select any vertex from the vertex given

okay and keep that was a root First Step

Second Step what it says we are just

creating a minimum spanning tree those

who are new kindly watch the full detail

video there in a minimum spinning tree

okay uh so here uh we kept the root R

based on that we created the minimum

sping tree as we have already discussed

whenever we studied the minimum spanning

tree there are two approaches or two

algorithms we discussed one is prims

algorithm other is cuscal algorithm so

here this is a PR algorithm we going to

use so because we are trying to find out

one by one with the ages that's why we

fixed up with the PES algorithm we

detail analysis will be done don't worry

about it first we will uh read each and

every sentence written there because

algorithm is a comprises of the

solutions that's why we first starting

with the solution then we are going

towards the problem

clear next H is a list of vertices what

exactly is our list of vertices you can

say ordered accordingly when they are

first visited in pre-order like whenever

we have already studied to visit a tree

there are three different ways one or

three different order we have studied

earlier in data structure one is

pre-order in order post order there are

three ways pre-order means we initially

we started visiting of the node for the

first first time in order means for the

second time post order means third time

clear we have already discussed in the

data structure video there it is clearly

mentioned so how to complete to the

pre-order first we have completed a

pre-order like H we will completely say

that one and return the hamiltonian

cycle hamiltonian cycle means we will

not repeat the same age again okay we

will say once I'll start with like the

the example I must tell you like we will

start from this end you can start your

movement but you will end up with this

one this is what your hamiltonian cycle

okay like you will definitely end at

this

position wherever you start you will

definitely end you can definitely end it

this position this is Hamilton cycle we

have discuss that that is what the

fourth line says clear so I hope you

understood what exactly it is written

now based on the example there in the

book I'm just going to tell you that one

this a represents this is a graph given

to us with uh you can say the weight are

different but here the weight is not

mentioned in the uh book that's why I'm

not you know adding that one so out of

this we are going to create MST minimum

spanning tree using prims why prims

because you can take uh the help of

crull also not an issue but they have

taken the PES okay so once the PES they

have collected like they started a as a

root from that one they just created an

MST okay next MST is a tree that we have

already discussed this C represents is a

full

work full

work full work means we are going to

just cover all all the vertices why

because we are trying to find out the

triangle inequality suppose you must say

like whether I if I'm coming to C to B

then I'm going towards C to H whether

this H is greater than this is or not if

this is greater than so I must have to

remove that one and I'll select this one

for for triangular inequality for

triangular

inequality or triangle inequality

I'm just writing in short for triangular

inequality we are actually doing the

full work okay next once it is done so

we have completed triangle inequality so

you can say this is your

approximate tsp traveling sales person

or traveling salesman problem

okay this is your approximate so instead

of B2 H C2 B then C2 H clear using

triangle

inequality this is your optimal

optimal or best you can say

tsp mean you know the problem optimal

how do you define in real life you know

that one is it will take at least 2

minutes to cover everything or 2 hours

to cover every CT is so you know that

this is optimal suppose you uh inform a

person to in a real life basically how

you will use that one optimal means the

experience fellow experience fellow

means I have already served the root

everything I know two hours is enough

but sometimes a person is coming I I I

hired him or her for delivery purposes

might be he or she will take like I'll

tell like which one that you should have

to cover first how you will complete

everything I instructed everything but

the new person he see tries to

understand tries to tackle all the paths

within less time might be it's near

optimal I told like 2 hours is enough

might be for him or her it took 3 hours

so this is what a real life example of

approximation with the optimal solution

optimal solution like here what they

said like A2 B then B2 H instead of H2 D

what they started h2f this is the

optimal answer okay which is represented

what format that we will discuss this is

how we have completed how it is working

clear now for the theorem for the

theorem how to prove it just check it in

general uh University type of exams this

type of questions could be come like how

to verify it is two approximation

algorithm clear so it is saying uh

approx tsp t is polom time to

approximation algorithm for traveling

salesman problem using triangle

inequality using triangle inequality we

are getting a two approximation means

two times it means 2

times

more

than

the

optimal value or optimal cost two time

more that that is what it represents two

approximation algorithm that we have

already discussed C

star C by C

star equal to row of n that row

represents two that is what we have

already discussed to

approximation then how to

prove this one try to understand now

clear so here H star denotes optimal

tour we have done the optimal tour H

star represents so this is our H star or

cost of H star you can say which is the

smallest for a timing because this is

our optimal one okay next T represents

the spanning tree which you have

completed for the first time it is

represented in the line two line two

means this one compute minimum spanning

tree whenever we have computed this one

is cost of spanning tree this is what CT

represents clear CT CH

star now for full work we'll decide full

work is represented as W clear so this

one is cost of w is represented as the

total cost or total weight covered by

the full work

okay

next this H represents which is obtained

by deleting the full work deleting the

vertices from the full work represents

the

approximate cost of

H

okay these are just the naming

conventions first we'll try to

understand what it does whenever we say

optimal one optimal is always greater

than the spanning tree why here you can

say whenever you are creating the tree

clear this is for one time one Ed should

be connected if there is a cycle

definitely I must tell you this is not a

Tre this is just a graph so minimum

spanning tree means we are just

converting the graph into tree means we

are trying to remove all the edges which

makes the cycle clear so here in this

example here is a cycle so definitely

what it says so this CH star is

definitely greater than equal to the CT

C might be it is equal but it is should

be always greater why because we can

have a cycle clear when we are creating

the cycle we cannot guarantee about the

cost minimum spanning tree is always

giving us the minimum value but here

whenever we include the cycle we cannot

always guarantee about the minimum cost

or minimum weight that is what we said

this is just one first expression or

mathematical model we designed or

developed which is 35.4 we named that

one clear I hope it is clearly

understood when we start with the full

work full work means we started from a

we are completing B like we are just

doing the pre-ordering which we have

said this one pre-ordering we are just

trying to go for the pre-ordering of the

full work like we started with a then b

c then B then H then again B so I must

write like how we are covering a then B

then C then again

B then H then H to again B then

a then

D then e f again e then G then D then

a clear this is what we are doing in a

full work it is also written there a b c

BH you can say a b c BH clear this is

what ba means this is exactly what I I'm

just writing this one I was just writing

this one it is written in the book this

is what a full work we are doing the

pre-ordering of it

clear like we have done just for what

reason just for find the triangle

inequality for finding triangle

inequality for triangle

inequality that's why we are just

covering all the one whichever is

greatest for us we trying to remove that

one clear

next so for that CW which is our full

work definitely 2 *

we are doing it two times how you can

say for A to B we have covered clear a B

to C we have covered for the first time

now then c2b we are covering again now

this is for one time this is for the

second time so you can say again for B

to H we have covered for one time again

H to B whenever we are coming this is

for the second time clear so whenever

I'm just coming towards this here it is

for the first time here it is for the

second time so indirectly we are just

covering all the paths second time means

this is what it represent CW full

work CW is 2

C to cost of t means the spanning tree

it is two times spanning tree okay the

cost of spanning tree two times we are

covering because of this region A to B

we have covered B to C is the first time

but whenever we coming back clear C2 B

it covers again the same uh AG cost or

the cost or the weight is covering again

that is what it represents

clear next if we equate and we name that

one 35.5 clear if we equate that one so

we will get this result as uh the the

full work which we did is equal to is

less less than equal to the cost of the

optimal answer which which we should get

you can equate that the previous two one

which we equate through that we have

finalized the answer as this clear next

what exactly we going to do we are now

saying whenever we are doing the uh

first visit pre-order pre-order case

what exactly Tells A B C then H then a d

this is what it represents a b c h then

d e FG this is for the pre PR order this

is pre-order that we have completed one

okay so once we have done

it so here you can check that one D

clear once we covered that one with F2 G

then G2 a there is another one like we

are going to the that one but how we

cover a b then B to C then C2 H H2 D D2

e E2 F F2 G this is what it is written

okay this is what we are getting just

deleting such notes which are giving us

maximum results using triangular

inequality or triangle inequality we did

that one the triangle inequality we

applied that one and we got certain

results definitely those results are

less than the full work why because we

are removing from the full work this is

our full work and we removed the full

work we have focused on minimizing that

one so definitely when we focusing on

minimizing that one so it is less than

here it is not we are saying it is two

times definitely we'll get either equal

to sign but that should be less so this

represents this is our optimal this is

our approximate value this is our full

work full work is less than equal to

this one clear whenever you equate uh we

name that one 37

35.7 so whenever you equate 3 5.6 with

35.7 because our Target is two way

approximation how it does like you can

say here CW here CW you just replace the

CW or the two CH there so we got the

value is this one this represents the

approximation value is 2 times greater

than the optimal answer this is what it

says clear so this

says this ISS two approximation clear

two approximation

I'm writing this it to

approximation because CH represents the

cost of approximation and C A Star is

optimal answer the optimal answer is two

times more clear so that's why what is

we what exactly we saying so uh the

answers which we are expecting here is

two times more than the optimal answer

which we are expecting that's why we are

saying it is two approximation algorithm

using triangle inequality clear so two

approximation as we have already told

you like this one C is two times more

than the C star okay that is what it is

written suppose I'm just writing

c 2 * C star this is what we are getting

this result so this is what we are

expecting this c h now to

c h

star clear this is what two *

approximation is so I hope it is clearly

understood by you how we have completed

with the approximation methodology we

have used the approximation indirectly

we said that triangle inequality how it

helps us to get a polom time though we

expecting the polom time here the prims

algorithm we have run so here others are

not exactly much time we expecting for

the prims algorithm PR algorithm we can

say the time complexity is e v log V

also we are saying b of e log V also we

are saying sometimes you can say it is

also r b of V plus e why because we are

just removing e Vortex with the ages

because we started with a Connect One

log V 2 this is what the time complexity

of Pol you know MST Pol PRS algorithm so

that's why we can say that complexity is

this one which is polom that's why

though it's polinomial one for us so we

must say the complexity of the algorithm

is polom so I'm just writing it clearly

time complexity

big of e you can say you can use mod

also not an

issue you can use mode or you cannot use

mode it it's up to you by the way

clear next we

of

uh we of V +

e then log V this also some someone can

write in this order also not an issue

but we must say this is the Pol

polinomial time it is taking but we are

taking the help of triangle inequality

this is what we did with the

approximation so I hope it is clearly

understood by you if any doubt you will

be having please comment below thank you

for having a good day