Abstract:
Assuming 3-SAT formulas are hard to refute on average, Feige showed some approximation hardness results for several problems like min bisection, dense $k$-subgraph, max bipartite clique and the 2-catalog segmentation problem. We show a similar result for max bipartite clique, but under the assumption, 4-SAT formulas are hard to refute on average. As falsity of the 4-SAT assumption implies falsity of the 3-SAT assumption it seems that our assumption is weaker than that of Feige.