Relaxations and Solutions for the Minimum Graph Bisection Problem
By (author) Marzena Fugenschuh
Paperback (Published)
(November 2007)
ISBN: 9783832517359
5.71 x 8.27 inches
Price: $61.00
Out of stock
The minimum graph bisection problem is a special kind of a graph partitioning problem, where the nodes of a weighted graph are divided into two subsets with prescribed capacity, and the weighted sum of edges joining nodes in different subsets is minimized. Due to the knapsack condition on the weight of the node subsets the problem is NP-hard. It has a variety of applications, for instance in the design of electronic circuits and devices. In this thesis we investigate current efficient optimization methods to solve to optimality the minimum graph bisection problem. This combinatorial optimization problem can be modeled by means of linear as well as quadratic integer programming. Each formulation leads to a different kind of approximation, in form of a relaxation, and thus different computational methods applied for their solution. Nevertheless, the feasible sets in each representation are in one-to-one correspondence under an affine transformation. Thus the convex hull of the feasible points, the so called bisection cut polytope, is a common object to study. The tightest possible description of this polytope can be utilized to improve the approximations. We incorporate the separation algorithms for the obtained new classes of valid inequalities in a branch-and-cut framework and investigate their interaction with linear and semidefinite relaxations using instances coming from VLSI design and scientific computations as well as random graphs. Generally only the linear relaxation benefits from the new inequalities. Although they also improve the bounds delivered by semidefinite relaxation, the separation time significantly slows down the solution process. The semidefinite relaxation seems to outperform the linear one due to a weakness of the primal methods applied to the linear relaxation. By means of random instances we show that combinations of the linear and the semidefinite relaxation within one solution process pay off.
- By (author) Marzena Fugenschuh
Similar Books
![Book cover: Transitive Media [Philosophy]](https://isd.stisonbooks.com/images/books/native/9781804132340.jpg?asset_id=66970)
Care in an Era of New Technologies and Artificial Intelligence
Relationships in a Connected World
Volume 14
Buchblogs zwischen Passion und Profession
Zur Diskursivierung digitaler literaturbezogener Anschlusskommunikation als Arbeit
Volume 5
Proceedings of the 7th Symposium of the Hellenic Society for Archaeometry
Archaeology Archaeometry: 30 Years Later
Die Einfuhrung ins richtige Handeln in der Arithmetik (Madhal ar-rasad ila ‘ilm al-‘adad) von al-Qalasadi (st. 1486)
Bearbeitung und Einordnung in die magribinische Mathematikgeschichte
Volume 19
I disegni e i discorsi di Giovanni Antonio Nigrone vol. I
fontanaro e ingegniero de acqua (1585-1609 ca.)
Volume 481
I disegni e i discorsi di Giovanni Antonio Nigrone vol. II
Fontanaro e ingegniero de acqua (1585-1609 ca.)
Volume 497
Performance Management in Humanitarian Logistics
Development of a Process-driven and IT-supported Performance Measurement System
Volume 66
Supporting Operational and Real-time Planning Tasks of Road Freight Transport with Machine Learning
Guiding the Implementation of Machine Learning Algorithms
Volume 69
