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