Title:
Modifying
the
Lovász
theta
function
for
obtaining
upper
bounds
on
the
stability
number
| Speaker: | Elisabeth Gaar |
| Affiliation: | Alpen-Adria Univrsitat |
| Room: | MC 6486 |
Abstract:
The
stable
set
problem
is
a
well-known
combinatorial
optimization
problem.
It
is
NP-complete
and
furthermore
hard
to
approximate,
hence
one
wants
to
get
tight
upper
bounds
for
the
stability
number.
One
possible
upper
bound
is
given
by
the
Lovász
theta
function,
which
can
be
computed
as
semidefinite
program.
In
order
to
improve
this
upper
bound,
we
will
add
additional
constraints
to
the
Lovász
theta
function,
namely
exact
subgraph
constraints.
For
a
certain
subgraph,
the
exact
subgraph
constraint
ensures,
that
the
submatrix
of
the
calculation
of
the
Lovász
theta
function
corresponding
to
the
subgraph
is
contained
in
the
convex
hull
of
all
stable
set
matrices
of
the
subgraph.
The
talk
will
give
a
motivation,
why
exact
subgraph
constraints
are
considered,
address
the
question
of
how
to
choose
the
subgraphs
to
be
added
as
exact
subgraph
constraints
and
eventually
have
a
look
on
computational
results.
This is joint work with Franz Rendl.
For
more
information
about
our
reading
group,
please
visit
our
webpage
http://www.math.uwaterloo.ca/~deolivei/reading.htm