One.

Does this work.

That's fine and well you know.

It's.

I'm not sure you know.

You should let me just do
this again off on a sort of.

Other is you know people
who are healthy and fit.

OK for me.

OK So this is I'm going to talk about

an element of the learning of us
would probably say some problem.

This is joint work that I mean and
Sharon Kyra.

So so let me first tell you what the
public system problem is I think most of

you know and I'm just going to appeal to
authority and take this call from good in

and when that is perhaps the most well
known committal optimization problem.

So I believe people we should know and and
one would ask why do people work on it and

this is beautiful call from us try work.

In is a nice book on chemical optimization
that it belongs to the most seductive

problems uncommented optimization pass to
a blend of complexity applicability and

appeal to magination.

This talk would mostly be about
the complexity of the problem not

the applicability.

About the problem.

Especially like talking about heads
architect which is I think where

it has had great impact on especially
a particular view about this problem.

So I want to make sure it's what I want
to talk about is merely the complexity

of this problem.

So and to give you prove that
it is the it is popular problem.

This is a poster with a script from
the T.S.P. don't get it but if you say

it was a contest which was run by Procter
and Gamble in nineteen sixty two.

It's a long time back it's a very
similar to the Netflix price

that was there all of which people might
know now was kind of Netflix price of

the one nine hundred sixty S. But the goal
was to find a traveling salesman to

which business I think around a bunch
of twenty five cities in the US.

Find the shortest to.

Somebody sources of quality
a million actually one displace.

Somebody such as from Carnegie Mellon
actually won this prize.

OK So them anyway.

And so let me just tell you
a couple of them that we're going

to talk in work with this and doc.

One is a basic is the metric D.S.P.
and so in this problem.

What you're given is a complete wrap with
some metric somatic means of distances

that satisfy triangle inequality and
the goal is to find a homage to a cycle of

the shortest length letter for
example if my graph is this.

I have these cost or one.

It is there to cost.

It is not a company graph.

But let's assume the edges which
are not there also cost to write so

the shortest two with look
something like this or

use two edges of cost one and three as a
cost to sort of the solution is eight and

one can of if I there's not a shorter time
in a cycle at least in this small graph.

OK.

From approximation I would point of view.

That's what we want to work on days of
beautiful alchemy Christof it is and

will come back to this later.

Approximation in this was in
one thousand nine hundred six.

It's beautiful out there.

Thomas very nice simple
is usually the force.

Algorithm one teaches also in one one
introduces approximation I will terms.

For a special class of Matrix people have
tried to improve it was ample R O N ninety

seven had a breakthrough
in Euclidean matrix.

So if your point you have points given
in let's say some Euclidean plane in

are two hundred businesses
are you clean in distance and

now you want to find
the shortest to which.

So the four that you can actually get
a one plus Upsilon approximation for

any fixed epsilon So prosecution scheme.

You can get are pretty close.

Of course.

Running time of the I will turn
would go exponentially in Epsilon

one of it's on the hardness it cannot be
approximate better than one point zero one

I talk about later that
you actually put a fence.

We have this is probably better Impala.

So and there was a conductor
actually which is nice injector.

I tried to pull a preferences for it but
I'm not completely sure I have to ask.

But I think one of the first thing I
could find was in goatees a woman's

who said the right answer should
be foretold not the half.

It might be older.

Also this conjecture although I'm
not completely sure about that.

And I'll tell you where December fourth
would actually comes from that it's

not that we're just pulling it
out of the hat or something.

But there are some lateral reasons why
the right answer should be foretold So

this is one problem.

The other way in which is also which
will be actually quite useful for us.

Also is is a generalization of
this problem is a matter to speak.

So generalization is as follows.

We do not assume the distances between you
and we and we are you or you are equal.

Actually they could be different.

So the we is not necessarily equal to.

D. B. you get.

For this there was an eighty
two by phrase governor.

R.T.M. a few only which was
along an approximation and then.

Very recently there was
a paper by Assad or

Marty who just gave a nice talk about all
the result of ACE and Karen and so Barry.

If you were not going to
log an approximation.

But had a conflict actually for
this problem.

I would say these things are even more
open here than I We don't know what that

ancestry half of voters here we don't
know what the right answer is logon to or

even to a lot of people who believe the
right answer might be too approximation.

Pardon.

Yes but I think is the right answer.

Or yes yes so

tried there are sit back and
inequalities but only on better triangles.

So so there is still so
in all of these we assume directed

by inequality if you do not as you
bring in inequality even for this.

Symmetric case.

You cannot approximate the problem at all
to any parliament factor is as hard as

hamiltonian path or having to cite or just
taking the graphics on it as I feel so

I can't seem to get this working but to.

So let me just so there is one of the
reasons that really comes so why with this

board number forty comes in because of
this lunar program so this and want to

spend some time on this new program and
we were just going to be crucial.

