Algorithm Design | Approximation Algorithm | Vertex Cover Problem #algorithm #approximation

Summary

This video delves into the Vex Cover problem, a well-known NP-complete problem, and its solution using approximation algorithms. The presenter explains the concept of Vex Cover and its reduction to the Independent Set problem, highlighting the challenges faced when dealing with NP-complete problems. The focus is on finding the minimum number of vertices required to cover all edges in a graph. The script introduces an approximation algorithm called 'approx Vex Cover G', which iteratively selects edges and removes incident vertices until all edges are covered, aiming for a polynomial time solution that approximates the optimal answer. The video also discusses the time complexity and provides examples to illustrate the algorithm's process and its 2-approximation property, ensuring users understand how the algorithm performs in polynomial time but may yield solutions that are twice the size of the optimal.

Takeaways

• 📚 The video discusses the Vertex Cover problem using approximation algorithms, a methodology for NP-complete problems.
• 🔍 It suggests that for NP-complete problems, there are difficulties in finding polynomial-time solutions, and approximation algorithms offer a way to achieve near-optimal results.
• 🎯 The goal of the Vertex Cover problem is to find the minimum number of vertices that cover all the edges in a graph, which is a part of NP-complete.
• 🤔 The script explains that taking all vertices as a cover is possible but not the minimum solution, which is the focus of the problem.
• 📘 The presenter refers to the Cormen book for the algorithm, indicating that the content is based on established literature.
• 🔧 The 'approxVortexCover G' algorithm is introduced, which iteratively selects an arbitrary edge and adds both vertices to the cover set, then removes all edges connected to these vertices.
• ⏱️ The time complexity of the approximation algorithm is discussed as being proportional to the number of edges, which is polynomial time.
• 📉 The script provides examples to illustrate the algorithm's process and how it arrives at an approximate solution, which may not always be optimal.
• 📝 The concept of an 'approximation ratio' is introduced, with the example given having an approximation ratio of 2, meaning the solution is at most twice the size of the optimal solution.
• 📚 A theorem is presented to prove that the approximation algorithm runs in polynomial time and achieves a 2-approximation of the optimal Vertex Cover.
• 💬 The presenter encourages viewers to comment if they have doubts, indicating an interactive approach to education.

Q & A

What is the main topic of the video?

The main topic of the video is discussing the Vertex Cover problem using approximation algorithms.

Why are approximation algorithms used for NP-complete problems?

Approximation algorithms are used for NP-complete problems because they can provide near-optimal solutions in polynomial time, which is not always achievable with exact solutions.

What is the Vertex Cover problem?

The Vertex Cover problem is a NP-complete problem where the goal is to find a minimum set of vertices such that each edge in the graph is incident to at least one vertex in the set.

What does the term 'approximation' mean in the context of the Vertex Cover problem?

In the context of the Vertex Cover problem, 'approximation' refers to the process of finding a solution that is nearly optimal, but not necessarily the absolute minimum, in polynomial time.

What is the significance of the term 'epsilon' in the approximation algorithm?

The term 'epsilon' in the approximation algorithm represents the degree to which the solution can deviate from the optimal solution. For example, a 2-approximation algorithm provides a solution that is at most twice the size of the optimal solution.

What is the time complexity of the approximation algorithm discussed in the video?

The time complexity of the approximation algorithm discussed in the video is O(e), where 'e' represents the number of edges in the graph.

How does the approximation algorithm select vertices for the Vertex Cover?

The approximation algorithm selects vertices for the Vertex Cover by arbitrarily choosing an edge and including both its endpoints in the cover set, then removing all edges incident to these vertices from the graph, and repeating the process until all edges are covered.

What is the difference between the optimal Vertex Cover and the approximate Vertex Cover?

The optimal Vertex Cover is the smallest possible set of vertices that covers all edges in the graph, while the approximate Vertex Cover is a solution that may be larger but can be found in polynomial time.

Why is the minimum number of vertices important in the Vertex Cover problem?

The minimum number of vertices is important because it represents the most efficient solution to the problem, using the least amount of resources to cover all edges.

How does the video script explain the proof that the approximation algorithm is a 2-approximation?

The script explains the proof by showing that for any edge 'a' in the graph, the optimal cover must include at least one of its endpoints, and the approximation algorithm includes both endpoints, thus ensuring that the approximation is at most twice the size of the optimal cover.

Outlines

00:00

