submodular minimization

Edge expansion of a graph: SDP-based computational strategies

  • Akshay Gupte
  • Melanie Siebenhofer
  • Angelika Wiegele
    • Categories Combinatorial Optimization, Parallel Algorithms, Semi-definite Programming Tags , , , ,

    Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relax- ation first to reduce the search space considerably. One … Read more

    Submodular Minimization in the Context of Modern LP and MILP Methods and Solvers

  • Jon Lee
  • Siqian Shen
  • Andrew Orso
    • Categories 0-1 Programming, Combinatorial Optimization, Linear Programming Tags , , , ,

    We consider the application of mixed-integer linear programming (MILP) solvers to the minimization of submodular functions. We evaluate common large-scale linear-programming (LP) techniques (e.g., column generation, row generation, dual stabilization) for solving a LP reformulation of the submodular minimization (SM) problem. We present heuristics based on the LP framework and a MILP solver. We evaluated … Read more