Title: Separating Maximally Violated Comb Inequalities in Planar Graphs
| Speaker: | Hao Sun |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
This is a reminder for our next (and last for the term) meeting that will take place on Monday in MC6486.
Door will open at 4:15pm. As usual we will have 15 mins for socializing and for eating pizza before the talk starts (at 4:30pm sharp).
Abstract:
In
this
paper,
we
consider
the
problem
of
finding
violated
comb
inequalities.
If
there
are
no
violated
subtour
constraints
in
a
fractional
solution
of
the
TSP,
a
comb
inequality
may
not
be
violated
by
more
than
1.
Given
a
fractional
solution
in
the
subtour
elimination
polytope
whose
graph
is
planar,
we
either
find
a
violated
comb
inequality
or
determine
that
there
are
no
comb
inequalities
violated
by
1.
Our
algorithm
runs
in
O(n
/
MC(n)
)
time,
where
MC(n)
is
the
time
to
compute
a
cactus
representation
of
all
minimum
cuts
of
a
weighted
planar
graph
on
n
vertices.
The
presentation
will
be
based
on
the
following
manuscript:
http://www.jstor.org/stable/3690533
For
more
information
about
our
reading
group,
please
visit
our
webpage
http://www.math.uwaterloo.ca/~k2georgi/reading.htm