## Upcoming Events

## On a Combinatorial Optimization Problem Involving the Graph Laplacian Matrix

October 25, 2013 3:00PM to 4:00PM

Presenter

Fu Lin (MCS)

Location

Building 240, Room 1404-1405

Type

Seminar

Series

LANS Informal Seminar

Abstract:

Given a graph Laplacian matrix, we are interested in finding a principal submatrix of fixed size such that the trace of the inverse of the submatrix is minimized. This combinatorial optimization problem arises in a variety of applications including leader-follower consensus networks, sensor localization, and circuit design. Instead of performing an exhaustive search, we develop efficient algorithms that provide lower and upper bounds on the global optimal value.

Given a graph Laplacian matrix, we are interested in finding a principal submatrix of fixed size such that the trace of the inverse of the submatrix is minimized. This combinatorial optimization problem arises in a variety of applications including leader-follower consensus networks, sensor localization, and circuit design. Instead of performing an exhaustive search, we develop efficient algorithms that provide lower and upper bounds on the global optimal value.

A lower bound is obtained by solving a convex relaxation and an upper bound is obtained by using a greedy algorithm. Furthermore, we significantly reduce the computational complexity by exploiting problem structure (such as separability in the convex relaxation and low-rank update in the greedy algorithm). Illustrative examples ranging from random networks to regular lattices are used to gain interesting insight.