So it's a very simple in a program that
was started in great detail by Helen cow

in one hundred seventy and the leader
program to say is the following.

How one for one variable for each age
which is indicated really well but

I'm going to pick it in my cycle
are not in my solution I'm not

objective function is clearly to
minimizing the cost of the edges I pick.

I want to say for each word like saying
that OK you pick two it is that it were

tax rate one like exactly
five you have to cycle and

have these cut constraints which says
that OK out of any cut you have to pick

at least two edges if it's a non-trivial
cut if the subset of what is not all

suitable This is you must go into each
subset and you must go out of its opposite

is called up to elimination usually
the is written in a different form but

I'm going to write in the Scott form that.

The couple of things to not all here
is the optimal piece clearly less and

less than optimal solution
is a lower bound.

Solution is a feasible solution
to your program as always.

The other thing is that this can be solid.

The couple of ways to do it is one is
that you give a separation Oracle for

this problem and then up then use the two.

And if you think for

a second that the separation Oracle
is really the main cut algorithm.

You just want to check for

whether each cut the milk out of
the graph is listened to or not but

that's that's basically the little so this
can be solved the other ways to solve it.

You can write an equal int formulation
which is Parliament sized.

OK so.

So what actually.

Nice in Christopher he showed that
he ordered three of approximation.

So short that.

It's no more than three after I'm stopped
and little we'll see actually sure that

Christopher These are with them or does
the solution which nobody three thousand

was that it is a strong
result because of the not.

Is a lower bound.

So like any sort of like we'll go with
most of the proof actually over this and

that's really one of the starting
points of our algorithm as well.

So he should do something.

And moreover there was this nice example
if you haven't seen this before.

It's like I want to point to must
I wanted but there is an example.

A very nice simple example which where
the optimum solution is actually

much higher than the linear
problem solution.

Remember leader program solution only law
it's it's something lower than optimal

solution and
the ratio can get is actually for third.

So if I look like.

Look at the integral of the gap of the P.
which is the matter which I defined to be

the maximum of the ratio
of the optimal P..

This example shows it's no more than it's
at least four told the maximum because

there is a particular instance where
it's foretold and just a few days after

the term and the argument of also
shows as no more than a three have.

When somewhere between four third and
Korea and

the connection was basically the right
answer is for third then you might think

maybe just because we found one examples
where people tried also looking at all.

Of the examples and even doing some
experiments so people have for

example enumerated all graphs all
instances of size of collecting sixteen or

twenty and they have really found
out this is the worst example.

Essentially you can.

It's a family of examples and

their character is all examples which
have the worst case in technology out.

OK So what are those that actually
gives is some evidence that the right

answer is not a half.

So it doesn't prove a smaller than that
but gives some evidence that it is smaller

than three yards doesn't show that
it's close to four total and they so

let me just give what our result is be
sure that there exists a point normal time

three hundred minus epsilon approximation
algorithm for the graphical T.S.P..

Where if someone has some fixed costs and
greater than zero.

So does not.

Size of instance is some pics
constant grade and zero.

So I have to tell you know what graphical
P.S.P. is graphical D.S.P. is a special.

Class of matrix which is defined as
follows I give you an weighted graph.

It's not a complete love anymore so
I give you some unweighted graph and

my metric is just sort of
part distances between.

This between any pair of
what is in this graph and

of course if this graph is
weighted is equal to all metrics.

But this is a subclass of all metrics and
these are and

this problem is called graphical T.S.P..

Actually this problem also equal and
to the following problem.

I give you this graph instead of thinking
of making the complete of as a metric.

I just want to visit every word takes at
least once and find a two which is every

word except least once you maybe said What
is more than one twice and come back to

the final vertex so insentient something
that does exactly the problem that we saw

that's exactly graphical T.S.P. you can
think of it in these two different ways.

OK so my I'll try to give you some idea
about how we actually get this result.

But do not have to introduce one concept
and that's going to be very crucial.

This is a concept of uniform London for

spanning three decisional spanning
trees which is a following.

So.

If so was I give you some numbers for

each of my graph with a lambda easy for
each easy and

I want a distribution which has a falling
property that the that the particular T.

The Probably that I actually get
a particular tree is a proportional

to the product of the lambda yes it so
that this this kind of measure for

a particular number and
want to call lambda uniform distribution.

OK So let me give you an example suppose
that you have this graph and lambda is for

these two edges as one and four.

This is half.

So this graph has three
police responding trees.

So you can see these two trees these two

trees will have the same
problem it is because.

The lambdas are the same a half and

business which is really going to
be very crucial for allowed them.

So it's a very nice image of crude
by a supporter doll with a use for.

This image P.S.P. is that if I give you
a free fashion solution of the sub to

LP which was LP for the for
the tally system problem.

Then I actually can find
a lumber uniform measure or

disparities of the graph such that
the probably actually use some for

