Sammanfattning En exakt algoritm presenteras för att lösa kantviktade graf partitionering problem. Algoritmen är baserad på en gren och bunden metod tillämpas på en kontinuerlig quadratic programmering formulering av problemet. Nedre gränser erhålls genom att den objektiva funktionen bryts ned i konvexa och konkava delar och att konkava delen ersätts med en affin underskattning. Det visas att den bästa afffin underskattning kan uttryckas i termer av centrum och radien av den minsta sfären som innehåller den möjliga uppsättningen. Konkavatermen erhålls antingen genom ett konstant diagonalt skifte i samband med det minsta eigenvärdet av den objektiva funktionen Hessian, eller genom ett diagonalt skifte som erhålls genom att lösa ett semidefinit programmeringsproblem. Numeriska resultat visar att den föreslagna algoritmen är konkurrenskraftig med toppmoderna grafpartitioneringskoder.
Hager, Phan och Zhang REF presenterar en exakt gren-och-bunden algoritm för kantviktad graf bidelning formulerad som ett kontinuerligt kvadratiskt program med lägre gränser baserat på semidefinit programmering.
An exact algorithm for graph partitioning
{'venue': None, 'journal': 'Mathematical Programming', 'mag_field_of_study': ['Computer Science', 'Mathematics']}