
Title:
1501 Dave's Problem

Description:

So Alice is now super, super happy, but what about the others?

So I suggest that we take a look at Dave here,

and Dave, as you remember, was working on a logistics problem,

so what he was trying to solve was shortest tour.

And actually, last time we left off,

Dave wasn't too happy,

because we found out it is not very easy to find

a good search tree or a pre processing strategy

for his problem.

On the other hand, of course, we mentioned that in practice

shortest tour is usually very easy to solve,

but from a theoretical perspective,

maybe we were a bit lucky for Dave;

if we're not looking for the best possible solution,

but except an approximation,

and then if we should find an approximation,

Dave can get a little happier here

and of course he doesn't have to be as jealous that

Alice has such an NP complete problem

and he seems to have a harder one.

Now lucky for Dave,

there is a constant factor approximation algorithm

for shortest tour,

but since Dave is not that proficient in theoretical computer science,

I think he doesn't really stand a chance

of coming up with this algorithm himself,

so you will have to pay close attention now

to be able to explain it to Dave.

The concept that we will use is that of a

spanning tree, and if you've had an algorithm course before,

you will know what a spanning tree is,

but I'm quickly going to explain it to you just to make sure.

A spanning tree is a part of a graph

or actually it's a selection of edges

in a graph so that the result looks

like a tree.

Well, what that means is that you select edges

so that you still keep the whole graph connected,

but you don't have any cycles,

so a cycle would be something like this

where you can leave a vertex and then come back to it

another way, so you select edges

so that the whole graph is still connected,

but there can be no cycles, so

to have you figure it out, let's do a quick quiz here.

This is the thing that worked 3 times.

I'm going to give you 3 choices of what a spanning tree could be,

and the red edges are always those that

I'm selecting here.

I would like you to tell me in which of these cases

the red edges from a spanning tree for the graph.