VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • MADAM : a parallel exact solver for max-cut based on semidefinite programming and ADMM
    Hrga, Timotej ; Povh, Janez, 1973-
    We present MADAM, a parallel semidefinite-based exact solver for Max-Cut, a problem of finding the cut with the maximum weight in a given graph. The algorithm uses the branch and bound paradigm that ... applies the alternating direction method of multipliers as the bounding routine to solve the basic semidefinite relaxation strengthened by a subset of hypermetric inequalities. The benefit of the new approach is a less computationally expensive update rule for the dual variable with respect to the inequality constraints. We provide a theoretical convergence of the algorithm as well as extensive computational experiments with this method, to show that our algorithm outperforms state-of-the-art approaches. Furthermore, by combining algorithmic ingredients from the serial algorithm, we develop an efficient distributed parallel solver based on MPI.
    Vir: Computational optimization and applications. - ISSN 0926-6003 (Vol. 80, 2021, str. 347-375)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2021
    Jezik - angleški
    COBISS.SI-ID - 74752771

    Povezava(-e):

    https://link.springer.com/article/10.1007%2Fs10589-021-00310-6
    DOI

Vnos na polico