spectral method – Optimization Online

Finding good nearly balanced cuts in power law graphs

Published: 2004/12/20

Graphs and Matroids flow-based rounding, graph partitioning, power law graphs, semidefinite programming, social graphs, spectral method

In power law graphs, cut quality varies inversely with cut balance. Using some million node social graphs as a test bed, we empirically investigate this property and its implications for graph partitioning. We use six algorithms, including Metis and MQI (state of the art methods for finding bisections and quotient cuts) and four relaxation/rounding methods. … Read more

Semidefinite optimization, a spectral approach

Published: 2002/09/30

M.A. van Bossum

Nonlinear Optimization, Semi-definite Programming convex optimization, eigenvalue optimization, iterative methods, large-scale optimization, newton methods, semidefinite programming, spectral method, subspace methods

This thesis is about mathematical optimization. Mathematical optimization involves the construction of methods to solve optimization problems, which can arise from real-life problems in applied science, when they are mathematically modeled. Examples come from electrical design, engineering, control theory, telecommunication, environment, finance, and logistics. This thesis deals especially with semidefinite optimization problems. Semidefinite programming is … Read more