Title: Line Search in Polymatroids
| Speaker: | Michel Goemans |
| Affiliation: | MIT |
| Location: | MC 5501 |
Abstract:
In
the
first
part
of
talk,
in
honor
of
W.T.
Tutte
just
two
days
before
he
would
have
turned
100
years
old,
we
will
review
a
few
(the
easier
ones...)
of
his
many
striking
results
that
are
part
of
the
foundations
of
graph
theory
and
matroid
theory.
In
the
remainder
of
the
talk,
we
shall
consider
the
classical
problem
of
finding
the
intersection
of
a
line
and
an
(extended)
polymatroid
in
dimension
n.
When
the
direction
of
the
line
is
nonnegative,
the
problem
is
well-understood
and
the
Discrete
Newton
method
will
require
at
most
n
trials.
For
general
directions,
however,
no
bound
(depending
only
on
the
dimension)
was
known
and
we
provide
a
quadratic
upper
bound.
The
analysis
relies
on
several
extremal
results,
such
as
the
length
of
the
longest
chain
of
ring
families
(closed
under
intersection
and
union)
or
the
length
of
the
longest
geometrically
increasing
sequence
of
values
for
a
submodular
function.
The
second
part
is
based
on
joint
work
with
Swati
Gupta
and
Patrick
Jaillet.