📚 Introduction to Approximation Algorithms for Vertex Cover Problem

This paragraph introduces the topic of the video, which is the Vertex Cover problem and its solution using approximation algorithms. The speaker explains that for NP-complete problems like Vertex Cover, where finding an exact solution can be difficult, approximation algorithms can be used to find a near-optimal solution. The video is aimed at those who have already seen previous videos on the topic, and it emphasizes the importance of understanding the basics, such as what a Vertex Cover is and how it relates to the Independent Set problem. The speaker also discusses the challenges of NP-complete problems and the three general approaches to tackling them: reducing problem size, focusing on special cases, or using approximation algorithms to achieve polynomial time complexity.

05:01

🔍 Understanding the Vertex Cover Problem and Its Approximation

The speaker delves deeper into the Vertex Cover problem, explaining that the goal is to find the minimum number of vertices that, when selected, cover all the edges in the graph. The paragraph clarifies that while it's possible to select all vertices as a cover, the challenge lies in finding the most efficient, minimal cover. The speaker introduces the approximation algorithm 'approxVortexCover G' and explains its basic steps: starting with an empty set of vertices, selecting an arbitrary edge, adding its endpoints to the cover set, and then removing all edges connected to these endpoints from the graph. The process repeats until all edges are covered. The time complexity of this algorithm is discussed, highlighting that it's proportional to the number of edges (O(e)).

10:04

📘 Example Walkthrough of the Approximation Algorithm

In this paragraph, the speaker provides a detailed example to illustrate how the approximation algorithm works. Using a graph with seven vertices and eight edges, the algorithm is applied step by step. The speaker explains the process of selecting arbitrary edges, adding their endpoints to the cover set, and then removing the relevant edges from the graph. The example demonstrates the algorithm's progress and how it builds up the vertex cover set, ultimately arriving at an approximate solution. The speaker emphasizes that while this example results in an approximation, the algorithm does not always yield the optimal solution.

15:04

🔑 Comparing Approximate and Optimal Vertex Covers

The speaker compares the concept of an approximate vertex cover with the optimal vertex cover. The paragraph explains that the optimal vertex cover is the minimal set of vertices that cover all edges, while the approximate cover, generated by the algorithm, may include more vertices. An example is used to show that the approximate cover may not be minimal but still covers all edges. The speaker discusses the importance of understanding the difference between the two and the trade-off between solution quality and computational efficiency. The explanation includes a step-by-step analysis of how the optimal cover might be determined and contrasts it with the approximate cover provided by the algorithm.

20:05

📚 Theoretical Analysis of the Approximation Algorithm

This paragraph focuses on the theoretical analysis of the approximation algorithm for the Vertex Cover problem. The speaker presents a theorem that the approximation algorithm runs in polynomial time and is a 2-approximation algorithm, meaning that the solution it provides is at most twice the size of the optimal solution. The proof involves showing that for any edge, the optimal cover must include at least one of its endpoints, and therefore, the approximation algorithm, which includes both endpoints, will be no more than twice the size of the optimal cover. The speaker emphasizes the importance of understanding the theoretical guarantees provided by approximation algorithms and how they can be used to solve complex problems efficiently.

Keywords

💡Vex Cover Problem

The Vex Cover Problem, also known as the Vertex Cover Problem, is a classic optimization problem in computer science and graph theory. It involves finding a set of vertices in a graph such that each edge of the graph is incident to at least one vertex in the set. The main theme of the video is to discuss an approximation algorithm for solving this NP-complete problem. The script mentions that the goal is to minimize the number of vertices selected to cover all edges, which is central to the problem's objective.

💡Approximation Algorithm

An approximation algorithm is a type of algorithm used for solving NP-hard problems when finding an exact solution is computationally expensive or impractical. The script discusses using such algorithms for the Vex Cover Problem, as they can provide solutions that are 'nearly optimal' within polynomial time. The video explains that the approximation algorithm used can achieve a two-approximation, meaning the solution is at most twice the size of the optimal solution.

💡NP-Complete

NP-Complete is a complexity class in computer science that includes problems which are at least as hard as the hardest problems in NP. The Vertex Cover Problem is mentioned as an NP-Complete problem in the script, indicating that it is a particularly challenging problem to solve optimally. The term is used to explain why approximation algorithms are considered for such problems.

💡Independent Set

