Friday, March 23, 2012 — 3:30 PM to 4:30 PM EDT

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.)

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2021 (95)
    1. November (2)
    2. October (6)
    3. September (12)
    4. August (6)
    5. July (10)
    6. June (12)
    7. May (7)
    8. April (9)
    9. March (13)
    10. February (8)
    11. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)