Ghaddar, B: Solving Partition Problems A Branch-and-Cut Approach based on Semidefinite Programming
-
- Deutsch ausgewählt
49,00 €
inkl. gesetzl. MwSt.,
Lieferung nach Hause
Beschreibung
Produktdetails
Einband
Taschenbuch
Erscheinungsdatum
01.05.2009
Verlag
VDMSeitenzahl
104
Maße (L/B/H)
22/15/0,6 cm
Gewicht
171 g
Sprache
Deutsch
ISBN
978-3-639-13621-0
The minimum k-partition (MkP) problem is the problem
of partitioning the set of vertices of a graph into k
disjoint subsets so as to minimize the total weight
of the edges joining vertices in the same partition.
The main contribution is the design and
implementation of a novel iterative clustering
heuristic (ICH) based on semide nite programming to nd feasible solutions for the MkP problem. We
compare ICH to the hyperplane rounding techniques,
and the computational results support the conclusion
that ICH consistently provides better feasible
solutions for the MkP problem. We use ICH in a
branch-and-cut algorithm to provide feasible
solutions at each node of the branch-and-bound tree.
The branch-and-cut algorithm computes globally
optimal solutions for dense graphs with up to 60
vertices, for grid graphs with up to 100 vertices,
and for different values of k, providing the best
exact approach to date for k 2.
of partitioning the set of vertices of a graph into k
disjoint subsets so as to minimize the total weight
of the edges joining vertices in the same partition.
The main contribution is the design and
implementation of a novel iterative clustering
heuristic (ICH) based on semide nite programming to nd feasible solutions for the MkP problem. We
compare ICH to the hyperplane rounding techniques,
and the computational results support the conclusion
that ICH consistently provides better feasible
solutions for the MkP problem. We use ICH in a
branch-and-cut algorithm to provide feasible
solutions at each node of the branch-and-bound tree.
The branch-and-cut algorithm computes globally
optimal solutions for dense graphs with up to 60
vertices, for grid graphs with up to 100 vertices,
and for different values of k, providing the best
exact approach to date for k 2.
Kundinnen und Kunden meinen
Verfassen Sie die erste Bewertung zu diesem Artikel
Helfen Sie anderen Kund*innen durch Ihre Meinung
Kurze Frage zu unserer Seite
Vielen Dank für dein Feedback
Wir nutzen dein Feedback, um unsere Produktseiten zu verbessern. Bitte habe Verständnis, dass wir dir keine Rückmeldung geben können. Falls du Kontakt mit uns aufnehmen möchtest, kannst du dich aber gerne an unseren Kund*innenservice wenden.
zum Kundenservice