Calculul gradientului funcţiei de penalizare în problema max-cut

Abstract

Prezenta lucrare este consacrată problemei determinării tăieturii maxime într-un graf. Pentru rezolvarea problemei relaxate max-cut se utilizează metoda punctului interior. Se prezintă o procedură efectivă de calcul al gradientului funcţiei de barieră, evitând inversarea matricelor.

The present work is devoted to the problem of determinating the maximum cut in a graph. For solving the relaxation max-cut problem the method of interior point is used. In the work there is presented an efficient procedure of computation of the gradient of the barrier function, not demanding matrix inversion.

Cet ouvrage est consacré au problème de détermination de la coupe maximale dans un graphe. Pour la résolution du problème relaxé max-cut on utilise la méthode du point intérieur. On présente une procédure effective de calcul du gradient de la fonction de barrière, en évitant l‘inversion des matrices.

Настоящая работа посвящена задачи определения максимального сечения в графе. Для решения ослабленной max-cut задаче используется метод внутренней точки. В работе приводится эффективный способ вычисления градиента барьерной функции, не требующий обращения матриц.