any is the marginal value of the probably
that this edge is in the three you sample

is that essentially very close
to the LP value of that edge.

OK So in some sense this
is like you can find a lump

you can find a bunch of these
lambdas weights for these edges.

So that you sample from this
resubmission that probably get.

And you look at the edge and you see
what the transit I want to get this as

in my sample T. is actually
essentially follows your L. L. P.

value so much in US are exactly
what you want in some sense.

This is paper was there to go but
they proved it for under it.

The only under today's no
no no there's none of that.

These edges are so if I give you X..

E values a.

So it's essentially a year or so.

You want this point to be in the interior
of the spanning tree polytope so.

So the that LP is if you scale it by
a factor of one minus one minus one

when you actually can put it in let us
show it in the interior of the Spanish

people it'll be OK And furthermore the
show actually does lambdas can be computed

in the Parliament I'm using a maximum
entropy comics program where

you can find these numbers and
you can sample from this is to be.

And so on it so you can actually do it.

So this distribution is it's nice
to be sure your sample from it and

it's and it'll be nice properties and
we'll come back to that later.

Hard hard code is to be.

Yes yes.

So I do.

Yes that's why.

Yes yes the state's also known
as hard core distributions.

Yes and it has some nice properties and
we'll come back to that as well.

So that's what we're going to use.

So that's one thing.

And so looking at the solution which
essentially came up with this algorithm

which is very similar to the cost of it is
our term and very similar to the outcome

which was used by it for
is a metallic system problem as well.

So I give them is the following you come
Solihull P. You computer and P. values.

OK God isn't the solution.

I compute Islam the information
which has which we

know exists which has this property.

I'm not sample a tree
from this is to be sure.

And now what I say is OK I've got a tree
and I look at the vote is if it's about

degree and I put a matching order already
were deceased and I take the union.

It's and that's what I return.

But of course if you want to return home.

I don't cycle.

But as I discussed before it's enough
to return something for lady and

you can all be shocked but do Somalians
shortcutting which is standard.

If you've seen Christopher he's
a little also so you can get

him into a cycle of he will cost but
it's enough to return this discipline.

So there's a whole hour to it.

It's very similar to the Christopher
desire to write because nobody wants

Christopher the other time does instead
of doing something like doing some random

picking random tree it picks up
a minimal spanning tree of the graph and

does a four step is exactly the same but

it's in the first three steps are replaced
by a minimal spanning tree here we're

doing some random sampling
to get the nice thing.

We're doing over here is
some of the nice about

sampling is essentially we're
following the LP solution.

And that's going to be.

That's the something with us.

You know.

Less so

you know the case

you rock.

A feasible solution.

Yes solution.

Every feasible solution actually yes.

Yes.

Which is exactly that is in
the interior of the Spanish people.

OK.

So I look at and for

this algorithm we made the following
conjecture that the approximation and

comfort factor for this I was a mystery
of mine is absolute for any metric.

So for T.S.P. I want to this is
a conjecture that made for the S.P.

This is a better than
three of approximation.

Yes So you have to do a scaling to get
inside the span into politics because it

picks your very best guess.

Or one please if you want to then but
it's a good skill you usually do do skill

by one minus one when I want don't
want to put that over there because.

So you because you scale by one minus
one of what I am like in the Idiot.

Smaller one.

So I can if you ask you this algorithm is
better than three off the south and Dr.

I think we still stand by this.

So we know for any metric for T.S.P.
fatalities a problem.

We believe this out of the kind of
algorithm actually gets better than

Christopher do with them.

For some excellent greater than
zero which is a real constant.

What we could prove is the following
the that approximation

factor of a similar other term is better
than three half for graphical metrics.

OK so we couldn't prove exactly what
you want to do but something similar.

OK And I'm going to tell you what the
force of good you know what graph metrics

are so I will tell you what the similar
to miss is not very different.

So basically I just add one more step.

What I say if you're LP is merely integral
that means if you follow your program.

Most of the edges are very
close to zero or one.

Basically you should be doing something
deterministically you the LP has already

solved the problem for
you if it were illegal you were dumb.

It was merely until you do something
deterministic don't try to do

something around them.

And and basically does a little in
case it is not merely an evil or

you do exactly what what
the other of them is doing OK.

In this case.

Actually it's lot of very hard to show
that you actually get a four third fourth

or approximation of a close
to forty depending on.

Almost all is one minus Epsilon and

the edges have value close has
value more than one my steps along.

So almost all the edges are very close
to one then essentially you should you

would think that you are done and after
you're done you can find a tree which will

give you approximation factor for thirty
plus epsilon some part of it's a lot.

Like maybe a few of us.

But basically you're done.

So the interesting case is the other
one when it is not the case.

And that's basically what I'm
going to discuss with it.

Yes.
So

not exactly no no no let me say it does.

Maybe but it's not completely clear no.

No no no.

