10 citations · 13 across the 4 of their papers we have counts for
4 papers
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
Per Austrin, Siavosh Benabbas, Konstantinos Georgiou
Recently Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the Max Bisection problem. We improve their algorithm to a 0.8776-approximation. As Max Bisection i…
A new point of NP-hardness for 2-to-1 Label Cover
Per Austrin, Ryan O'Donnell, John Wright
We show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a $(23/24 + \eps)$-satisfying assignment.
On the Usefulness of Predicates
Per Austrin, Johan Håstad
Motivated by the pervasiveness of strong inapproximability results for Max-CSPs, we introduce a relaxed notion of an approximate solution of a Max-CSP. In this relaxed version, loo…
Improved Inapproximability For Submodular Maximization
Per Austrin
We show that it is Unique Games-hard to approximate the maximum of a submodular function to within a factor 0.695, and that it is Unique Games-hard to approximate the maximum of a…