Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-048 | 21st April 2004 00:00

An approximation hardness result for bipartite Clique

RSS-Feed




TR04-048
Authors: André Lanka, Andreas Goerdt
Publication: 9th June 2004 18:02
Downloads: 1815
Keywords: 


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.



ISSN 1433-8092 | Imprint