In some sense because I could
always add some kind of a dummy at

this kind of zero cost of the graph and
do something to some takes.

So basically the whole of all your
instance is really in those Epsilon and.

With a fractional so I can hide.

So like one can do some takes so
it's really does not apply.

So basically for
this algorithm this is the algorithm for

which we proved a guarantee for graphical
T.S.P. OK so for the rest of talk I'll do

the analysis goaded analysis give you
some idea of how the analysis goes

which I think is it has some interesting
we use some interesting ideas.

From different parts for different
parts and but basically I'm not one.

Talk about this part anymore.

I'm just going to assume
this doesn't happen.

Yeah sure.

OK.

Yes I'll call Christopher he's your yes
you're absolutely starting point would be.

This is very similar to what Christopher
does does Christopher does actually

swapping random pleats a minimum spanning
tree and the mineral spring to you can

show is clearly no more than not because
optimal solution contains a spanning tree.

It's a cycle.

So clearly there is a tree spanning
tree of steeple cost over there so

it's a very similar idea over there and
the second one is is a is a bit tricky but

not too difficult but
I'll go over it in more detail in next.

Light is basically that for any tree in
the doesn't matter how costly it was for

anything you can show
the cost of the matching or

odd degree what he sees in respect to what
the set about anybody sees are is no more

than the half of the LP cost which
is no more than our power to get so

this is I'll show the slide show this
in the next slide in more detail but

basically the idea would be to
just keep this like this and

we're going to some are sure
that the randomness of T..

We're going to maybe be small chance.

They expected cost of
the matching Latin you drop down.

We'll get we'll get some savings.

Sometimes we'll get lucky.

Sometimes we'll pick a tree
which actually gets.

A small set of what he sees a small
cost for the matching to repair it.

And no because.

This Is Us expectation I just apply
linearity of expectation my total cost is

cost of the cost of the matching.

So I just applied in Europe
expectation I'll get.

I don't want to do that.

I say Yeah I said it is not true but.

Yes.

Yes.

So like I will get it
with high probability.

Yes yes yes.

So yes.

It's not really as you're
saying it's not deterministic.

I would not get any particularly
Yes you're correct.

I only get it it's anonymous I
would I could just repeat right.

Yeah I know it's come with you.

This is yes.
OK So let's let's see why this is true.

So I'm claiming what you
would do you choose.

So unfortunately that's not
a set of our bodies would be

different in respect to whatever
the state of our bodies is you get

the matter would be no
more than a first year.

Let's at least two so we want to show the
matching cost more than after one or two.

Right so let's look at optimal solution.

Like this.
Essentially I'm going to reduce analysis I

thought so
this is this is our optimal solution.

And I mark the words which I read which
are the odd degree what is overspending

to you that's what you found founder
three which is something which

I'm not showing you.

And these are or degree what he sees and
I want to find a matching of what

these are to be what he sees and
then claiming them.

The main course matching cost
no more than October two.

And why is that to.

Well because after the solution
actually contains two such man things.

And one of them is going to
cost more than up to two.

Well you know.

Well you see actually deals are not
really matters what you have done is

actually found parts.

Between these audio disease but when you
were in was to toggle the degree you

want to make every vertex of even degree.

So something which was already even you
wanted to keep it even something that was

all you want to talk so if you find parts
whose endpoints are the word disease for

which you want to talk all that's perfect.

And this is generally exactly
quality Don't problem.

So where you are rather than finding
direct answers you're finding parts of it

so up contains these two teeth
the joints more particularly OK so

this always shows that matching
is no more than art or

do I want to claim a stronger thing
which is matching is no more the LP or

two which is funny thing because L.P.'s.

All of the not at the end this
is what we'll see should.

And I'm going to in the next I'm
going to show his analysis and

then we're going to see how that actually
how what we need to do to get improvement.

OK so let's see why is Martin
the lesson help you or to what we're

going to do is the right Alina program for
this matching what each one problem.

OK So
we want to write a linear program for

the student problem which is which
was given by Edmonson Johnson

the linear program essentially says
the following is very intuitive.

So I have new variables Y. e one finding a
matching So I'm writing a linear program.

So one of the set of variables Y. e.

But it is but
I'm going to put it in my matching or

not objective function again minimizing
the cost and recall what was our goal.

I want I'm giving you a tree and
I want to make it all.

Ian I want to make every word
text which is what degree even.

But if you see that if I were
everywhere Texas even degree every cut

has even number of edges.

Also right and that's a constraint
on placing that if your T..

These are three.

If your cut has odd number of edges.

Then you have to pick at
least one more in that cut.

OK So this is a valid constraint for
any subset of what is if you only put

the odd number of edges you know you have
to pick one more edge in that cut right.

And that's what you place.

So this is more than the degree that
you really want to say OK at every or

body what access to pick ONE MORE it.

What is placing actually not just for
what he sees what tax cuts but