An independent set in graph theory is a set of vertices no two of which are adjacent. The script mentions that the Vertex Cover Problem can be related to finding an independent set, as they are complementary concepts. The video discusses how the Vex Cover Problem can be reduced to an independent set problem, which is a key concept in understanding the problem's complexity.

💡Polynomial Time

Polynomial time refers to a class of algorithms where the running time can be described by a polynomial function of the size of the input. The script mentions the desirability of polynomial time algorithms, as they are considered efficient. The video discusses the approximation algorithm's ability to provide a solution in polynomial time, despite not being the optimal solution.

💡Graph Theory

Graph theory is a branch of mathematics concerned with networks of points connected by lines, known as vertices and edges, respectively. The script uses concepts from graph theory to explain the Vertex Cover Problem, which is inherently a graph-based problem. The video discusses selecting vertices and edges, which are fundamental elements in graph theory.

💡Optimal Solution

An optimal solution is a solution that is the best possible within the constraints of a problem. In the context of the script, the optimal solution for the Vertex Cover Problem would be the smallest set of vertices that covers all edges. The video discusses the approximation algorithm's goal to find a solution that is close to the optimal, specifically a two-approximation.

💡Time Complexity

Time complexity is a measure of how long an algorithm takes in terms of the size of the input. The script refers to time complexity when discussing the efficiency of the approximation algorithm. The video mentions that the time complexity of the algorithm is proportional to the number of edges, which is crucial for understanding its efficiency.

💡Arbitrary Edge

An arbitrary edge refers to any edge selected without any specific pattern or rule. The script uses the term 'arbitrary edge' to describe how the approximation algorithm selects edges from the graph. The video explains that the algorithm picks edges without any particular order, which is an important aspect of its approach.

💡Vertex Cover Approximation

Vertex Cover Approximation refers to the process of finding a set of vertices that covers all edges in a graph, with the solution being an approximation of the optimal vertex cover. The script discusses an algorithm named 'approxVortexCover G' that performs this task. The video explains that this approximation is a key part of the algorithm's approach to solving the Vertex Cover Problem.

💡Theorem

A theorem is a statement that has been proven on the basis of previously established statements, such as other theorems. In the script, a theorem is mentioned to prove that the approximation algorithm for the Vertex Cover Problem is a polynomial time 2-approximation algorithm. The video discusses the importance of proving the correctness and efficiency of the algorithm through the theorem.

Highlights

Introduction to the vertex cover problem and its approximation using an algorithmic approach.

Explanation of the vertex cover problem as part of NP-complete problems and the challenges associated with it.

Discussion on the three expected solutions for NP-complete problems, focusing on approximation algorithms.

Definition of polynomial time and its relevance to the approximation algorithm.

Introduction of the approximation algorithm as a method to achieve polynomial time solutions.

Explanation of the vertex cover problem in terms of minimizing the number of vertices selected.

Clarification that the vertex cover problem aims to find the minimum number of vertices, not all vertices.

Description of the algorithm 'approxVortexCover G' and its parameters.

Discussion on the time complexity of the approximation algorithm, which is proportional to the number of edges.

Explanation of the algorithm's process of selecting an arbitrary edge and updating the vertex set.

Illustration of the algorithm's execution with a simple graph example.

Introduction of the concept of optimal solutions and approximation values in the context of the vertex cover problem.

Explanation of the approximation factor and its significance in the approximation algorithm.

Presentation of a book example with seven vertices and eight edges to demonstrate the algorithm.

Discussion on the optimal vertex cover and how it compares to the approximation algorithm's results.

Proof that the approximation algorithm is a polynomial time 2-approximation algorithm.

Conclusion summarizing the understanding of the approximation algorithm for the vertex cover problem and its practical implications.

Transcripts

hello everyone welcome to educ in this

video we are going to discuss about Vex

cover problem using approximation

algorithm methodology okay so those who

are new kindly watch the previous videos

where we discussed about the deductions

that time where we have already

completed some of about the vortex cover

problem to reducible to Independent set

that time we discussed like what is

Vortex cover in depth we have uh read

that one as well as independent set also

we have completed so let us start with

that one like Vortex C problem so here

uh the vertex C problem we are working

with that uh so basically we are going

to use the approximation algorithm the

approximation algorithm especially is we

using like we know when we are working

for the NP complete problems uh we found

like there are three uh difficulties

there are many difficulties we are

getting so there are three solutions we

can expect as we have already completed

