Name
Abstract | ||
|---|---|---|
Problems such as bisection, graph coloring, and clique are generally believed hard in the worst case. However, they can be solved if the input data is drawn randomly from a distribution over graphs containing acceptable solutions. In this paper we show that a simple spectral algorithm can solve all three problems above in the average case, as well as a more general problem of partitioning graphs based on edge density. In nearly all cases our approach meets or exceeds previous parameters, while introducing substantial generality. We apply spectral techniques, using foremost the observation that in all of these problems, the expected adjacency matrix is a low rank matrix wherein the structure of the solution is evident. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1109/SFCS.2001.959929 | foundations of computer science |
Keywords | DocType | ISSN |
low rank matrix,approach meet,spectral partitioning,random graphs,expected adjacency matrix,general problem,spectral technique,worst case,edge density,average case,acceptable solution,simple spectral algorithm,computational geometry | Conference | 0272-5428 |
ISBN | Citations | PageRank |
0-7695-1390-5 | 242 | 15.51 |
References | Authors | |
15 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank McSherry | 1 | 4289 | 288.94 |