all odd cuts and Edmonson down to
sort of if you solve your problem.

You get into your solution.

So this is the Salina
program is actually in deal.

So which is a very messy and
developing on it once batting.

Theory so.

So for example this would be a cut.

Also right in the if this is my tree in
this cut I picked three edges I know I

have to pick at least one more so
I don't know which what exit would hit but

it has to wait at least
one more certainty.

So nice thing now I want to claim if X.
star is your LP solution to a sub to LP.

I want to play my start over
to is feasible for this LP.

And that's actually straight
forward if you look.

For a minute.

What does your stuff to help me give you.

It gives you that in every cut you
have at least two edges fractionally.

This LP demands one edge in only
some of the cuts the cuts for

your tree were actually appeared on
number of edges so if you clearly.

Why a star or two is a feasible solution.

So this cast the there is a feasible
solution to this LP which is no

more than my sub to the LP cost two or
two and I know this is in detail.

So the opportunity to
solution is not even cheaper.

So that the troops will
seize argument basically so

that the cost of a diesel term
is three help themselves.

And our goal will be to not see

when I have to improve this argument when
when can we reduce the cost of formatting.

So one has a real thing
to do is actually four.

Maybe we'll just keep this every I'll
keep it to be extra by two but for

some ideas I try to reduce it a bit
maybe extra work to do a start or

two plus a long and
still hope that this LP remains feasible.

OK Does him and
we want to see when can we do that and

that will give us some condition and
we're just trying to stick out what what.

When will that condition actually work.

OK so
let's see when if I try to reduce it.

When can I reduce it.

OK.

The other thing is this analysis hold for
any theory that's so

suppose you want to set Y. e two extra
over to perception on the two two ways

I can do that first thing is for
base edge the cuts are not even

let's say the cuts are not even
present for which which will complain.

So they some cats will start complaining
some cat will say OK this this modern new

will be solution is no longer feasible.

I will reduce too much.

So maybe if they don't.

Not if they're not even present then
I'm even happy with the other is I'm

only reducing by a factor of two plus
Absalom if some of these cards as we had

a value more than two plus Absalom then
I'll be OK as well because why did two

do well because I knew in every
cut I was too if I never thought

I would I would be too close.

Absalom this would still work out if we
reduced by a factor of two closer to one.

So the cards are really don't matter
out of the cuts which contain my.

And whose values between two and

two plus along with those are the only
cuts that really worry about.

And I want I want those
cussed not to be present in.

So that's a bit of a mouthful but
basically what I want if

men cut those are so remember the men
cutting aren't a solution is value too so.

And anything between bitch is
between two want to gossip salon and

I'm calling them as near mint cuts.

I want men cuts a near mint cut to be even
mighty should be even number of edges

in those trees in those cuts if that
happens then I can obtain improvement.

Like this is something like
put a lid to our problem but

there's something I just want
to remind everybody again like.

People ever matting is like
until it doesn't matter.

We could just look at it as a.

Every day we were to say I want to hit but
actually it's not oddly what it

is you want to hit you want to hit the set
about cuts really that's really what

you want to hit and that's basically
what Edmund algorithm does.

So that's where his blossom algorithm.

Yes and this like it means Johnson
generalizes the framework of the joints.

So to let make it may be possible.

I'm not sure whether it'll make it.

We'll understand more American
make it more complicated but

let's try to see what kind of
edges will be good or not good.

So suppose this is the solution.

So the LP values are written
over Hell most as you can see

most of them are one and a half.

And this is a spanning
tree that I have and

I want to check whether it is good or not.

So let's check whether
this edge is good or not.

OK So what do I want to check I
want to check all the middle.

Cuts mean cuts where the government is
given by these weights in this graph and

I want to check whether my tree actually
picks even number of edges in all

these simultaneously.

So let's use a minute cards for now so
example in this graph I want to say this

is not good because this cut
the singleton cut is a is a min cut.

Actually every degree cut is a min cut
every degree fraction degrees too and you

are picking only one it so clearly this
is not a good edge right for the street.

So you might think.

OK At least I want.

Even degree on both sides for
is to be good simultaneously.

But again as I said it's just not
enough for example this edge for

this is the end points clearly
have even degrees in my tree but

they're still not a good age because if
you look at this cut now a new graphic can

still say see it's a it's been cut
in it's value is all people used to.

And you've only paid one estimate.

As you can look at this graph.

You won't find.

It's very hard to find actually
any good ideas in this plea.

So it's your question.

Yes yes yes.

No the saving

in here is this example is merely
until we find a deterministic.

So called Other them is still run.

Yes but the very far our
knowledge is OUR them alone but

our analysis does not run in this
sort of masses does not work for

this example because this example
is merely until most edges are one.

So we actually pick
a deterministic tree and

do it and do a photo of the analysis
with this example so that.

You are so yes so
that's exactly what we show.