in the introductory video that time we

found either the space could be small or

might be we can take the small example

or the small uh categorical problems

through which we can at least expect the

polinomial time because this happens

because of polinomial time though we are

not getting the polinomial time that's

why we reading this one okay like we are

trying to reduce if it is not possible

to reduce is there any other way to

reduce towards the polinomial because

polinomial is a typ time like you can

say B go of n to the per K okay K

represents the constant this is what the

polinomial time so nothing I must not

say that one like nothing in the world

is poal but I must say something there

is a way through which at least we can

achieve the polinomial though we are

getting it that's why we have different

ways one of the ways are one of the ways

you can say uh is your approximation

algorithm so the approximation algorithm

is a way that we have used here

basically Vex cover is a part of NP

complete so as I told you the first we

have a solution like we can take a small

one second as we have already discussed

is you can say uh if similar or a

special case of things we can focus like

three sh some problems we can say

through which at least we can expect the

polom if both two cases which we have

already studed if both two cases are not

there like there is another way through

which at least we can get nearly optimal

result the near optimal result is

approximation which we have already

discussed in the previous videos okay so

here in the vortex cover problem this

this problem basically we are focusing

Vortex cover in the sense like uh

minimization of picking the notes like

we will pick the minimum noes through

which we must say like all the edges

connected to the vortex which you have

have selected is the vortex cover here

Vortex cover that doesn't mean that only

minimum you can take all the vertex as

the vortex cover not an issue but the

problem is if I take all the vertex in

the graph that is also part of Vortex

cover the minimum one is a part of the

Vex cover here exactly what we are doing

we are working for the minimum one that

is where the problem we are occurring

otherwise I must say like the E is the

ages V is a vertices of a graph okay if

I would like to say like it's it's

definitely I must say big of fun to say

vertex cover in what sense if I say all

the vertices which you have is

equivalent to the vertex cover that time

I must say because all the vertices are

covering means are connecting with the

edges in general you can say I'm taking

this example of a

graph clear this is just a graph or you

can say a tree I must still for a graph

all vertices should be connected me

there is a cycle must be present for a

graph okay so if I would like to say the

vortex cover I must say if I'm selecting

all the vertices it's also part of

Vortex cover but this is not exactly our

Target is to find the Vex cover is

minimum one whenever we are focusing on

the minimum like the minimum means the

number of vertices which you are

selecting should be less

clear if I'm selecting

a this will be covered this will be

covered clear if I'm

selecting B this will be covered and

this will be covered so what we have to

do like out of this like there is a

three vertices are there so if I'm

picking this one so I must cover this

one also so two vertices at least needed

to complete or to say a minimum vertex

cover clear this is what exactly we are

targeting to find out so the Tex cover

you can say the total is could be

considered whenever you are considering

total is this is a maximum Vex cover

this is not our Target is the minimum

size the minimum one whenever we are

discussing that is a part of you that is

our Target how to define the minimum

number of edges to be considered as a

part of vertex cover this is our Target

okay minimum vertex cover I must write

that one here

minimum minimum number

of AG uh

vertices

for vex

cover this is our Target or a and

objective you can say to find minimum

number of vertices required or need

needed for the vertex

cover next uh I must tell you like I'm

following the book for this problem I'm

following uh Corman book you can follow

that one the same to same I'm keeping

the lines and wordings there so this is

an algorithm you can say the algorithm

name as approx Vortex cover G here C is

a set you can say C stands for the

set for keeping

the

vertices keeping the

vertices next e Dash is a age which is

equivalent to g dot represents while the

number of edges clear until it is empty

mean suppose as I have already given you

the example so here this is one

graph here the edges are three until the

are three like we will run that one

clear so from this we found uh it will

run for big of e because V Loop we have

included within that while loop we set

until it is e means big of Fe the number

of edges we are actually having that one

we can say definitely it's a part of our

complexity which we have already

completed in our the the first the might

be the complexity video that time we

have completed uh to find out the term

complexity so you can say until so we

will return it Okay so until means we

are just focusing on the number of edges

so here as for the time complexity I

must tell you the time complexity could

be big of e why because the number of

Ages we are focusing at here clear next

once we started this one let

U be on arbitrary edge of e Dash we just

whenever we said e Dash e is skipping

all the number of edges from the graph

clear so then what we'll

do c was previously is a set C was empty

set this represents empty set okay of

five like we include suppose UV suppose

