Problem so
I'm very happy to be curate and.
Spent a very nice year and
a half year and.
So this is trained.
On and don't ask if.
I think you could come sometimes in
October or so to give another talk on and
they're very nice recent
resolve they have.
So.
Let me start with what it is this
is kind of one of our problems that
really made it into popular culture
there are like movies of the spear.
So this is the problem EVERY have and
sit is and
the one to visit all of these cities.
And once and then get back to the starting
city left from so that we were visiting.
All the cities this problem has
a very long and rich history I.V.
along the focus on the trail of and
special kisses for this.
So first of all what are the possible
distances between all these functions
between all these if you
like arbitrary distances and
your goal is to visit every city exactly
once on your tour down the problem
becomes super hard there is no constant
factor approximation algorithm possible so
the standard assumption
VICH is made in the.
Literature is that the distance is
satisfied the triangle inequality
getting from city.
As much as I think an ad.
Stop in between that some thirty.
So we can I do assume that the train will
the inequality is satisfied or bitches.
Can our salesman to visit.
Some cities more down one and
then we can basically mimic the effect
of this triangle inequality.
About this sense functions.
Like two.
Classes of the problem
which are the symmetry
Candia Symmetrix into symmetry problem
version getting from city to city G.
has the exact same cost it has the exact
same distance as the other of the around.
There S.
in the.
Spirit dike.
The dawn to assume any relation between
the two directions to make if you imagine.
A cyclist going up here can be
definitely take much longer or
can even become infeasible
in San Francisco.
And then going downhill so
if you want to schedule.
A cycle career service stand then you
definitely need to dig this into.
So what in the you can approach the S.P.
from multiple directions well.
To read Georgia Tech and
even after that has these
amazing implementation
six can solve any D.S.P.
problem on his i Phone So
this is from one of his.
Which is the you keep
crawling which visits every.
Pub in the U.K.
or almost every pub in the U K.
Pubs are not included in
this tour which really.
I find somewhat annoying.
There are but from the approximation
perspective the are looking for
accurate guaranteed approximation
Richard that is the one to
output to each whose
cost is within a certain
factor from the optimal cost so
there is actually a very
huge gap between symmetry and is symmetry
problem versions so for the symmetry
problem version I guess most of you
are familiar of it Christopher disses.
Which is really simple and
elegant one point five approximation
it obvious returns a tour at
most fifty percent more expensive
than the best possible and
this is pretty much the state of the art
for the general Cimatron problem
now there is a special case which
has received quite some attention
then we have a graphic problem instance
of you have or improved is given by
the shortest path metric of
directed graph so I don't you can.
Think of it this way like if two
cities are connected in the draft
distances one otherwise is the shortest
possible to or between them or
you can think of the problem as you have
to travel on the edges of the graph you
have to get everywhere at least once but
you can visit cities small tipple times.
So if you have this special cost
structure than this one point five
can be improved to one point four which
is the current best special bent figure.
Previous for.
Sons and.
So here really.
The game is Stu this is
this is like the main
question can be improved on this some
point five in the general case at but
be a religious fine tuning
constants to see there S.
in the symmetric problem version like for
a long time.
Constant factor was in
fact the long standing
best approximation ratio was a lot
Ganesan is the number of sit is.
Only from eight to two it's
a very elegant simple algorithm
a villa actually present
it doing that all so for
some time I think people
believe that this slogan
is The Truth in fact this is not an order
LOGAN This is an exact dubious look very
firm and
already just improving on the this and
the constant factors it bringing it down
to zero point one thousand nine log and
was already non-trivial which
was followed by later over.
Two point six to summon.
Fagan Singh and then kind of.
The most important breakthrough here was
this assert smudgy obvious Karen and
Subir image went below de law again
threshold it was only by a factor
log log an However it kind of
fell on this people that Logan
is not the final answer and
it introduced is technically
of thin trees so
they reduced A.T.'s speed to
another problem which is finding
a spare special kind of spending
tree in a graph which doesn't use
too many edges of any of the cuts and
they should that if we can get.
Tree View.
Certain thin Street should and
we can use that to get good it D.S.P.
approximations are getting there like
a constant Fintry would also give like a.
Constant factor for it E.S.P.
So this has been for a long time really.
What people have been trying to.
Do to improve results on thin trees but
this by itself turned out to be
a very challenging question.
So in this line of work like the.
Current bound is like the.
Poly log log and bound on
the integrity to get No I haven't yet
mentioned the natural LP relic system
material come in a few slides but
what the he here should is like a.
Bond that they're all this exists in
theater so you Sherm whose cost is
at most made in this factor from
the optimal solution however the proof
is nonconstructive so it doesn't actually
give you a polynomial time Magritte
this really pushes this
thin tree technique.
To the limits sound.
Like an extension of
the cut this on singer.
Conjecture turned theorem so
it's really a very impressive
machinery in despair but it's still.
Not going stand and now the arithmetic.
Constant factor approximations have been
known on special kisses which are kind of
analogous to the C.
metric setting so
there if we impose like certain
special structure than we can
get beyond one point five So
here are other special cases include.
Idea a risk on the structure of the graph
like if you have a plane or a graph or
more generally a boundary genus craft and
using this think again.
Obvious Karen and.
Give a constant factor approximation and
then like the other
results which will be directly related
to my talk are for nude weighted
graphs Now what is a node weighted graph
so it's a simple extension of just
directed graph shortest path metric
we have like weights on the nodes and
the cost of an edge is the sum
of the width of the points.
So.
When Sun introduced a very
different approach from the thing.
Explain later on in more detail using
this approach the same course managed to.
Do it to give the constant factor and
before two different Actually it's.
Now you have imagine you have a shorter
spiral symmetric in a graphic you can
have like heavy edges and light edges and
only these two classes but
that kind of seemed to be like
the limitation for for some point until
this result they're building like
a mini on that Nic of this first paper.
Managed to give a constant
factor approximation for
general if the speed no
restriction on the course and
the result there's this guarantee
is compared to the optimal solution
of the health care products ition which is
the standard red exception to a problem.
So I'm not going to tell you at
this point what our constant is you
might have already looked it up but.
If you make it until the end
of the talk you will see our
beautiful if slightly over of it constant.
So.
Let me give you like a formal
description of the problem variant
looking at well this is really
equivalent to be of stating the.
General metric speed in graphic
terms are inputted directed graph.
And we want to find a minimum to.
Now say again the Tories like warp
lose more visiting all the sit
is and it is a useful observation that.
What matters from this story if you
just look at it as a set of edges more
precisely a multiset of edges because you
can use the same measure multiple times is
that it is already Ariane the Indy
agree and the out degree of every node
are equal because the enter every city the
same number of times as the leave it and
the other is that it must be connected so
once you have connected a Larry and multi
set of edges you can all this convert
it into a war is a simple exercise.
And then.
Also use the concept of a sop to work.
Yes this is.
For the to correct this is a sop to
research to run a subset of the vertices.
Are serious a little example
the have this very expensive
edge which is one hundred and
other cheap edges hanging around.
This is the optimal D.S.P.
to worry it manages to avoid the expensive
of every do have to cross this.
While.
One can easily check that.
Every vertex like this says in
degrees three of degree three
degree one zero degree one and you can.
Simply convert the thing into two
were visiting all the cities.
Right so let me now introduce the.
Natural relics which is was
given by held and carp.
We have a variable X.
E.
for
each of the edges of the graph and the.
Integer solution this is supposed to mean
the number of times we use
the SAT in our mall to set.
So we want to minimize
the cost of power at certain
it should be non-negative vector and
there are two sets of constraint
the first set of constant is the.
V.
denotes the set of all the edges and
tearing down or text and
out out the set of all edges leaving the.
Two fractional there you should be
equal and then we have what is called
a sup to rally munition constraints of the
one to make sure that the two doesn't get
stuck in a certain part of the graph
it makes everything connected so
what it is is that the top all X.
value.
Set of.
Being a set would be at least two now.
If you have worked with this
session before you probably looked at
it in a slightly different way than.
The thought all and
directed degree images the set of
incoming plus the set of outgoing edges.
But and then the standard
formulation would be interested.
Said that the acts of the incoming
should be at least one.
However if you just think about it for
a second these two things are in
fact equivalent because if you have
the eye Larry and constrained and
two every said that thought all in flew
equals that thought all out really the X.
of the delta in equals the X.
of the doubt out there for
imposing this constraint that the.
X.
of the delta is at least two is
exactly the same as imposing that
in degrees at least one which
means that the degree on the components
sets at least so this is actually for.
Just convenience of the arguments we
somehow find it easier to work with the.
Do all of this program OK So again.
This is one of these L.P.'s which has an
exponential number of constraints of this
first set is sort of harmless it
just one questions for each node but
the second set is a constant for
every subset.
Can I just solve it in polynomial time
using the method because we can officially
separate over this constraint or
can actually find
compact polynomial size formulation
which is equivalent to this.
So D..
Well.
What we know about the approximate
realty of it E.S.P.
is that it's approx hearts but.
The best result is like one point or
one something.
Very small that is known about the health
care products session that the integrity
to get is at least two so
if you want to use the health car.
For your average thumb then
the best you can hope for
is Stu But again like getting anywhere.
Really challenging a new.
Integrity gaps are known as far.
So any questions so far.
So.
This is actually a useful
overview of what are the factors
at play here so we want to find it E.S.P.
image is an integral vector of
each is connected that sits
here in the middle Indian intersection
if you just stick do all of these.
Then we are in business
like if you just look at.
Connected but
drop integral it didn't it's exactly
the health care products ition if it drop.
The constant but keep integral and
connected then it's the minimum cost
spending tree problematic and again so
very efficiently if we drop connectivity
but insists on integral and
I Larry and then the cycle cover
problem which is basically
a minimum course not for a floor problem
because again solve that fission.
So if you want to solve it E.S.P. Well
you have to start somewhere you need to
relax something here and then this thing
she approaches basically by relaxing and
condition it insists on starting
with a spending tree however
you need some special structure on
the spending tree in order to be
able to fix our area city later so
this is one possible approach however
what we now use is actually relaxing
connective it is this is very
much in line of it like this.
Is the.
Time I'm going to start to explain this
log an algorithm because that's kind
of the starting point of all our arguments
so just out of curiosity who has seen.
This before.
OK so not so many is so if you know
this is actually a very good take home
message from the toxic if you don't
understand this like rather a complex and
intricate algorithm they have but
do you understand how
this log an algorithm is working
a thing that's already like a.
Very very.
Very Good Thing to take home.
So what we start is.
Find a minimum with cycle cover so
in terms of this LP We have seen
that means that the sub two of constraints
would only be for the single atom said So
you expect every node to have
indeed recall the out degree and
that every nude must have
at least one unit of flow
going through it so if you just look at
these conditions it actually becomes.
Feasible circulation or a minimum cost
circulation problems to the way you and
imagine it is that you believe that every.
Into.
Yes.
Yes yes.
So you split into the incoming and
outgoing edges and boot and
between the two and you impose
a capacity constrained between them so
this a so you sent to dis map spec to
the origin or graph which has again.
In degree the of degree and the degree of
every vertex is at least one if you think
of an integer solution to this
problem it will be exactly and
set of edges covering all vertices of
the graph which means that you have.
And that you can always
decompose into cycles that is.
Pressing for.
A cycle cover him in Soviet have
set of cycles which altogether cover
every vertex in the graph and.
This set of.
This it can.
Find definition Clee via minimum cost
situation flew under a thumb in fact since
it is a relaxing of the health care
products cost of the cycle cover via be at
the cost of the optimal solution to how
the car service started this cycle cover
it can actually contain some
overlapping cycles as well but
of course it can end up not being
connected so if it's connected then
we are done if it's not connected them
basically what's happening is that we
tracked all these components
the OP didn't hear.
And now we get a smaller
graphic like naturally the.
Distances from here today and
now we want to find like an X.
cycle cover on this small or
graph and again this is a B.
a set of cycles which.
We find another color.
So this next cycle Coverdell in this
case we just have three vertices left so
there is no other way than
connecting all of them together and
now it is to cycle covers.
All together they are connected and.
They are Lariam because it
is a union of cycles so
now this gives us in this specific
example a tour which is like
at most twice the cost of
the core products ition But
this process could go on for longer like
you can than just construct this next
set of cycles again decrease the number of
components again find a cycle cover and
some but what does happen here is that
every cycle has length at least two so
with every cycle cover you
decrease the number of components
by a factor two and
that's where this to be dubious and
it's coming from and
various kind of did this seems like
overly pessimistic that every cycle
of length doing diverse still like.
There is no obviously improved
disagree from event to decreased.
It to some smaller constant times again.
OK so.
There's a six ounce again so so
what we're going to do this.
Prudish Beatrice first given for
the node with it is.
Is to somehow strengthen this
cycle cover technique to defining
a problem called local connectivity it
E.S.P. but let me let me start with.
The Nude bit it probably is.
We have like some nude weights or
potentials age which is a.
Negative number on every vertex and
then the weight of every edge be a B.
the sum of the weights of the two
endpoints this is slightly different but
equivalent from the way it's
originally in the paper but
what is kind of annoying
notable property of this
weird function that it is symmetry
like if you have an edge between U.V.
and then edge between vu
they have the same cost
now of course the difficulty arises
because you don't have a symmetry grab for
better Fergus's you can have just one of
the but not the other so that's that's
why I like this is done get confused by
symmetric form of the cost function so
it's only valid for the edges
which are included in our impute.
Directed graph.
So what this local connectivity eighty S P
problem is which I will define
later during the talk is sort of.
Operate with cycle covers but
the cycle covers must satisfy some special
requirements they must connect some local
connectivity is of an input partition so
the very exactly what this problem is but
like there is a black box reduction that.
If we have something
which is called an alpha.
For local connectivity it is a speed and
there is like a nine are far
approximation for general it so
this off it is something like an AFA
proxy mission algorithm but it's
different terminology this is kind of very
analogous to proof that if we can get like
all of us in three then we get an alpha
approximation for it E.S.P. a similar.
Seemingly simpler problem and if we can
solve it then we can also solve it E.S.P..
And.
He.
Follows.
Well he gives a twenty seven
approximation algorithm for
node with spin you can see from the
numbers that this is by given three light.
For this local connectivity it D.S.P.
in node instances
now this reduction here is
General this is valid for
arbitrary cost functions however if.
If you look at the node with it it is
then this really becomes like a simple
network flow problem to implement
this three light algorithm but
then what remained to
be the challenge is to.
Implement it.
For for general D.S.P..
And what we did in our previous paper and
Yacoobi is the actually implemented
constant light algorithm for
the special case than edges can have two
different kinds of course function and
that was kind of a really
really tough work to get there.
In some sense technically distributes
paper is more difficult than.
This one for generally the S.P.
So what's happening here is there is this
long sequence of predictions
in the paper but
like the the overall
idea of each kind of his.
Greedy and here is that we.
Just jump on the problem and try to
implement this local connectivity it
E.S.P. for the input instances first
sort of tame the input and reduce it to.
Something simpler first
misstep here be to irreducible
instances than something
called vertebrate.
And on this vertebrate pairs
have like a rich structure
which enables us to implement this
constant light for local connectivity.
So it will not like go through all
these steps in the reduction of
first started the very
first which just reduces
general it E.S.P. to it E.S.P.
of certain special cost structure
this is basically just using L.P.G.
Well it is this this is kind of.
Terry.
And then I will.
Jump to this last part try to
give you some idea of well
first of all that this local connectivity
it E.S.P. problem is how it is implemented
simpler nude with it case in less
previous paper and how do we use that to.
Implement it on our so-called vertebrate.
And then if time permits give you
some details about this intermediate
should auction so like these intermediate
productions are like fairly.
Natural.
Elementary like theoretical
arguments compared to.
This.
Approach here really just like very common
at Oriole techniques the only way around
the fractional so you should be solving.
Flow problems.
So this.
Is a bit bit long but I would say that
like local the each part is fairly.
Not so difficult so let me let me
start fit this first part very.
Calm there are instances of
weighted instances even though.
According to Dick leapt on I
mean only it's not legal but.
Yeah.
But only for DOS to stay on to.
Yes exactly so I guess you have
a brief dispersed reduction and.
You're.
Free to free to leave but
maybe listen a bit to the last step.
So what I did here is right thing to
do all of the health care products
recall the health care of
her accession every vertex.
In flu and outflow and
every subset of dirt.
This is must have at least
two units going in and out.
So the do all it has stews sets of
variables we have the of for these.
No degree constraints and we have wise for
the subset concept from life or just.
Yet I haven't defined that
like come in this last part.
Yes a local connectivity of the A bit
like a different problem so
there is this like reduction.
Saying that if we can give an alpha
to this problem I haven't yet
defined for
you then we can solve the D.S.P..
You get there let me let
me finish it dispersed
by Stan that's the next
thing I will tell you.
So what are the constants.
We have a variable for the vertices and.
The vertex subsets and we have
a constant for every edge for every.
Vive values.
Vich are crossed by the surge Bloss
half of the starting point and
subtract the up of the end point and this
should be at the cost of this edge and
our objective it has zero for
the Alpha and a factor of two for
the sum of device again we can
solve it in time what is kind of.
Less obvious fact is that one
can find an optimal solution
such a values supported on a family of
sets or by lemon or family I mean that for
any to say they are idea destroying two or
one contains the other.
Sprue prove the existence of
an optimal solution is kind of
simple uncrossing argument you can
see that if you have a solution like.
Pairs sets of pairs violating them in
their IT TO YOU can replace them by
the symmetric difference and
get something better now if to get a
polynomial time either it's that's kind of
a non-trivial resolved by Carson
of to make this uncrossing
algorithmically efficient but but we have
do have such so your chance of evil.
Slammin are a family of sets.
Only supported by.
Based on.
Really deep primal dual slenderness
conditions idea reduce
the general speed to.
Like a special.
Class of.
Problem instances where the cost function
is defined based on the jewels so
what let me
write on the board are instances of
abuse and that's what we threw out.
So we have G.L. X.
and Y.
so here G.
is a directed graph we have L.
which is a lemming or.
Family of subsets of.
So we have X..
Which is a feasible.
Health Card.
Such that the X..
Exactly equal stew for
Annie in my laminar family.
And they also have that X.
strictly for city for
any edge in the graph.
And why it's like a set of.
Positive teachers on the laminar.
A case of it we have this Stoppel of
four things and this will define us and
in used with function so
the induced with functional fan as U.V.
The R.B.A. there are some of use.
This crosses.
So let's just see an example so
here this is like my lamb in our
family it may contain sets which are like
seeing letters like distilled on here but
like the more interesting part
is the non-singing letters.
And then for every edge we look at
all the values it crosses including
the endpoints if that's in
the family like here it's four plus
twelve plus five plus four all
together twenty five for deception.
So.
What this really captures this structure
is like Primal the wall slackness.
Though the way we can
reduce our arbitrary input.
To such instances is kind of starts by
solving the health card which gives us
an accent gives us a dual vibe which is
supported on a laminar family then we
did it all zero actually is for all.
Remaining edges which have a positive.
Value.
They must have equally
to do all constraints so
we kind of have that this sum of device
crossed my decide blasts are for you.
Equals the W.
off you know all of you need to do
doing this here to make
the office disappear and then.
The simple observation is that
if you take our cost function W.
and like shift it at every
notes of you have a.
Value of far.
Have renewed you and
then we replace a few V.
by W.
a few of the minus for you then the set
of every hour LARRY And so you should
remains the same because like every
vertex has the same number of incoming and
outgoing edges of
you has a positive sign on one negative
on the other they cancel out so
this makes the our thoughts go away and
then we really get this this W.
prime this equivalent cost function
is exactly used cost function and
then the rest of the conditions
again like that every.
Set in the family which is in
the support of the war must
be tied that's all such
a simple primal was like yes.
Exactly so that's that's that's
kind of the motivation for
this if you look at
the special case that L.
is just a single at Turnstone in that the
weight of every edge is the sum of the two
and buy ins in fact that says something
even stronger because we also assume that
whatever has a positive vibe
value must also be tied which
must have ANY degree exactly one which
you know move in and assume some kind of
what we do here is to take like structured
generalization of the node weighted
instances ie don't work with arbiter.
Because functions but like that cause fear
be exactly controlled by disarming our
family and
we kind of try to reduce our family to.
Looking the same as the new one so in
fact that we are to be the motivation of
these intermediate steps but
I think before the bridge
at least want to tell you what this local
connectivity is Spears because of that.
Solution.
It will be under support of X.
Yes yes.
Kind of iteratively around in
a certain frame for this solution X.
and that will become my
final interest solution.
Yes.
So let me read you let me first
introduce like this concept of
vertebrate pairs which other.
Terminology Dick was making fun of.
This is actually a pair of an instance
an instance recall is exactly
what I describe here bloods B.
which is called The Bag it is a sub
that crosses every non-single at and
set in I so
what we do in this series of production.
Like start feed our input instance
the reduce it to a spot and
show you a smaller instance than in
the smaller instance we can find a set off
edges which like does much of the job
of what one would expect from.
D.S.P. two or so
somehow I didn't initially is that these
non-trivial sets in the laminar
family are the ones of each
mass up our cost function from
the nice node weighted one.
And this somehow have to
connect like our two or must.
Cross all these sets but
I already have something this bag does
connect them throughout so
that's very we'll get and this
is very we'll solve the local connectivity
images the following problem so.
We have our stance and
we have a lower bound function.
Assigns a certain weight
to every vertex in
the graph which sum up to the fractional
optimum of the health care for
use in the simplest cases in the node it
is something actually that's adverse for
all of this lower bound function via be
exactly the total fraction of value and
touring that the total cost of.
The fractional energy centering the set
exactly sum up to the optimal solution so
this is kind of the local
budget of this vertex and
then be defined as lower bound
function it's up to us to define but
once defined and
the input to this local connectivity.
Partition of the vertices
v v v v to the K..
And we have to output and set of edges
which connects each of
the sets in this partition.
An important constraint
on the cost of the sets.
Namely that every component is able to pay
for itself from their budget so what's.
The weight of the take a connected
components are like in this example
I had to connect it components this
first one connected through V three and
then there was this other van connected
the four D.'s two components are not.
To each other so for
each of the components the want to see
that weight of the edges
used in this component
should be at most of the times
that taught all lower bound.
On the edges on the vertices
on the components so
like all of these components have
their lower budget sit the budget
sitting in a vertices inside a company and
they can put this money together and
that should be able to afford paying for
this company.
So let me just say two remarks first
of all this is a relic sition of it yes
because if you happen to be so
fortunate that someone.
If we have our fire
approximate algorithm for
it E.S.P.'s suddenly can all this output.
Speed trivially through every set in.
The partition and well approximate means
exactly that the weight of the solution is
at most of the times the optimal solution
but the optimal solution is a thought or
budget of four vertices so this is why
it's kind of a relic system because
now we don't expect that
to be connected so another.
Special key is if this input
partition is like the.
Individual single atom vertices
then you get back to this.
Fuel The problem we are looking for
a cycle cover right we have
we want to find a connected event to
find and I Larry a set of edges which
crosses every single at and
sets that's exactly right looking for
a cycle cover and then the cycle
cover if you define these fractional
with the fractional contributions
here exactly correspond to.
Get that for four from the flu so
your sense of what we're trying
like Sirius that we can like.
Very disorder call like arbitrary
partitions which occur in the algorithm
and then like instead of.
Like this free Scobee are to my furious
kind of a naive version of doing this like
first to start with the singer and then
we look at the components the opt in and
the need to connect them but
one can do this kind of more
clever by and down at the like the.
D.S.P. so usually a be a contact
donation of several So
you shuns fiche one obtains from
these local connectivity so
your chance but I don't want
to go much into the detail of.
Them.
Yes that's what we get for D.S.P. So
if we have like an artifact or
here like this factories.
Like a hundred nine hundred
approximation for it to be.
So I guess this is like
a good place to start and
whoever has seen enough so
let me just show you.
Have seen this first by now but.
Tell you is first for
this local connectivity at the S.P.
how this can be implemented for the node
bit its special case if it did and
then I'll explain how this bag boon
think helps us to be implemented for
our gears and then I guess I just
mostly skipped the intermediate.
Steps So
that's just have a few minute break here.
Find a lower bound of every vertex it's
their local budget twice by a few.
And if you remember the objective value
of the do all these some of this nicely.
Some of the lower bounds
exactly do all objective exactly because
we only have Vice on the sing that.
Gives a no or partition walks in and
what we do is we modified the graph and
the fraction also use an X.
to opt in.
An integer to obtain a circulation problem
and we'll solve that circulation problem.
So like in if even a virtuous looking for
a cycle cover very rigorous need
run unit of flew through each of
the vertices then we could have like split
this vertex into two like a lower bound
van on this vertex so that's what we.
Kind of try to do here now if my.
Sat so let me cheat a little
bit let me assume that
the input partition only consists of sets
which are strongly connected in the graph
there is a path inside
between any two vertices so
that's an assumption you can on this
make you have an arbitrary partition.
For each of the classes you can look at
the strongly connected components and
then if you're seeing
component than like any.
Set of edges which crosses dissing
component must also cross the entire sets
so we can just get the stronger problem if
we replace them by the stronger connected
them in Seville like if
one of these contests.
Happens to be a tight.
Then I can just construct this tight
set into a single single vertex impose
a lower bound on that single
vertexes solve my flow problem and
then when I have to map it back
to the origin or craft and
I can just blew it back there because I
assumed that the set is strongly connected
and I can like connect up
to two endpoints inside so
that's very much what we do even if
the set isn't tied that is like the in
degree is more than one so what we do V.
take like.
Proportionally one unit of
the incoming and the outgoing flu.
So here like let's assume the total
of two units of incoming fluid so
we take half of our flow and rerouted to
another tax sitting outside somewhere.
So right now I like the routed like
the half of all the incoming and half of
all the outgoing to our new vertex now.
Want to keep the whole thing so
what we do look at like
cycle decomposition of our original so
you are using this
cycle decomposition become proportionally
decrease everything inside us at
the not even needed so
if resulted like half year then if.
Everything inside then I still
have an idea and so you.
So no.
I we'll have a situation problem
there I impose a lower bound fan
here and
on the vertices inside I actually just.
Had a positive value I impose
an upper bound one so my current.
Fractional acts or what I got from
the fractional left through this map.
Beings that we have be a feasible solution
of this problem of course that moves
the optimum.
Therefore because of the integrity
of the flow problem we
have an integer solution which
as that moves the same cost so
what this integer so
you do to be a visit all these vertices.
And inside here like.
The in degree of every vertex
which had my value positive one.
So what we do then mapping
back again like I had.
I have like exactly one
unit coming to this.
Coming to the Vonage going out
I may have something sitting
inside here I did this set me.
Beyond not be connected so
now I'm back to valid they came from.
Then I use strong connectivity and
just an arbitrary power of
connecting these two inside so
that we are give me an area set of
edges in the origin or graph which.
Which connects all the sets in my
partition so that the cost and
most of fractional cost of the fraction
Shanel optimal solution I started with
OK So very good so what we have to very
funny is that this local connectivity
it E.S.P. property holds meaning that
whenever I take a connected component
it start all the way it is at moves to
times the lower bound of the vertices.
So here the key observation is
that every vote every vertex had
a positive value has indeed
three at Moose two so
why is that true so
I had the upper capacity.
Consent for every such vertex
which was at most one so in my so
useful on the modified graph
degree at most one and
when I add the spatula
is inside asserts that.
That's a path that degree
at most one to everyone and
it can only happen because of the path for
the set you are sitting inside so
that's why we have in the stew is
the same as the I would degree it and
then we are in business because then I
look at the way it of a component so
some of the use of the two endpoints
because of the cost structure of you.
And that is then well.
Every.
Vertex contributed to for the incoming and
two for the outgoing said most four so
now the way it is and
most four times the sum of the wise but
the lower bound that's exactly twice
the sum of the lies so
this gives a thumb it's actually.
Three light again we are using here that
it's even more special because vertices
that positive by have in degree exactly
one so is this like roughly a killer.
So again we kind of what
we do is like in this.
Fuel this we define circulation problem
forces flu going through each
of each of these sets and
we can even impose that the degree
of every verse to every one for
a Texan are so usually set most do so
basically like every vertex can be for
all the incoming and outgoing edges
within a factor two So what we do.
Now.
The have this local connectivity it E.S.P.
and we have a vertebrate
pasa let me remind you what this
vertebrate Perry is so I have.
A lemon our family and
let me explain the argument
on the special case when our Lemon our
family only contains singletons and
one single non-trivial
family non-trivial set so
this is like just one large above the Nor
do it it is but it actually
captures all the mean ideas of
what's going on under general so.
Some of the press something goes.
On.
Right.
So this is my non-trivial set as and
the backbone of us and
I Larry a set of edges which went through
every nontrivial set in the family which
in this case just means that
I have an eye Larry and
at certain age crosses this OK so
that's not too much to ask for a victim.
Of that property in general so now my
cost function is almost like a nude it
cost function so for edges which
sit I don't completely inside or
outside the search we just it's
of the two endpoints and then for
edges crossing the set we
also have to add this.
Value sitting on the set.
And now.
We defined a lower bound so the lower
band function be a lesser see it.
The same as in the node of it it is for
all that this is which are not incidental
to the backbone and on the bag.
The red equally distribute
the weight of the backbone
Now I assume so that's what came from
the previous reduction stems that this
on its way it is like in the same
ballpark as the optimum their use
then the total cost here is and
moves the optimum from the first and
most constant time to man from the second
term so this is like good enough for us.
And now.
There is only one single step there
I've used the spec so it intersects
my set which means that there must be
like a little ass sitting inside the set.
Such that which is on the backbone so now.
It is like a simple.
Cut argument that.
For in this set I also had as
a property of my instance is that every
that the set has exactly one
unit of incoming flow so
then this one unit of incoming
flu can be routed to this tax S..
So that's like obvious true like
if you have like a hard carp so
you shy meaning that every set has
incoming degree in coming through.
At least one and
it's an oily Rian solution.
You can take any set which has
exactly one unit of incoming flow and
you can like Sandy it.
Inside a certain by sending I
mean that I used a fraction
of their use as the capacities.
Sort of.
Don't want to run.
So what we'll do.
Using this little flow is the following.
When I create my circulation instance and
this involves some even further
splitting of the nodes or
SCIRI arcs and all that but all this
is about is to make sure that in the So
You shine I get from my circulation
problem every edge which enters
this set us must ultimately
reach this little S..
So again like I use a construct
like a circulation problem vitriol
output a set of edges which a.
Cross every cert and B.
whenever it.
Through my special set then it
must eventually reach the backbone
so if I have these properties then
I can claim that this gives like
a constant light approximation and
so this is kind of.
Like.
The analysis that works here is basically
works for like the general let me know if.
So the idea is that there
are really in this solution I get
two kinds of components some of the mass.
Which I don't completely stay inside or
completely stay outside for
all these components locally everything
looks like in the nude with it
is because their cost was just
why the use of the two endpoints
I can like verb but in repeat
the same analysis we had previously.
And then there will be one
giant component so this is the.
Deal in my so you Shannon that's something
I forgot to say all this through in
descent tire bag Boom be so
the way I start I
include the bag and I include
the solution of my circulation problem so
having the backbone there grant that the
whole thing is in the same components or
this is now a big giant component and
I argued that
this trend component also has this
property that it's able to pay for
it it's law call lower
bounds it's able to pay for
all the edges and this is like
a very kind of rough argument so
what we do here is to say
that both the weight and
the lower bound be like bounded
by the optimum so the lower bond.
Of this component we
have been abounded by.
A bond of backbone and
on the backbone be distributed equally.
The cost of the backbone between
the verticity lower bound.
Term here the weight of the backbone
vitreous that it's like
omega of the optimal solution.
So it's at least a constant
factor stands the optimum and
then on the other hand the upper
bound the weight of the tray and
component by the weight of the holes
what we get as the whole so
you shine is really like it's
the backbone plus the cost of.
Circulation so you shall we.
Be again by the flu optimality at.
The fractional So you thought all.
This is really a robust bond that
like the total cost of this giant
component is at the cost of everything and
actually the lower bound of this train
component would be able to pay for
everything so
that's why this giant component will also.
Satisfy this of a light property.
And so
this is this is why our solution is.
For light so again I didn't give
you too many technical details and
I'm sure like if you haven't used
this sort of like circulation
constructions before then it's not easy
to follow but kind of fillers a few of
the whole thing is that like everywhere
if I don't cross the set than
everything looks like in the nude
with it it is now for the.
Edges which cross the set as I
don't have a good control on the.
On the costs of the individual edges but
they can all too.
Globally handled them by using this bag.
Does all the coverage which is needed for
these certs and in my local connectivity
at the S.P.V. we'll make sure that
every edge which crosses one of.
The sets in my family be merged
into this company and so
that's kind of the high level idea here.
All right so.
This is what we did.
Is this final step and
then there are these missing links going
from the laminar live it
incenses to vertebrate pairs now.
Since I've prepared for
a longer time to optimistic and.
Many sites here Richard Beatrice
relief fast forward through and
just kind of give you an intuition
where this backbone is coming from.
So.
What is this year Reggie civil instance
I have this lemon early waited
in stance given by this big
family of vertices idea all kid
is all these are singletons we are back at
the nude waited case nothing to be done
otherwise we kind of try to do try to
reduce our instance by contracting so.
We want to replace it by like the usual
like graphs theoretic contraction
into a single vertex a question is When
can we do that when can we take a solution
to the contracted instance and
map it back to the original instance.
It's kind of if you think about this for
a like what it really matters is that
you have to take connecting coming and
outgoing and points in a certain
how expensive that could be
then you define different
things give different bands or.
Get to something.
Then the instance where
like New such contraction
is seems easily possible and then we have.
The result which shows that if you
can give a rule approximation for
irreducible instances than we can give
an approximation for arbitrary instances.
So the punchline is that we only need
to vary about instances which are.
Very couldn't furder
get any reductions and.
Contractions school back and forth but let
me just explain what like the intuition
behind D.C. registerable instances
are invited to give us the backbone.
So remember this backbone was a sub
crossed every non-single at onset in
mind I mean our family and then so
for an irregular cert this
comes from the previous.
Parts of I haven't gone through but the I
wanted to illustrate it from like this
puzzle from one of my children spooky
there is all this this puzzles and
this guy Fred has to get from
here to the pirate MIT and
there are like many paths going but
there are all these like spiders and
scorpions and other like this
Earth things in in the way so
you cannot actually get anywhere but
somehow or
in all the solutions you really need to go
through the anti your picture almost So
that's not like any read use of all the
instances we have a pair of this is such
that the shortest path going from one
vertex to the other is almost like.
A path A.T.'s speed like this it's almost
everything on the way between the two so.
You know the interesting part
is of course like if you have
normally like an almost D.S.P.
so you should visit smooth things but
not everything that you know you cannot
like easily extend it like D.S.P. It's
really an all or nothing thing but what we
can do here is kind of the we can like
in terms of this do all Squinty five or
disorder this will give
us like inside every
set in our Lem in our family if
we all get a path which visits.
Like most of the weight of sets
in which live inside this.
And then what we do.
So and
this is like the final thing I wanted to.
Start we had.
Our irreducible instance and
we take the largest sets in the family so
now and me contract all these sets into
a single atom vertices it's an irreducible
thing contraction doesn't work
by like we cannot reduce our
problem to dismantle their instance but at
least this gives us something it's a node
weighted instance where we can use
Sansa It's all there to get our.
It E.S.P. to work now what we
do movie map this speak to or
to the previous to the original
graphic this big family and
then like what we can do is exploit
this structure that there is
this pair offered this is which
are really horrible to connect denies
like kind of complimentary thing is that
if there are no such pairs in the sets
then Demick can contract these sets and
reduced instance if there are such pairs.
Then we can like use them to get something
which starts looking like a backbone so.
Like let's say entered here and
go out on the outer And
if this is Fred and
this is the pirate mid then I.
When I go from one to the other I visit
most of my sets in the family even if
I would end up being lucky and these guys
have some short path between them I can
force myself to be unlucky like now here
is Fred here's the pirate Maiden I go to.
Their den I go through my
long visits every thing and
finish it up so
surveyed all these connections.
I get the receipts like.
Most of the sets in the family and
by most time mean by.
Seventy five percent of the total
weight and then what we do.
For the rest so
I now have like still a few
set sitting sitting here
which are not crossed by
the time not don't have a bad bill and
yet but luckily the total wait
to see if I restrict my instance to
dis little instances I can get inside
they're taught all do all optimal their
use would be at least a constant and
most a constant fraction of the total
do also therefore I can kind of do
a recursive algorithm I find
a little speed it E.S.P.
to re inside each of them and
then I contract them and
then I contract the i get i do
get a backbone because now my.
Visit every Sat in the I mean our
family of each is not a single.
So that's kind of.
Did.
And of this story is so
let me just wrap up what happened here.
So there was this first we.
Really trusted Elpida Well it is
what we learned from there and
that's kind of by itself kind of.
Like an important step because it gets
you in the right mindset we don't have
arbitrary cause but we have this lamb in
our family that guides of course then.
The try to reduce to slam in our
family by a series of contractions and
a set of US contractible if between any
two vertices the shortest path is not so
bad as in not visiting everything so it's
a distance us to read double instances
in irreducible instances we can
construct these bad things vitriol and.
SOP to visit every
non-trivial non-single at and
sat in the I mean our family and
once we arrived here this is
like the riot police to play out
this local connectivity it E.S.P.
card because this backbone
kind of does everything for
the coverage retrieve wouldn't be
able to do just using the new do it.
Like one in our previous two
different kind of impatient and
tried to implement this
local connectivity a.
Very beginning and that kind of something
you can if you really want you can do for
two actually it's but that's very stops so
that's but if you get this better
structural understanding then luckily
this local connectivity D.S.P. works out.
So for Deuce who remained here you
have the privilege of seeing
our beautiful Khan stand.
So you can.
In the paper event.
The kind of the simplest
analysis even trading off like a.
Fact.
If you just tighten some screws you can
bring it down to like three thousand
if you open up these books from.
Previous paper or the local connectivity a
D.S.P. and start working directly you can
bring it down probably to a few hundreds
or can bring it down to a few hundreds.
You are bound.
To resteal quite some gap between
them in fact I don't think
this true trunk can realistically get
something under one hundred but you know.
All our protests are still in the game
there is still the thin she conjecture
which is by itself a very interesting
one there are there are proper
problem variance such as the bottleneck
at D.S.P. very You want to.
Minimize the maximum weight which
is needed to a defined at D.S.P.
to repair this process and
for about three inches could.
And yes in terms of.
General T.S.P. picture there is also.
The question of getting better than
one point five for symmetric D.S.P..
For it D.S.P. if you are really
just trying to bring down the constant
to something non astronomic.
Just have a finals.
Of.
European Research Council grant it's not
quite true lated to this than it's about
scaling methods for discrete and
continuous up to my session.
For five years and I'm looking for post
docs and students if you are interested or
know someone who would be
interested please start to me and
you can look it up on my website so
thank you very much.
When.
You just get.
Yes.
That's a integrity to get premiums.
Probably with one.
Yes yes yes exactly like because yes so
or like elementary steps.
This big.
Stuff is ultimately like rounding
fractional first interest.
Yeah thank you.