So we show you the real P. is merely
until all costs a fraction of edges

are good in their random
tree in expectation.

Yes exactly.

So we should one of
these two things happen.

They sum instructor to know
about the linear program.

Solution.

And we show it in two steps and

they are basically two very
different like different steps.

The first every show.

If either you or LP is nearly integral or
you can get a pass and

fraction of edges which are only in
constant constant number of Neumann cuts.

So I can get ASA fraction of the ideas.

Each of them is no more
than let's say ten.

And cuts on tenure mean cuts.

OK So one of these things always happens.

And then we show will then we find
some subset of these are just

constant fraction of these ideas and show
that they actually are good in a random.

And human cuts.

We have to look at you.

So this is good for business.

Not when this is so so this part is

like there's no two you are not this is
a this is just a graph terrific statement.

Complete after six images not
going to do without them at all.

Lots of.

Oratory And they saying you know
you're LP solution is merely until or

a cause and fraction of the ages
are in constant amount of human cuts.

OK And this building after Rick
there's no randomization overhead.

Only issues from when from head to head.

And we see the structure of
human cuts play important role.

See her more than not
doing that great on time.

So let me just briefly
tell you what this is so

so one claim that we prove
is that if I give you or

took a regular to get connected graph and
I told you that almost all the edges

are in a large number of me and many
cards then G. is very close to a cycle.

OK so.

So for example if if your graph
was like This is a cycle and

this directly caper ledges
between each of them right.

And then she does well proving
if you have this thing.

If you.

Most of it is a large number of human
cast your graph will essentially look

like a cycle.

More than a constant.

OK.

Depends also very close to a cycle
what you mean very close a cycle you

would like a bit of a large you might have
other edges which are going around but

those edges number of those issues
can be bounded depending on how many.

Cuts you have.

So it's in it's easier to
think on the converse.

So if you look at a cycle in
a cycle every year it is an end.

Minus one near mint and minus one
min cuts this as in any other it.

In sums is what we are proving is
that your converse of the statement.

So you are proving that
every edge is in a.

Not just in minus one in
a large concert number of

most of the edges are is in more than
some large concert number of near

mint cuts then glass structure
actually looks like a cycle.

OK and forty S B What that implies
is your solution nearly until.

Like if you are and

that's like I want I'm going to detail
by that exactly place the story hard.

It's basically very simple the TO DO
care really corresponds to

Caylee cause points to one.

So this was key and Kiki would be one
who has so that's really integral it.

So this.

So this uses some properties are sort
of near mint cuts and many cuts.

I don't have time to go into this but.

They gave you extend the results of
banks are really who gave a very nice

representation of women cuts of a graph.

And we extend that and prove it.

So and

I like the rest of the few minutes I want
to spend on talking about this part now.

So this part is now.

Kind of independent.

As well where we want to say OK we
have a we have a course of action if

this were the case we're done.

We have a deterministic out of my way in
this case that a constant fraction of

the ideas are and of course a number of.

Near Mint cuts.

Can we have to argue that in a random
tree with most of these it would be good

to get so what does that really mean.

OK maybe I should know.

So we're not using capital behind if you
don't use something that is our lead in

and the saving that we're accounting is
using the fact that as a graph metric any

edge cost is at least
one that all the edges

of a graph cost at least one and
nor are there no very costly edges.

Because the shortest part
is no more than and so

all the edges are the cost
of nicely bonded and so on.

OK so.

So the situation simple latest
let's just look at for a single it.

Suppose I told you this of a.

The edge is in a bunch of
middle cuts came in cuts.

We want to see.

I'm in cuts on him and cuts for
the masses really doesn't matter for

now and can think of here's
a constant let's say ten and

we want to find this
problem that your T.V.

to sample from this mass amount will be
distribution of this uniform distribution.

I want.

The T. to contain even number of pages
each of these cuts simultaneously and

I want to load on this probably I want
to show this is at least a constant

if I could show that then
I'll be like I'll be happy.

That's when I'm done.

So this is really the main
problem that I'm interested in.

And why would why should you
when expect nice things.

So one thing is so let's let's look
at the indicator random variables for

a particular is that we say that those
are axes and it's a very old theorem of

Fed and we heil shows that these are
unavailable something to be associated so

in football if you pick actually say that
a one hundred F. is going to be chosen.

It's actually going to decrease
the problem of every other it right and

also commit to a host also more generally
and also implies concentration.

We can apply sure no bounds and so
on water will basically some very

nice concentration properties hold for
London from distributions and

this exactly what was used for
is a matter of traveling salesman problem.

You can apply for no bounce nicely.

So far as it's a big moral tricky
because we want some it to

be even we can't say it's between the up
to something smaller than some number

because two is good for us.

Three B.'s but again but
four is good for us.

So either I want to say it's always two.

I can't apply the range or something
like sort of one of two very precise.

So if there were for
example I could still work it out you can