here is a I'm just writing this one a so

a comma B both we will be keeping

because from an age if the if I'm

picking one age a will have two end

points here is for that one A and B

whenever I'm keeping this age so here it

is written UV clear that UV is Union

means we added to that the five which

was previously

there then

remove from E Dash every Edge incident

to either U or V means once I'm picking

this one once I'm picking this one the

two end points I have one and a and b so

what I have to do I have to remove this

one I have to remove this one what it is

written I have to remove that one I'm

just picking this one so written c c is

a so we are expecting our Optimal

Solutions first of all this C is

approximation value the number of

vertices are two if I'd like to say for

this example the optimal optimal means

what what should be the uh the answer

what should be our expected answer clear

means what should be the correct answer

for us so we have already checked that

one for optimal value either a AC CB

anything we can take but at least two so

for uh if this is C if I'm writing C

star so C star could be the optimal uh

solution or optimal uh number of or

optimal set you can say if I'm picking

also it keeps either a b or B comma C or

a comma

C so the optimal means whenever you

focus on the vertex cover the number of

vertices which you are going to pick is

either AB BC anything you are taking so

that should be two also here the

approximation for this example as we

have already covered in the previous

video as an introduction for this graph

for this graph we are saying one

approximation one approximation means

which is equivalent to the optimal

answer optimal

algorithm or optimal value for this

example for this example we are

expecting the one approximation where

Epsilon is equivalent to zero means the

extra which we are adding in 2 three

whatever we are taking suppose for two 2

approximation we must say epsilon is 1

why because 1 + Epsilon we have already

said in the approximation one that time

we must say for approximation value if

it is two means more than one suppose we

have so that one more than one whatever

is there so we can say it is Epsilon for

us okay so uh we will be discussing with

the example so for this example which we

just have taken for our uh you know

approach for this one we found one

approximation for this one but this is

not always correct okay next for the

example you can say uh suppose this is

example this is a book example I have

kept here so a b c uh d e f g there are

almost seven vertices we have with us

and the ages is 1 2 3 4 5 6 7 8 okay

there

are 1 2 3 4 5 6 7 and 8 eight edes are

there so what we are doing first we'll

start

arbitrarily eight means we will start

with the while loop while loop will run

for eight number of times because we

need to remove all the elements all the

edges the number of edges are eight so

we will take all the eight up to in of

five means zero up to up to eight we

will run this is what it represents

arbitrary written arbitrary Edge we are

not always saying only this one will be

picked or this one will be picked number

wise no arbit you can take EF also but

as for the book they have taken B to C

okay so this age once this AG is

selected line five which it says the C

was previously five here C is previously

five for this one C is B comma C the two

elements we have included clear next As

for six remove e- every incident means B

to C which are connected we have to

remove this one just dotted L says we

are removing that one clear this is what

the C value is I'm just writing C value

here B and C node here arbitary again we

have two options we have uh 1 2 3 3 4

five there are four options we have

because every others are we have already

removed so here I as for the book they

have taken E and F so once E and F is

picked now C value will be previously it

was B comma C why because here it is

Union okay B comma c e comma F we are

picking so now C value is

updated only one we have to pick there

is

not no other ver edges are free then

what we'll

do we have to pick that one b c e f d

then G this is our final uh you can say

the vertex cover okay which is using the

approximation algorithm or approximate

vertex cover you can say this is our C

value so uh this one is approximate Vex

cover I can say us approximate so that

that's why I'm just writing

uh

approximate vertex cover or ABC this one

is AVC so which choose we have selected

b c d e f g this is our uh number of

nodes or number of vertices we have

selected but for the optimal which is

said as C star

like if you say the optimal means the

number of vertices which we are

selecting wisely that should be minimum

clear minimum means you can check

suppose I'm picking B indirectly I'm

removing this one clear if I'm keeping e

I'm ring this one means I'm covering

basically here no removing Concepts we

should use we will cover when we are

covering so I'm putting tick mark okay

next if I'll pick D also uh Tex to be

covered so here a part of cover we are

supposed saying so for optimal

indirectly what we are doing so you can

check we can cover all the edges if I'm

saying covering all the edges I'm just

putting this Mark so you can take all

the ages should be covered that's why we

can say it's a Vortex cover so here

optimally what exactly we are doing b e

d this is not always a true but

definitely I must say as we have already

studied in the independent set that time

