{
  "id": "2006.04571",
  "version": "v1",
  "published": "2020-06-05T12:16:08.000Z",
  "updated": "2020-06-05T12:16:08.000Z",
  "title": "A Computational Study of Exact Subgraph Based SDP Bounds for Max-Cut, Stable Set and Coloring",
  "authors": [
    "Elisabeth Gaar",
    "Franz Rendl"
  ],
  "comment": "arXiv admin note: substantial text overlap with arXiv:1902.05345",
  "doi": "10.1007/s10107-020-01512-2",
  "categories": [
    "math.OC"
  ],
  "abstract": "The \"exact subgraph\" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-05T12:16:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C22",
      "90C27"
    ],
    "keywords": [
      "exact subgraph",
      "stable set",
      "computational study",
      "sdp bounds",
      "np-hard graph optimization problems"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Springer"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}