still apply shown a bounce in and
we can check OK.

I want to find out.

Probably not exactly two because she
says she is at least a constant and

why is that because your expectation
is exactly what is the expectation.

Your three in expectation is
following the LP solution.

That's exactly why.

Distribution one of the reasons
we chose is the submission.

So an expected number of edges that you
put into Scott is very close to L.T.

value and
we know this cut is a mere man cut so

that means there are people
is very close to.

So in expectation you close you
expect to see two inches and

you know you are concentrated around it so
they'll be a constant problem

that you will hit the peak you will
actually get to with the way you can

actually work out the numbers and
you'll get at least a one third.

So that's a start at
least one we can get it.

Not all of these cuts are independent.

They only care of them case a constant so
I could just multiply them.

But they're not independent of course
it's ease common to all of these cuts but

they could be other ideas which are common
and it's not even clear that this

certainly were not human to exist are not
independent negatively associated.

So the question is what
do we do from here and

to do this we actually have to go
to more general distributions.

So we really want to have one problem.

Which I strongly really measures.

I would NOT going to do too
much detail about these.

Defined by looking at
the data functions and

giving some condition on possibilities.

But the basic idea is these are a big gem
of more than a class of of distributions

probably the switches with generalized in
particular lambda uniform spanning trees.

But a nice property about distributions
are there close under a lot of operations.

So what example close under
protection truncation or

even conditioning if you do some
some nice kind of conditioning.

You will again get strongly measure and

these are introduced in the recent paper
by both your brand in the link it.

So my thing is if you even if you do a lot
of these operations nice operations.

You can get.

Strongly measures and all strongly valid
measures have a negative association and

again you can apply sure no bounds for
all of these measures.

So things work very nicely and

what we really want to use are these end
up using up the strong rally measures.

So the way we do it is pretty simple.

So we know this is true by just
straight forward sure no bounds.

What we want.

What we do is condition
of this being happening.

OK So we look at the measure.

New Prime which is new condition
on that we actually get

two edges in that particular card because

because the new was strongly rally
because it was planning to measure.

So reply would be strongly Dolly
is no longer a crazy measure

you're saying on a particular cut you
picking two edges look at that measure.

But still strongly Ali what
about that measure this.

And now.

You're so.

So now basically if you look at
two cuts now I want to look at

probably that it is two
in the first part and

it is two in the second cut by a simple
base rule is just that is two in the first

part times in the conditional measure
it's two in the second quite well and

I haven't done anything I just played
baseball great the first time but I know

it's at least a one third second now but
also want to see it at least I'm told.

Why because I start so
strongly I can apply the same thing.

One has to be a bit careful about overhead

because expectations hundred
new play might have changed.

Remember why would we apply.

To get this concentration what happened
because we said our peak is essentially

to our expectation is to imagine you.

That's also true for C two but
are measured as genes from you to me prime

your condition on certain events is no
longer true the expectation would be too.

So one has to do a lot of bookkeeping to
make sure the expectations don't change

too much and we can still do this or
a constable cuts and

basically that's where a lot of
bookkeeping is done but it can be done so.

Pardon.

You have to also do truncation Yes yes.

And we also have to apply like we
can't do it for all such areas.

It's not that it isn't cost an army near
mint cuts we can actually prove this.

So we actually have to characterize
look at all such as these and

character is them and
only prove it for certain subclass and

then show that the supplies
are still large.

So we can't prove it and I don't see went
through so we don't have a counterexample

So for example we can't even prove in this
land informational if I give you an edge.

There's a chance of probably both
the imports will be will be so

even that we cannot do actually.

And I don't think so
though even that is true so.

So it's not.

In general it's just like OK but basic
idea when it works it works like this.

Mostly yes in a few except for
a few cases like there are over again.

One or two cases where we
actually end up going to four.

Because of yeah but most cases to us.

So these are kind of things I
wanted to put under the rug and

I'm not want to go but
yes this is how it works.

So it is simple it's not hard basically
But sometimes have to do bit more

bookkeeping and things work around
the edges but mostly it was like this.

For is also your number.

Yes.

That's.

OK.

But I think I should get
over the proof somebody is

basically decided we should destruct
a term and there to really parts of it.

Want to spill it after tickle the other is
kind of uses just the properties of these

lumbering reform measures.

To conclude we actually give improve
the lot of a graphical D.S.P.

handle which is still bothering me
like there is this nice algorithm.

Right.
We give and

I think it's a very natural law a lot
of as well and we've conducted is

going to work for all metrics that we
like right now we can prove that this is.

The case.

Actually I don't even know what a lot
won an epsilon I don't know off of for

example where the Sultan
was worse than foretold.

But I don't think so

we can prove anything close to forethought
because just I don't think so.

Playing around with these
probably dimensions and so on.

We can get such strong bones at all.

OK.

The other cases subsequent to our work
they were work my mom can sense them which

