An exact combinatorial algorithm for minimum graph bisection
We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully co...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2016
|
| Online Access: | http://hdl.handle.net/1721.1/103396 https://orcid.org/0000-0002-3962-721X |
| _version_ | 1826208996012326912 |
|---|---|
| author | Delling, Daniel Fleischman, Daniel Goldberg, Andrew V. Razenshteyn, Ilya Werneck, Renato F. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Delling, Daniel Fleischman, Daniel Goldberg, Andrew V. Razenshteyn, Ilya Werneck, Renato F. |
| author_sort | Delling, Daniel |
| collection | MIT |
| description | We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. We introduce novel lower bounds based on packing trees, as well as a new decomposition technique that contracts entire regions of the graph while preserving optimality guarantees. Our algorithm works particularly well on graphs with relatively small minimum bisections, solving to optimality several large real-world instances (with up to millions of vertices) for the first time. |
| first_indexed | 2024-09-23T14:15:43Z |
| format | Article |
| id | mit-1721.1/103396 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:15:43Z |
| publishDate | 2016 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1033962022-10-01T20:13:28Z An exact combinatorial algorithm for minimum graph bisection Delling, Daniel Fleischman, Daniel Goldberg, Andrew V. Razenshteyn, Ilya Werneck, Renato F. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Razenshteyn, Ilya We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. We introduce novel lower bounds based on packing trees, as well as a new decomposition technique that contracts entire regions of the graph while preserving optimality guarantees. Our algorithm works particularly well on graphs with relatively small minimum bisections, solving to optimality several large real-world instances (with up to millions of vertices) for the first time. 2016-06-30T19:53:42Z 2016-06-30T19:53:42Z 2014-09 2013-09 2016-05-23T12:11:15Z Article http://purl.org/eprint/type/JournalArticle 0025-5610 1436-4646 http://hdl.handle.net/1721.1/103396 Delling, Daniel, Daniel Fleischman, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck. “An Exact Combinatorial Algorithm for Minimum Graph Bisection.” Math. Program. 153, no. 2 (September 10, 2014): 417–458. https://orcid.org/0000-0002-3962-721X en http://dx.doi.org/10.1007/s10107-014-0811-z Mathematical Programming Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Delling, Daniel Fleischman, Daniel Goldberg, Andrew V. Razenshteyn, Ilya Werneck, Renato F. An exact combinatorial algorithm for minimum graph bisection |
| title | An exact combinatorial algorithm for minimum graph bisection |
| title_full | An exact combinatorial algorithm for minimum graph bisection |
| title_fullStr | An exact combinatorial algorithm for minimum graph bisection |
| title_full_unstemmed | An exact combinatorial algorithm for minimum graph bisection |
| title_short | An exact combinatorial algorithm for minimum graph bisection |
| title_sort | exact combinatorial algorithm for minimum graph bisection |
| url | http://hdl.handle.net/1721.1/103396 https://orcid.org/0000-0002-3962-721X |
| work_keys_str_mv | AT dellingdaniel anexactcombinatorialalgorithmforminimumgraphbisection AT fleischmandaniel anexactcombinatorialalgorithmforminimumgraphbisection AT goldbergandrewv anexactcombinatorialalgorithmforminimumgraphbisection AT razenshteynilya anexactcombinatorialalgorithmforminimumgraphbisection AT werneckrenatof anexactcombinatorialalgorithmforminimumgraphbisection AT dellingdaniel exactcombinatorialalgorithmforminimumgraphbisection AT fleischmandaniel exactcombinatorialalgorithmforminimumgraphbisection AT goldbergandrewv exactcombinatorialalgorithmforminimumgraphbisection AT razenshteynilya exactcombinatorialalgorithmforminimumgraphbisection AT werneckrenatof exactcombinatorialalgorithmforminimumgraphbisection |