Discrete Optimization Problems in Graphs

Optimization is a mathematical discipline that concerns the finding of minima and maxima of functions, subject to so-called constraints. Discrete optimization problems arise, when the variables occurring in the optimization function can take only a finite number of discrete values. For example, in the graph bisection problem, the goal is to divide the nodes of the graph in two equal sized disjoint sets such that the number of edges between these parts is minimized.

There is no general solution known for optimization problems that reliably and speedily computes solutions to discrete optimization problems. In recent years, it has become clear that different application domains lend themselves to different solution techniques. Linear programming has been applied to discrete optimization using so-called "branch-and-bound" techniques, for example to solve facility location problems. Heuristic search aims at finding good but not necessarily optimal solutions quickly.

In order to be able to evaluate these solution techniques it is important to derive efficient (lower and upper) bounds for certain classes of discrete optimization problems. In our work, we mainly focus on the following problems related to partitioning of graphs:

  • Spectral bounds for optimal partitions in graphs
  • Isoperimetric problems and isoperimetric inequalities