## Abstract

The cut-norm ∥A∥c of a real matrix A = (a_{ij}) _{iεR,jεS} is the maximum, over all I ⊂ R, J ⊂ S of the quantity | ∑_{iεI, jεJ} a_{ij}|. This concept plays a major role in the design of efficient approximation algorithms for dense graph and matrix problems. Here we show that the problem of approximating the cut-norm of a given real matrix is MAX SNP hard, and provide an efficient approximation algorithm. This algorithm finds, for a given matrix A = (a _{ij})_{iεR, jεs}, two subsets I ⊂ R and J ⊂ S, such that | ∑_{iεI, jεJ} a_{ij}| ≥ ρ ∥A∥c where ρ > 0 is an absolute constant satisfying ρ > 0.56. The algorithm combines semidefinite programming with a rounding technique based on Grothendieck's Inequality. We present three known proofs of Grothendieck's inequality, with the necessary modifications which emphasize their algorithmic aspects. These proofs contain rounding techniques which go beyond the random hyperplane rounding of Goemans and Williamson, allowing us to transfer various algorithms for dense graph and matrix problems to the sparse case.

Original language | English (US) |
---|---|

Pages (from-to) | 72-80 |

Number of pages | 9 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - 2004 |

Externally published | Yes |

Event | Proceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States Duration: Jun 13 2004 → Jun 15 2004 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Cut-Norm
- Grothendieck's Inequaity
- Rounding Techniques