Multilevel Processing of large graph problems

Achi Brandt
Weizmann Institute of Science

1. Most graph problems originate from fuzzy real-world problems, reformulated as optimization problems. Examples to be discussed: Image segmentation, traveling salesman, graph drawing, graph linear ordering, and data clustering.

2. The resulting optimization problems are usually ill posed and hard to solve.

3. They are often approximately solved by spectral methods.

4. Very fast multilevel spectral solvers are based on Algebraic MultiGrid (AMG).

5. Avoid spectral solvers: Better apply the fast multilevel (AMG-like) processing directly to the fuzzy problem. The obtained solution is closer to optimal than the spectral solution.

6. Moreover, for the original fuzzy problem, the fast multilevel processing offer tools to produce solutions that are often far more adequate than the solution of the optimization reformulation (as judged on collections of practical problems in terms of their real set of, sometimes contradictory, objectives).

Presentation (PowerPoint File)

Back to Graph Cuts and Related Discrete or Continuous Optimization Problems