648 research outputs found
Computational Experience with a SDP-Based Algorithm for Maximum Cut with Limited Unbalance
No full textIn the Maximum Cut with Limited Unbalance problem, we want to partition the vertices of a weighted graph into two sets of sizes differing at most by a given threshold B, so that the sum of the weights of the crossing edges is maximum. This problem has been introduced in [Galbiati and Maffioli, Theor Comput Sci 385 (2007), 78–87] where polynomial time randomized approximation algorithms are proposed and their performance guarantees are analyzed in the case of non-negative integer weights. In this article, we present extensive computational experience with these algorithms on a large number of different graphs. We then extend the analysis of these algorithms to integer weights not restricted in sign, and continue the computational testing. It turns out that the approximation ratios obtained are always substantially better than those guaranteed by the theoretical analysis
La memoria come strumento di lotta: dall’incontro con Annie Ernaux
No full textIn October 2022, a few weeks after the announcement of the Nobel Prize, Annie Ernaux premiered in Italy her first film, Les Années Super8, released with her son David Ernaux-Briot. The extract below corresponds to a part of the dialogue between the French author and Francesca Maffioli, which took place in Bologna at Salaborsa Library during the XV edition of Archivio Aperto, the festival of Home Movies – National Family Film Archive
Approximation algorithms for maximum cut with limited unbalance
No full textAbstractWe consider the problem of partitioning the vertices of a weighted graph into two sets of sizes that differ at most by a given threshold B, so as to maximize the weight of the crossing edges. For B equal to 0 this problem is known as Max Bisection, whereas for B equal to the number n of nodes it is the maximum cut problem. We present polynomial time randomized approximation algorithms with non trivial performance guarantees for its solution. The approximation results are obtained by extending the methodology used by Y. Ye for Max Bisection and by combining this technique with another one that uses the algorithm of Goemans and Williamson for the maximum cut problem. When B is equal to zero the approximation ratio achieved coincides with the one obtained by Y. Ye; otherwise it is always above this value and tends to the value obtained by Goemans and Williamson as B approaches the number n of nodes
- …
