Friday, March 23, 2012 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
Better balance by being biased: a 0.8776-algorithm for Max Bisection
| Speaker: | Per Austrin |
|---|---|
| Affiliation: | University of Toronto |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Recently
Raghavendra
and
Tan
(SODA
2012)
gave
a
0.85-approximation
algorithm
algorithm
for
the
Max
Bisection
problem.
We
improve
their
algorithm
to
a
0.8776-approximation.
As
Max
Bisection
is
hard
to
approximate
within
roughly
0.8786
(under
the
Unique
Games
Conjecture)
our
algorithm
is
very
nearly
optimal.
We
also
obtain
an
improved
algorithm
for
the
analogous
variant
of
Max
2-Sat.
Our
approximation
ratio
for
this
problem
exactly
matches
the
optimal
(assuming
the
UGC)
ratio
of
roughly
0.9401
for
Max
2-Sat,
showing
that
the
bisection
constraint
does
not
make
Max
2-Sat
harder.
(Joint
work
with
Siavosh
Benabbas
and
Konstantinos
Georgiou.)