you can compare one okay so if I would

like to say a then a could at least keep

this one if I'm keeping C so c will

cover this one if I'm giving d d will

cover this one but this age will be

covered by at least one of the uh vertex

that's why the problem will arise for

the optimal one means what should be the

best answer this is our best best one

best or optimal you can

say optimal

value of vertex cover okay so is b d

only clear those

so the the problem is not that much hard

to understand the way how we are doing

the approximate value or approximation

how we doing that one that is playing a

vital Ro

okay so I hope you understood here we

are keeping 3 36 here our C value if I'm

saying mode so it is six here if I'm

doing the mode means the number of

vertices here it is three so if you can

say like which we have studied earlier

is a row value so here is c c

star which we must say two approximate

value or two approximation

to approximation okay this is what we

have

covered like the row value is two here

and we must say it's approximation 2

approximation so I hope you understood

this one theorem I kept for you so here

in the theorem basically how to prove it

that matters a lot always so approximate

cover is a polinomial time two is two

approximation algorithm it it just shows

whatever the appro oximation that you

have done polinomial time exactly you're

getting but that is two approximation

means it is two times more than the

optimal answers what should be the

optimal answer is this one should be the

optimal answer but it is two time more

the approximation value which you got is

two time more that's why it is two

approximation clear so uh proof that

whenever we are starting with a proof

always you should remember what exactly

we are representing like C represented

as the set of vertices that you are

getting through approximate vertex cover

as we have already discussed that one

clear and here they have introduced a a

is just an age you can say here the

cover and age is a has two end points

okay like it has two end points so

whenever we start with c c is optimal

cover optimal Vortex cover you can say

or optimal cover set of optimal Vortex

cover which we have studied earlier

clear so here this is the optimal vertex

cover or best vertex cover you can say

so it is three so like that but how to

basically verify that one so whenever we

say Vex is a minimum one means there is

an end point of A and B suppose this is

our a clear this is our a I am just

changing that suppose C with d the

naming convention I'm changing just try

to understand suppose this is a we're

having this one so there are two

different end points we have for

whenever we say say optimal we have to

pick at least one if I'm saying

approximate for approximate two end

points have to be selected that is what

the problem is clear whenever I must say

keeping the optimal one optimal will

keep at least C or or D any one of this

but at least one this is what it is

written clear optimal include at least

one end point it is clearly mentioned so

definitely a has two end points and here

it will skip one that's why

clip this C and this one first we'll

cover up so this C whenever we discussed

with C star

and with a what exactly we should have

to do like for the line

four line four means here let youu be an

arbitrary age we just picked arbitrary

age which we discuss this one

clear so next Once the arbitrary AE is

being fixed so optimal cover we should

have the optimal cover optimal cover at

least we will pick one of them so

whenever we should say the one of them

we are picking up so this condition will

satisfy once it is satisfied next C

which is the approximate value c will

keep the both the end points clear both

the end point it should have to keep

that's why it cover up with Cal to 2 a

means there are two different end points

we have So based on that we will pick

this one if you equate if you equate

this to like

3.2 35.2 35.3 if you're going for

equation so what you'll get it like c

equal to 2 a

this is what exactly you got in 3.5

earlier 35.3 so you just equate with the

previous equation definitely you'll get

uh this C is less than equal to 2 C star

means earlier you were just keeping this

was our like for C I must

tell U

First for this example means there is

two edges uh sorry one edge with two

vertices

so c will keep definitely we studied

earlier like two end points C and D okay

so C star will be picking at least one

of them either C or D anything

or D clear so if I'm saying this one so

it represents two because the number of

uh vertices are this one and for C

star it is one it's a basic simple

example that through which we can

understand so definitely it is two times

uh more you know C uh that's why you can

say C is less than equal to 2 into 1 why

you are saying uh less than might be it

is somehow the problem could be the what

exactly you getting suppose 1.5 instead

of 1.5 you you might expect that one so

it is some somehow nearly equivalent to

two-way approximation that's why we are

saying in this order clear I hope it is

clearly understood by you where we are

getting the approximation through which

uh we we have completed the

approximation on Vex cover and we are

getting in polinomial time but the

polinomial time is two two approximation

algorithm two times the optimal answer

we are expect uh we are getting but our

expectation should be exactly one

approxim

but we are getting two approximation

this is what we have completed of the I

hope it is clearly understood by you if

any doubt please comment below thank you