Lift and project systems performing on the partial-vertex-cover polytope
| Speaker: | Konstantinos Georgiou |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5479 |
Abstract:
We
study
integrality
gap
(IG)
lower
bounds
on
strong
relaxations
derived
by
various
lift-and-project
systems
for
the
$t$-Partial-Vertex-Cover
(t-PVC)
problem,
a
variation
of
the
classic
Vertex-Cover
problem
in
which
only
$t$
edges
need
to
be
covered.
t-PVC
admits
a
2-approximation
using
various
algorithmic
techniques,
all
relying
on
a
natural
LP
relaxation.
Starting
from
this
LP
relaxation,
our
main
results
assert
that
level-$\Theta(n)$
LPs
or
SDPs
derived
by
all
known
lift-and-project
systems
that
have
been
used
for
positive
algorithmic
results
have
unbounded
IGs,
where
$n$
is
the
number
of
vertices
of
the
input
graph.
Our
results
show
that
restricted
yet
powerful
models
of
computation,
associated
with
lift-and-project
systems,
fail
to
witness
(in
poly
time)
$c$-approximate
solutions
to
t-PVC
for
any
constant
$c$,
and
for
$t=O(n)$.
This
is
one
of
the
very
few
known
examples
of
an
intractable
combinatorial
optimization
problem
for
which
LP-based
algorithms
induce
a
constant
approximation
ratio,
still
lift-and-project
LP
and
SDP
tightenings
of
the
same
LP
have
unbounded
integrality
gaps.
Most
importantly,
one
of
our
main
contributions
is
that
we
make
explicit
of
a
new
and
simple
methodology
of
constructing
solutions
to
LP
relaxations
that
almost
trivially
satisfy
constraints
derived
by
all
SDP
lift-and-project
systems
known
to
be
useful
for
algorithmic
positive
results.
This
is
joint
work
with
Edward
Lee,
and
was
completed
as
part
of
the
undergraduate
research
program
at
Combinatorics
and
Optimization
(C
and
O)
in
summer
2014.