Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with 4-SAT:
TR04-048 | 21st April 2004
André Lanka, Andreas Goerdt

An approximation hardness result for bipartite Clique

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

ISSN 1433-8092 | Imprint