is give a very nice but a very different
algorithm which is fairly common authorial

and they give a one point four six
approximation for the government E.S.P.

case exactly the problem that we started
the analysis will be little improved by

a move or two in one point four four.

So the other next one problem would
be to actually just nail down there's

a graphical T.S.P. is the right answer for
third just for graphical B.S..

So that would be one problem.

The other is how hardness I mentioned
earlier is one point zero one.

And I must say this is not
very satisfactory in some.

We should really be getting a harness or

possibly even for thought there
isn't a reality gap of all told.

This paper is still I don't want to

say that some thought should be the guy
who is responsible for not doing it but

there's a nice paper I fold on this
paper but I actually have no ideas.

I don't think so.

No well not calculated bone earlier at all
but yes it's basically A.P. It's hard.

That's what it is kind of more.

Like maybe there's a sponsor and or here.

It would be interesting because
there are entirely gaps and

there's a somewhat decent
amount of theory that

has been developed to actually
take integral gaps to harness.

It's not really over that such
things can be done about head on.

Or is there a strong reason
why it can't be done.

So the sting the other I want to see is is
basically using these Macs and probably

decision on hardware distributions they
have been a bunch of successes especially

applying these hard core distributions and
using point here to structure together.

For example for a T.S.P.
like basically the way T.S.P. give this.

Dog It is not going to level again what I
want to think are there like the politest

of flaws with maximum properties we really
give give some partial progress on P.S.P.

by applying this combining the politest
of the joystick Maxima to Patrice.

In some sense I want to
interpret the result of card for

color multiclass it is also beautiful
problem which kind of combines elements

matching part of his
mathematician to be matching.

So this if one can do produces
approximation approximation results and

is kind of not quite as well there's open
conjecture for what I won't go into detail

and the problem is I think this
should be should be more and

more common we should like especially
the of seen a lot of algorithm is

a purely polyhedral but I think especially
combining with these random structures.

Even Maxima will be stuck to
give me one particular candidate

can we get improved I will transform
a form of Luke and I guess with that.

Thank you thank

you.

Yes.

So yes so yes I yeah I we tried a bunch of
different approaches but we don't have a I

would say we don't have a conviction also
how to what would be the corresponding.

Claim or what have you all so

you want to do you want to
use a cost of a metric right.

So in some sense it cannot happen that.

There are a lot of costly edges.

You know.

You're so you want to see
the edges which have nice and

they kind of hit all
kind of possibilities.

So that it's costly as it would be had.

They basically so
I don't know maybe they hit all carts.

I really don't know exactly all cycles or
something like that.

I don't know exactly what
the computer would be.

But yeah.

But it could be different
approaches this exactly.

The algorithm is there but did of this
is the way if I did analysis maybe

that was a misleading but that's another
way to do the analysis that way to reduce

one particular lead but maybe you
could play around you can increase for

the problem increase or
decrease and so on.

You could do that as well but
you know not necessarily.

But be comparable for every And
we still again a subset of.

Yes.

Well except our one could
think of say Iran or

my surroundings always
mustn't repeat on the right.

Like if one would think about
I don't want to say that but

make one could do that or for that matter.

So for example let's just do said
cover letter to max coverage for

the for that matter right for mastery
to have a constraint and to pick a set.

So I think if you say
that I'm going to do pick

the distribution side of my marginal side.

I can readily no problem for it.

My marginal.

And I have discussed and
I'm not subject to discussing.

I want to be the maximum
entropy distribution.

It will be like I did one minus
one hundred years when so.

But I don't it will be very different
again for some kind of a grounding I think

will be the kind of the same distribution
you scale everything in and so

much less

so in something that's what the fall
of paper does they try to do a comment

a little thing in something defined try
to find a tree or don't find a plea but

a bit more general structure which tries
to take into account the cost of the edges

would you pick and maybe the cost of the
little edges that you want because well.

And so they do try to do in some sense
combine both of those things together

in the first step itself in beautifully
that's how I try to think of them

but it's not.

Yes yes.

Rule your mind but I'm not sure I don't
know of one but I didn't try too hard.

So far

I'm going to time we tried to calculate
it it's small on the small very small.

Thank you.

You're certainly

very well

so.
So the LP but you say LP value

will be like No no no no no no.

You could still have a so a lot of four
cards so Lakota Indian P. solution you

could slam a lot of men because all
of the scenes are clearly to write as

a constraint to place over constant
fraction of the N.T. is part of it.

Most of the YES YES YES YES
that is true and

this is probably got a little
statement you're making.

Yes yes yes.

So only if all of the in all of
those cut you pre-prepared even

number of pages then I can actually
anomalies by two plus two.

Yes.
Basically yes.

No you're not just your after two.

Yes I could be stated also as a to get a
bill or to get going to telegraph has some

properties I consider
purely good after to go.

Yes.

OK Thank you.