The Graph Partitioning Archive

Welcome to the University of Greenwich Graph Partitioning Archive. The archive consists of the best partitions found to date for a range of graphs and its aim is to provide a benchmark against which partitioning algorithms can be tested and as a resource for experimentation.

Partitions computed for the colouring test suite in [Wal01] are contained in a separate annexe.

The archive was initially set up as part of a research project into very high quality partitions and authors wishing to refer to the partitioning archive should cite the paper [SWC00].

Problem definition

Let G = G(V,E) be an undirected graph of vertices V, with edges E. We assume that both vertices and edges can be weighted and that |v| denotes the weight of a vertex v and similarly for edges and sets of vertices and edges. However, it is often the case that vertices and edges are given unit weights, |v|=1 for all v in V and |e|=1 for all e in E and indeed so far this is true for all of the example graphs. A partition of the graph is a mapping of V into P disjoint subdomains S_p such that the union of S_p = V. The weight of a subdomain is just the sum of the weights of the vertices in the subdomain, |S_p| = sum |v| and the set of inter-subdomain or cut edges (i.e. edges cut by the partition) is denoted by E_c.

The usual objective of graph partitioning is to find a partition which evenly balances the vertex weight in each subdomain whilst minimising the total weight of cut edges or cut-weight, |E_c|. To evenly balance the vertex weight, the optimal subdomain weight is given by S_opt := ceil(|V|/P) (where the ceiling function ceil(x) returns the smallest integer greater than x). The graph partitioning problem can then be specified as: find a partition of G such that |E_c| is minimised subject to the constraint that |S_p| <= S_opt.

In fact it has been noted for some time that partition quality can often be improved if a certain amount of imbalance is allowed, [ST97]. The imbalance is defined as the maximum subdomain weight, S' = max |S_p|, divided by the optimal, S_opt. If we allow x% imbalance then the partitioning problem becomes: find a partition of G such that |E_c| is minimised subject to the constraint that |S_p| <= S_opt.(100+x)/100.

The graph partitioning problem arises in many applications such as VLSI circuit design, data mining and parallel computing. In the latter case the subdomains are mapped to processors and the cut-weight then approximates the total communication volume. However, there is some discussion about whether this is the most appropriate metric for partitioning, e.g. [HK], and indeed it is unlikely that any one metric is appropriate. Currently in the archive, the quality of partitions is determined by cut-weight, however, there is no reason why it should not be extended to incorporate partitions which minimise different cost functions.

Submissions

The archive welcomes submissions of either partition files, graph files or both. Partition files will be validated and added to the archive if they improve on a particular result. In this context improvement is

having a lower cut-weight than the exisiting result whilst not exceeding the maximum subdomain weight; or
having the same cut-weight as an exisiting result but a smaller maximum subdomain weight; or
being a new result.

File for submission should be made available on a web site or ftp site and a mail message indicating their presence sent to Chris Walshaw. If this is not possible the files may be mailed directly. Submitted files should also include some indication of how the partition was derived which, if a public domain software package, may be subject to verification. The archive reserves the right not to accepted submitted files (either for reasons of disk space or for other unspecified reasons).

Archived partitions

The best partitions found to date are listed in 4 tables corresponding to 0% imbalance (perfect balance), 1% imbalance, 3% imbalance and 5% imbalance. For each graph, partitions into 2, 4, 8, 16, 32 and 64 subdomains are given and have the format

C (S') [M]

where C is the cut-weight, S' is the weight of the largest subdomain and M is the method/software that produced the partition. The cut-weight also provides a link to the partition file. The format of the partition file is a list of |V| integers {p}, with 0 <= p < P, and each denoting the subdomain to which the corresponding vertex has been assigned (e.g. if the integer on line 200 is 0 then vertex number 200 is in subdomain 0).

Software

The software that produced the partitions is denoted as follows

Abbreviation	Software	Reference
Grdy	Farhat's Greedy algorithm (as implemented within JOSTLE)	[Far88]
RCB	Recursive Coordinate Bisection (as implemented within JOSTLE)	[Sim91]
MRSB	Barnard & Simon's Multilevel Recursive Spectral Bisection	[BS94]
Ch2.0	CHACO - multilevel Kernighan-Lin (recursive bisection); version 2.0 (October 1995)	[HL95]
pM4.0	p-METIS - multilevel Kernighan-Lin (recursive bisection); available as part of METIS version 4.0 (September 1998)	[KK98a]
kM4.0	k-METIS - multilevel Kernighan-Lin (k-way); available as part of METIS version 4.0 (September 1998)	[KK98b]
GTS	Stephane Popinet's multilevel implementation available as part of the GNU Triangulated Surface Library	-
J2.2	JOSTLE - multilevel Kernighan-Lin (k-way); version 2.2 (March 2000)	[WC00]
iJ	iterated JOSTLE - iterated multilevel Kernighan-Lin (k-way)	[Wal01]
JE	JOSTLE Evolutionary - combined evolutionary/multilevel scheme	[SWC00]
GrPart	Alexander Kozhushkin's implementation of iterative multilevel Kernighan-Lin	-
MLSATS	MultiLevel refinated Mixed Simulated Annealing and Tabu Search	[BGOM03]
AMG	A bisection algorithm based on classical Algebraic MultiGrid from S. Wishko, A. Brandt and D. Ron	-
MQI	Max-flow Quotient-cut Improvement, a bisection algorithm from K. Lang & S. Rao, which uses many multiple tries and improves an initial partition provided by METIS	[LR04]
SDP	A semi-definite programming approach together with a max-flow algorithm from K. Lang & S. Rao	-
mpM4.0	Multiple runs (6561) of a randomised version of p-Metis; results provided by K. Lang & S. Rao	-
N/A	not available/recorded (probably JOSTLE Evolutionary)	-

Note that a certain amount of care needs to be taken with the attribution of a result to a particular method. For example the finan512 graph with P = 4 is attributed to CHACO 2.0 although an equivalent quality partition was also found by p-METIS, k-METIS, JOSTLE 2.2, JOSTLE Evolutionary and iterated JOSTLE. Attribution is thus given to the earliest method which found it but does not imply that an equivalent quality partition has not been found by a more recent method. The results were added into the archive in the order shown in the table (which is approximately the order in which the methods and software were developed).

Notes:

CHACO was run using the multilevel KL method with recursive bisection and a coarsening threshold of 200.
JOSTLE was run with the imbalance threshold set to 0%, 1%, 3% (default) and 5% (i.e. 4 different tests for each graph and value of P).
JOSTLE Evolutionary (JE) was run with the imbalance threshold set to 0% and 3% (i.e. 2 different tests for each graph and value of P). It was only tested in full on a subset of the graphs (add20, 3elt, uk, add32, whitaker3, crack, wing_nodal, fe_4elt2, vibrobox, 4elt, fe_sphere, cti, memplus, cs4, fe_pwt, bcsstk32, t60k, wing, brack2) although occasional JE attributions may be found for other graphs.

References

BGOM03: R. Banos, C. Gil, J. Ortega, and F. G. Montoya. Multilevel Heuristic Algorithm for Graph Partitioning. In 3rd European Workshop on Evolutionary Computation in Combinatorial Optimization, volume 2611 of LNCS, pages 143-153. Springer, Berlin, 2003.
BS94: S. T. Barnard and H. D. Simon. A Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems. Concurrency: Practice & Experience, 6(2):101-117, 1994.
Far88: C. Farhat. A Simple and Efficient Automatic FEM Domain Decomposer. Comput. & Structures, 28(5):579-602, 1988.
HK00: B. Hendrickson and T. G. Kolda. Graph Partitioning Models for Parallel Computing. Parallel Comput., 26(12):1519-1534, 2000.
HL95: B. Hendrickson and R. Leland. A Multilevel Algorithm for Partitioning Graphs. In S. Karin, editor, Proc. Supercomputing '95, San Diego. ACM Press, New York, 1995.
KK98a: G. Karypis and V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J. Sci. Comput., 20(1):359-392, 1998.
KK98b: G. Karypis and V. Kumar. Multilevel k-way Partitioning Scheme for Irregular Graphs. J. Parallel Distrib. Comput., 48(1):96-129, 1998.
LR04: K. Lang and S. Rao. A flow-based method for improving the expansion or conductance of graph cuts. 2004.
Sim91: H. D. Simon. Partitioning of Unstructured Problems for Parallel Processing. Computing Systems Engrg., 2:135-148, 1991.
ST97: H. D. Simon and S.-H. Teng. How Good is Recursive Bisection? SIAM J. Sci. Comput., 18(5):1436-1445, 1997.
SWC00: A. J. Soper, C. Walshaw, and M. Cross. A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph Partitioning. (to appear in J. Global Optimization; originally published as Univ. Greenwich Tech. Rep. 00/IM/58), 2000.
Wal01: C. Walshaw. Multilevel Refinement for Combinatorial Optimisation Problems. (To appear in Annals Oper. Res.; originally published as Univ. Greenwich Tech. Rep. 01/IM/73), 2001.
WC00: C. Walshaw and M. Cross. Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm. SIAM J. Sci. Comput., 22(1):63-80, 2000. (originally published as Univ. Greenwich Tech. Rep. 98/IM/35).

Test Graphs

The test graphs are taken from various sources and listed in the table below. Graphs for which the original source is bracketted appear to be no longer available at that site. However all the graph files are also available from this site converted into a standard format. This format is the same as used by JOSTLE, CHACO & METIS and is described in the JOSTLE userguide.

graph	\|V\|	\|E\|	original source
add20	2395	7462	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/Hamm/add20.rua.gz
data	2851	15093	http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/archive/data/data.graph
3elt	4720	13722	(ftp://riacs.edu/pub/grids/3elt.grid.gz)
uk	4824	6837	http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/archive/uk/uk.graph
add32	4960	9462	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/Hamm/add32.rua.gz
bcsstk33	8738	291583	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/HB/bcsstk33.psa.gz
whitaker3	9800	28989	(ftp://riacs.edu/pub/grids/whitaker3.grid.gz)
crack	10240	30380	http://www.uni-paderborn.de/fachbereich/AG/monien/RESEARCH/PART/GRAPHS/FEM2.tar
wing_nodal	10937	75488	http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/archive/wing_nodal/wing_nodal.graph
fe_4elt2	11143	32818	(ftp://ftp.u-bordeaux.fr/pub/Local/Info/Software/Scotch/Graphs/fe_4elt2.src.gz
vibrobox	12328	165250	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/Cote/vibrobox.rsa.gz
bcsstk29	13992	302748	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/HB/bcsstk29.psa.gz
4elt	15606	45878	(ftp://riacs.edu/pub/grids/barth5.grid.gz)
fe_sphere	16386	49152	(ftp://ftp.u-bordeaux.fr/pub/Local/Info/Software/Scotch/Graphs/fe_sphere.src.gz)
cti	16840	48232	http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/archive/cti/cti.graph
memplus	17758	54196	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/Hamm/memplus.rua.gz
cs4	22499	43858	http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/archive/cs4/cs4.graph
bcsstk30	28924	1007284	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/HB/bcsstk30.psa.gz
bcsstk31	35588	572914	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/HB/bcsstk31.psa.gz
fe_pwt	36519	144794	(ftp://ftp.u-bordeaux.fr/pub/Local/Info/Software/Scotch/Graphs/fe_pwt.src.gz)
bcsstk32	44609	985046	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/HB/bcsstk32.psa.gz
fe_body	45087	163734	(ftp://ftp.u-bordeaux.fr/pub/Local/Info/Software/Scotch/Graphs/fe_body.src.gz)
t60k	60005	89440	http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/archive/t60k/t60k.graph
wing	62032	121544	http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/archive/wing/wing.graph
brack2	62631	366559	(ftp://riacs.edu/pub/grids/brack2.grid.gz)
finan512	74752	261120	ftp://ftp.cis.ufl.edu/pub/umfpack/matrices/Mulvey/finan512.psa.gz
fe_tooth	78136	452591	(ftp://ftp.u-bordeaux.fr/pub/Local/Info/Software/Scotch/Graphs/fe_tooth.src.gz)
fe_rotor	99617	662431	(ftp://ftp.u-bordeaux.fr/pub/Local/Info/Software/Scotch/Graphs/fe_rotor.src.gz)
598a	110971	741934	ftp://ftp.cs.umn.edu/users/kumar/Graphs/598a.graph.gz
fe_ocean	143437	409593	(ftp://ftp.u-bordeaux.fr/pub/Local/Info/Software/Scotch/Graphs/fe_ocean.src.gz)
144	144649	1074393	ftp://ftp.cs.umn.edu/users/kumar/Graphs/144.graph.gz
wave	156317	1059331	(ftp://riacs.edu/pub/grids/wave.grid.gz)
m14b	214765	1679018	ftp://ftp.cs.umn.edu/users/kumar/Graphs/m14b.graph.gz
auto	448695	3314611	ftp://ftp.cs.umn.edu/users/kumar/Graphs/auto.graph.gz

Results with up to 0% imbalance
S_max <= 1.00 x S_opt

graph	2	4	8	16	32	64
add20	612 (1198) [MQI]	1203 (599) [JE]	1758 (300) [iJ]	2216 (150) [iJ]	2765 (75) [JE]	3266 (38) [JE]
data	191 (1426) [mpM4.0]	429 (713) [iJ]	728 (357) [iJ]	1245 (179) [Ch2.0]	2004 (90) [iJ]	3016 (45) [iJ]
3elt	90 (2360) [JE]	201 (1180) [JE]	349 (590) [JE]	589 (295) [JE]	972 (148) [JE]	1594 (74) [iJ]
uk	20 (2412) [mpM4.0]	44 (1206) [JE]	91 (603) [JE]	162 (302) [JE]	286 (151) [JE]	456 (76) [iJ]
add32	11 (2480) [Ch2.0]	37 (1240) [pM4.0]	75 (620) [JE]	121 (310) [Ch2.0]	234 (155) [JE]	720 (78) [Ch2.0]
bcsstk33	10172 (4369) [mpM4.0]	21956 (2185) [iJ]	35088 (1093) [iJ]	56973 (547) [iJ]	80099 (274) [iJ]	109585 (137) [iJ]
whitaker3	127 (4900) [JE]	382 (2450) [JE]	664 (1225) [JE]	1110 (613) [JE]	1719 (307) [JE]	2579 (154) [iJ]
crack	184 (5120) [JE]	368 (2560) [JE]	687 (1280) [JE]	1124 (640) [JE]	1768 (320) [JE]	2696 (160) [iJ]
wing_nodal	1707 (5469) [JE]	3581 (2735) [JE]	5443 (1368) [JE]	8422 (684) [JE]	12228 (342) [iJ]	16373 (171) [iJ]
fe_4elt2	130 (5572) [MRSB]	349 (2786) [JE]	617 (1393) [JE]	1028 (697) [JE]	1677 (349) [JE]	2537 (175) [iJ]
vibrobox	10343 (6164) [JE]	19245 (3082) [JE]	25468 (1541) [iJ]	33468 (771) [iJ]	43786 (386) [JE]	51101 (193) [JE]
bcsstk29	2843 (6996) [mpM4.0]	8786 (3498) [MRSB]	16832 (1749) [iJ]	24706 (875) [iJ]	38535 (438) [iJ]	61252 (219) [iJ]
4elt	139 (7803) [JE]	327 (3902) [JE]	556 (1951) [JE]	968 (976) [JE]	1606 (488) [JE]	2702 (244) [iJ]
fe_sphere	386 (8193) [JE]	773 (4097) [N/A]	1193 (2049) [JE]	1750 (1025) [JE]	2567 (513) [JE]	3663 (257) [JE]
cti	334 (8420) [JE]	977 (4210) [JE]	1812 (2105) [JE]	2915 (1053) [JE]	4460 (527) [iJ]	6277 (264) [iJ]
memplus	5538 (8879) [JE]	9754 (4440) [JE]	12095 (2220) [iJ]	13742 (1110) [JE]	14830 (555) [iJ]	17446 (278) [JE]
cs4	372 (11250) [JE]	964 (5625) [JE]	1496 (2813) [JE]	2206 (1407) [JE]	3110 (704) [iJ]	4223 (352) [iJ]
bcsstk30	6394 (14462) [JE]	16652 (7231) [JE]	34921 (3616) [JE]	72007 (1808) [JE]	120580 (904) [JE]	184855 (452) [JE]
bcsstk31	2768 (17794) [mpM4.0]	8322 (8897) [iJ]	14426 (4449) [pM4.0]	25491 (2225) [iJ]	39440 (1113) [iJ]	63998 (557) [iJ]
fe_pwt	340 (18260) [GrPart]	709 (9130) [JE]	1465 (4565) [JE]	2855 (2283) [JE]	5848 (1142) [iJ]	8495 (571) [iJ]
bcsstk32	4667 (22305) [JE]	10578 (11153) [JE]	22826 (5577) [JE]	40275 (2789) [JE]	66407 (1395) [JE]	102820 (698) [JE]
fe_body	262 (22544) [MQI]	703 (11272) [pM4.0]	1315 (5636) [iJ]	2117 (2818) [iJ]	3432 (1409) [iJ]	5588 (705) [iJ]
t60k	80 (30003) [JE]	216 (15002) [JE]	480 (7501) [JE]	892 (3751) [iJ]	1453 (1876) [iJ]	2277 (938) [iJ]
wing	791 (31016) [MQI]	1666 (15508) [JE]	2589 (7754) [JE]	4198 (3877) [JE]	6104 (1939) [iJ]	8203 (970) [iJ]
brack2	731 (31316) [JE]	3090 (15658) [JE]	7269 (7829) [JE]	12324 (3915) [JE]	18421 (1958) [iJ]	27881 (979) [iJ]
finan512	162 (37376) [Ch2.0]	324 (18688) [Ch2.0]	648 (9344) [Ch2.0]	1296 (4672) [Ch2.0]	2592 (2336) [Ch2.0]	11192 (1168) [pM4.0]
fe_tooth	3850 (39068) [mpM4.0]	7605 (19534) [iJ]	12850 (9767) [iJ]	18804 (4884) [iJ]	26642 (2442) [iJ]	36766 (1221) [iJ]
fe_rotor	2103 (49809) [mpM4.0]	8097 (24905) [Ch2.0]	14953 (12453) [Ch2.0]	21241 (6227) [iJ]	34320 (3114) [iJ]	52626 (1557) [pM4.0]
598a	2411 (55486) [MQI]	8379 (27743) [Ch2.0]	17223 (13872) [Ch2.0]	28152 (6936) [iJ]	42088 (3468) [iJ]	59708 (1734) [iJ]
fe_ocean	465 (71719) [mpM4.0]	1923 (35860) [JE]	4760 (17930) [N/A]	8622 (8965) [iJ]	14277 (4483) [iJ]	22301 (2242) [iJ]
144	6491 (72325) [MQI]	15964 (36163) [N/A]	27751 (18082) [N/A]	39856 (9041) [N/A]	58659 (4521) [iJ]	82123 (2261) [iJ]
wave	8735 (78159) [SDP]	18774 (39080) [iJ]	32204 (19540) [iJ]	47277 (9770) [iJ]	66891 (4885) [iJ]	91784 (2443) [iJ]
m14b	3836 (107383) [MQI]	14013 (53692) [Ch2.0]	28128 (26846) [pM4.0]	45362 (13423) [iJ]	68468 (6712) [N/A]	103946 (3356) [iJ]
auto	10173 (224348) [MQI]	29409 (112174) [iJ]	53326 (56087) [pM4.0]	83748 (28044) [iJ]	131236 (14022) [iJ]	182934 (7011) [iJ]

Results with up to 1% imbalance
S_max <= 1.01 x S_opt

graph	2	4	8	16	32	64
add20	607 (1209) [MQI]	1203 (599) [JE]	1758 (300) [iJ]	2216 (150) [iJ]	2765 (75) [JE]	3266 (38) [JE]
data	188 (1438) [AMG]	425 (717) [iJ]	719 (358) [iJ]	1245 (179) [Ch2.0]	2004 (90) [iJ]	3016 (45) [iJ]
3elt	89 (2382) [GrPart]	199 (1186) [JE]	349 (590) [JE]	589 (295) [JE]	972 (148) [JE]	1594 (74) [iJ]
uk	19 (2414) [AMG]	44 (1206) [JE]	86 (608) [JE]	157 (305) [JE]	285 (152) [iJ]	456 (76) [iJ]
add32	10 (2481) [J2.2]	33 (1241) [JE]	69 (621) [JE]	117 (311) [JE]	212 (156) [JE]	720 (78) [Ch2.0]
bcsstk33	10109 (4407) [GrPart]	21685 (2203) [iJ]	35088 (1093) [iJ]	55546 (551) [iJ]	79121 (275) [iJ]	109585 (137) [iJ]
whitaker3	126 (4908) [JE]	380 (2458) [JE]	660 (1231) [JE]	1110 (613) [JE]	1719 (307) [JE]	2579 (154) [iJ]
crack	183 (5161) [AMG]	368 (2560) [JE]	678 (1291) [N/A]	1124 (640) [JE]	1707 (323) [iJ]	2623 (161) [iJ]
wing_nodal	1696 (5522) [MQI]	3572 (2747) [JE]	5443 (1368) [JE]	8422 (684) [JE]	12228 (342) [iJ]	16221 (172) [iJ]
fe_4elt2	130 (5572) [MRSB]	349 (2786) [JE]	611 (1402) [iJ]	1028 (697) [JE]	1677 (349) [JE]	2537 (175) [iJ]
vibrobox	10310 (6184) [JE]	19245 (3082) [JE]	25001 (1556) [iJ]	33468 (771) [iJ]	43415 (388) [JE]	50849 (194) [JE]
bcsstk29	2818 (7008) [GrPart]	8786 (3498) [MRSB]	16505 (1758) [iJ]	24706 (875) [iJ]	37810 (441) [iJ]	60795 (220) [iJ]
4elt	138 (7844) [GrPart]	327 (3902) [JE]	556 (1951) [JE]	961 (985) [iJ]	1606 (488) [JE]	2689 (246) [iJ]
fe_sphere	386 (8193) [JE]	768 (4098) [N/A]	1152 (2060) [JE]	1730 (1033) [iJ]	2565 (516) [iJ]	3663 (257) [JE]
cti	318 (8480) [JE]	967 (4247) [N/A]	1812 (2105) [JE]	2915 (1053) [JE]	4460 (527) [iJ]	6125 (265) [iJ]
memplus	5492 (8937) [JE]	9754 (4440) [JE]	11939 (2241) [iJ]	13742 (1110) [JE]	14830 (555) [iJ]	17446 (278) [JE]
cs4	367 (11351) [JE]	940 (5638) [JE]	1476 (2840) [N/A]	2206 (1407) [JE]	3110 (704) [iJ]	4223 (352) [iJ]
bcsstk30	6335 (14603) [GrPart]	16622 (7301) [N/A]	34604 (3649) [JE]	72007 (1808) [JE]	120468 (912) [iJ]	180470 (456) [iJ]
bcsstk31	2701 (17965) [GrPart]	7879 (8898) [pM4.0]	14426 (4449) [pM4.0]	25491 (2225) [iJ]	39440 (1113) [iJ]	63626 (561) [iJ]
fe_pwt	340 (18260) [GrPart]	705 (9139) [JE]	1442 (4583) [JE]	2855 (2283) [JE]	5779 (1152) [iJ]	8454 (576) [iJ]
bcsstk32	4667 (22305) [JE]	10578 (11153) [JE]	22826 (5577) [JE]	39682 (2790) [JE]	65389 (1407) [iJ]	102820 (698) [JE]
fe_body	262 (22544) [MQI]	703 (11272) [pM4.0]	1197 (5637) [pM4.0]	1981 (2819) [pM4.0]	3370 (1423) [iJ]	5518 (711) [iJ]
t60k	77 (30299) [AMG]	213 (15027) [iJ]	467 (7534) [N/A]	878 (3783) [N/A]	1450 (1892) [iJ]	2277 (938) [iJ]
wing	787 (31278) [MQI]	1666 (15508) [JE]	2589 (7754) [JE]	4198 (3877) [JE]	6074 (1957) [iJ]	8161 (978) [iJ]
brack2	708 (31614) [GrPart]	3090 (15658) [JE]	7269 (7829) [JE]	12324 (3915) [JE]	18421 (1958) [iJ]	27881 (979) [iJ]
finan512	162 (37376) [Ch2.0]	324 (18688) [Ch2.0]	648 (9344) [Ch2.0]	1296 (4672) [Ch2.0]	2592 (2336) [Ch2.0]	11192 (1168) [pM4.0]
fe_tooth	3823 (39456) [SDP]	7435 (19725) [iJ]	12850 (9767) [iJ]	18435 (4928) [iJ]	26642 (2442) [iJ]	36487 (1233) [iJ]
fe_rotor	2049 (50305) [GrPart]	8097 (24905) [Ch2.0]	14028 (12576) [iJ]	20773 (6288) [iJ]	33686 (3144) [iJ]	50912 (1572) [iJ]
598a	2388 (55856) [MQI]	8311 (27985) [N/A]	16594 (14010) [iJ]	27344 (7005) [iJ]	41124 (3502) [iJ]	59152 (1751) [iJ]
fe_ocean	387 (72425) [GrPart]	1911 (36195) [N/A]	4760 (17930) [N/A]	8507 (9049) [iJ]	13767 (4526) [iJ]	21854 (2263) [iJ]
144	6479 (72980) [MQI]	15345 (36366) [N/A]	25818 (18201) [N/A]	39856 (9041) [N/A]	58659 (4521) [iJ]	81145 (2268) [N/A]
wave	8682 (78934) [MQI]	18058 (39395) [iJ]	32204 (19540) [iJ]	46903 (9860) [iJ]	65926 (4933) [iJ]	91304 (2466) [iJ]
m14b	3826 (107831) [MQI]	14013 (53692) [Ch2.0]	28128 (26846) [pM4.0]	44515 (13433) [N/A]	68468 (6712) [N/A]	101980 (3382) [N/A]
auto	10042 (226571) [SDP]	29158 (112676) [iJ]	53158 (56646) [iJ]	82901 (28256) [iJ]	130818 (14160) [iJ]	182890 (7079) [iJ]

Results with up to 3% imbalance
S_max <= 1.03 x S_opt

graph	2	4	8	16	32	64
add20	579 (1233) [MQI]	1188 (616) [JE]	1720 (308) [iJ]	2216 (150) [iJ]	2758 (76) [JE]	3266 (38) [JE]
data	185 (1465) [AMG]	383 (733) [iJ]	708 (367) [iJ]	1195 (183) [Ch2.0]	1970 (91) [iJ]	2911 (46) [iJ]
3elt	87 (2398) [JE]	199 (1186) [JE]	336 (607) [JE]	566 (303) [JE]	958 (151) [N/A]	1552 (75) [N/A]
uk	18 (2455) [JE]	41 (1228) [JE]	82 (620) [JE]	154 (308) [N/A]	265 (155) [N/A]	455 (77) [iJ]
add32	10 (2481) [J2.2]	33 (1241) [JE]	69 (621) [JE]	117 (311) [JE]	212 (156) [JE]	624 (80) [pM4.0]
bcsstk33	10064 (4419) [AMG]	21423 (2250) [iJ]	34322 (1124) [iJ]	55546 (551) [iJ]	79121 (275) [iJ]	109348 (140) [iJ]
whitaker3	126 (4908) [JE]	380 (2458) [JE]	658 (1261) [JE]	1092 (630) [JE]	1686 (315) [JE]	2535 (157) [JE]
crack	182 (5224) [AMG]	360 (2616) [JE]	676 (1309) [JE]	1082 (659) [JE]	1679 (329) [N/A]	2592 (164) [JE]
wing_nodal	1680 (5629) [SDP]	3566 (2796) [JE]	5401 (1407) [JE]	8316 (704) [JE]	12024 (352) [JE]	16221 (172) [iJ]
fe_4elt2	130 (5572) [MRSB]	349 (2786) [JE]	603 (1429) [JE]	1007 (717) [JE]	1651 (358) [JE]	2537 (175) [iJ]
vibrobox	10310 (6184) [JE]	19245 (3082) [JE]	24874 (1587) [JE]	32002 (793) [iJ]	42582 (396) [iJ]	50849 (194) [JE]
bcsstk29	2818 (7008) [GrPart]	8541 (3600) [J2.2]	16505 (1758) [iJ]	24706 (875) [iJ]	37810 (441) [iJ]	58452 (225) [iJ]
4elt	137 (8017) [JE]	319 (3966) [N/A]	527 (2009) [N/A]	916 (1004) [JE]	1537 (502) [JE]	2581 (251) [JE]
fe_sphere	384 (8289) [JE]	766 (4155) [JE]	1152 (2060) [JE]	1706 (1053) [N/A]	2477 (527) [JE]	3547 (263) [JE]
cti	318 (8480) [JE]	917 (4331) [JE]	1716 (2160) [JE]	2778 (1080) [JE]	4236 (542) [iJ]	5992 (271) [iJ]
memplus	5407 (9140) [JE]	9664 (4542) [JE]	11939 (2241) [iJ]	13559 (1143) [JE]	14548 (571) [iJ]	17409 (285) [JE]
cs4	362 (11586) [AMG]	936 (5704) [JE]	1472 (2861) [N/A]	2126 (1448) [N/A]	3110 (704) [iJ]	4196 (362) [iJ]
bcsstk30	6251 (14679) [JE]	16617 (7341) [JE]	34559 (3666) [JE]	70768 (1851) [JE]	117232 (930) [JE]	178578 (465) [JE]
bcsstk31	2676 (18184) [MLSATS]	7879 (8898) [pM4.0]	14426 (4449) [pM4.0]	25160 (2290) [iJ]	38572 (1145) [iJ]	61066 (572) [iJ]
fe_pwt	340 (18260) [GrPart]	704 (9365) [JE]	1436 (4701) [JE]	2784 (2338) [JE]	5606 (1175) [JE]	8346 (587) [iJ]
bcsstk32	4667 (22305) [JE]	9728 (11286) [JE]	21307 (5741) [JE]	38929 (2864) [JE]	64302 (1435) [iJ]	96168 (717) [iJ]
fe_body	262 (22544) [MQI]	703 (11272) [pM4.0]	1197 (5637) [pM4.0]	1981 (2819) [pM4.0]	3223 (1451) [iJ]	5502 (725) [iJ]
t60k	71 (30795) [AMG]	211 (15219) [iJ]	467 (7534) [N/A]	852 (3862) [N/A]	1420 (1922) [iJ]	2258 (958) [iJ]
wing	774 (31824) [MQI]	1636 (15815) [JE]	2551 (7894) [JE]	4015 (3966) [JE]	6028 (1996) [JE]	8161 (978) [iJ]
brack2	684 (32168) [JE]	2864 (16127) [JE]	7080 (8057) [JE]	11958 (4030) [JE]	17952 (2015) [JE]	27345 (1007) [iJ]
finan512	162 (37376) [Ch2.0]	324 (18688) [Ch2.0]	648 (9344) [Ch2.0]	1296 (4672) [Ch2.0]	2592 (2336) [Ch2.0]	10821 (1203) [N/A]
fe_tooth	3792 (40210) [SDP]	7435 (19725) [iJ]	12850 (9767) [iJ]	18435 (4928) [iJ]	26642 (2442) [iJ]	36030 (1257) [iJ]
fe_rotor	1965 (51065) [SDP]	8097 (24905) [Ch2.0]	14028 (12576) [iJ]	20773 (6288) [iJ]	33686 (3144) [iJ]	47972 (1603) [iJ]
598a	2367 (56705) [MQI]	7978 (28520) [N/A]	16031 (14286) [N/A]	26257 (7143) [N/A]	40792 (3571) [N/A]	58454 (1784) [iJ]
fe_ocean	311 (73322) [GrPart]	1704 (36802) [N/A]	4019 (18436) [N/A]	7838 (9223) [N/A]	12746 (4616) [N/A]	21854 (2263) [iJ]
144	6438 (74281) [MQI]	15250 (37037) [N/A]	25611 (18523) [N/A]	38478 (9311) [N/A]	58659 (4521) [iJ]	80894 (2287) [N/A]
wave	8616 (80306) [SDP]	18058 (39395) [iJ]	30895 (20087) [iJ]	46487 (10056) [iJ]	64953 (5027) [iJ]	88383 (2515) [iJ]
m14b	3823 (108879) [MQI]	14013 (53692) [Ch2.0]	27711 (27431) [iJ]	44174 (13785) [iJ]	68468 (6712) [N/A]	101980 (3382) [N/A]
auto	9782 (230275) [SDP]	29158 (112676) [iJ]	48398 (57769) [iJ]	82901 (28256) [iJ]	130310 (14437) [iJ]	180562 (7211) [iJ]

Results with up to 5% imbalance
S_max <= 1.05 x S_opt

graph	2	4	8	16	32	64
add20	551 (1256) [MQI]	1184 (628) [iJ]	1705 (314) [iJ]	2186 (157) [MLSATS]	2758 (76) [JE]	3266 (38) [JE]
data	181 (1497) [SDP]	378 (746) [iJ]	702 (374) [iJ]	1195 (183) [Ch2.0]	1922 (93) [iJ]	2911 (46) [iJ]
3elt	87 (2398) [JE]	199 (1186) [JE]	334 (617) [iJ]	566 (303) [JE]	958 (151) [N/A]	1552 (75) [N/A]
uk	18 (2455) [JE]	41 (1228) [JE]	82 (620) [JE]	154 (308) [N/A]	265 (155) [N/A]	436 (79) [iJ]
add32	10 (2481) [J2.2]	33 (1241) [JE]	69 (621) [JE]	117 (311) [JE]	212 (156) [JE]	624 (80) [pM4.0]
bcsstk33	9914 (4554) [iJ]	21229 (2293) [iJ]	34117 (1145) [iJ]	55546 (551) [iJ]	78821 (286) [iJ]	108249 (143) [iJ]
whitaker3	126 (4908) [JE]	380 (2458) [JE]	658 (1261) [JE]	1092 (630) [JE]	1686 (315) [JE]	2535 (157) [JE]
crack	182 (5224) [AMG]	360 (2616) [JE]	676 (1309) [JE]	1082 (659) [JE]	1679 (329) [N/A]	2590 (168) [iJ]
wing_nodal	1668 (5742) [SDP]	3566 (2796) [JE]	5387 (1429) [MLSATS]	8316 (704) [JE]	12024 (352) [JE]	16102 (179) [iJ]
fe_4elt2	130 (5572) [MRSB]	349 (2786) [JE]	597 (1457) [iJ]	1007 (717) [JE]	1651 (358) [JE]	2516 (182) [iJ]
vibrobox	10310 (6184) [JE]	19245 (3082) [JE]	24158 (1603) [iJ]	31695 (809) [iJ]	41176 (404) [iJ]	50757 (202) [iJ]
bcsstk29	2818 (7008) [GrPart]	8088 (3672) [MLSATS]	15314 (1836) [MLSATS]	24706 (875) [iJ]	36731 (456) [iJ]	58108 (229) [iJ]
4elt	137 (8017) [JE]	319 (3966) [N/A]	527 (2009) [N/A]	916 (1004) [JE]	1537 (502) [JE]	2581 (251) [JE]
fe_sphere	384 (8289) [JE]	766 (4155) [JE]	1152 (2060) [JE]	1692 (1074) [iJ]	2477 (527) [JE]	3547 (263) [JE]
cti	318 (8480) [JE]	917 (4331) [JE]	1716 (2160) [JE]	2778 (1080) [JE]	4236 (542) [iJ]	5907 (276) [iJ]
memplus	5353 (9322) [iJ]	9427 (4652) [MLSATS]	11939 (2241) [iJ]	13279 (1165) [iJ]	14384 (582) [iJ]	17409 (285) [JE]
cs4	356 (11794) [AMG]	936 (5704) [JE]	1472 (2861) [N/A]	2126 (1448) [N/A]	3080 (737) [iJ]	4196 (362) [iJ]
bcsstk30	6251 (14679) [JE]	16617 (7341) [JE]	34559 (3666) [JE]	70768 (1851) [JE]	117232 (930) [JE]	177379 (474) [iJ]
bcsstk31	2676 (18184) [MLSATS]	7879 (8898) [pM4.0]	13561 (4670) [iJ]	24179 (2331) [iJ]	38572 (1145) [iJ]	60446 (583) [iJ]
fe_pwt	340 (18260) [GrPart]	704 (9365) [JE]	1436 (4701) [JE]	2784 (2338) [JE]	5606 (1175) [JE]	8310 (599) [iJ]
bcsstk32	4667 (22305) [JE]	9728 (11286) [JE]	21307 (5741) [JE]	38320 (2923) [iJ]	62961 (1463) [iJ]	96168 (717) [iJ]
fe_body	262 (22544) [MQI]	703 (11272) [pM4.0]	1145 (5885) [iJ]	1833 (2952) [iJ]	3223 (1451) [iJ]	5219 (739) [iJ]
t60k	65 (31437) [SDP]	211 (15219) [iJ]	467 (7534) [N/A]	852 (3862) [N/A]	1420 (1922) [iJ]	2221 (984) [iJ]
wing	770 (32550) [MQI]	1636 (15815) [JE]	2551 (7894) [JE]	4015 (3966) [JE]	6010 (2031) [iJ]	8161 (978) [iJ]
brack2	660 (32600) [SDP]	2808 (16439) [MLSATS]	7080 (8057) [JE]	11958 (4030) [JE]	17952 (2015) [JE]	26944 (1027) [iJ]
finan512	162 (37376) [Ch2.0]	324 (18688) [Ch2.0]	648 (9344) [Ch2.0]	1296 (4672) [Ch2.0]	2592 (2336) [Ch2.0]	10821 (1203) [N/A]
fe_tooth	3773 (40567) [SDP]	7152 (20405) [MLSATS]	12646 (10071) [iJ]	18435 (4928) [iJ]	26016 (2563) [MLSATS]	36030 (1257) [iJ]
fe_rotor	1957 (51783) [SDP]	8097 (24905) [Ch2.0]	13184 (12999) [iJ]	20773 (6288) [iJ]	33686 (3144) [iJ]	47852 (1633) [iJ]
598a	2336 (57855) [MQI]	7978 (28520) [N/A]	16031 (14286) [N/A]	26257 (7143) [N/A]	40179 (3641) [iJ]	58307 (1820) [iJ]
fe_ocean	311 (73322) [GrPart]	1704 (36802) [N/A]	4019 (18436) [N/A]	7838 (9223) [N/A]	12746 (4616) [N/A]	21784 (2353) [iJ]
144	6362 (75917) [SDP]	15250 (37037) [N/A]	25611 (18523) [N/A]	38478 (9311) [N/A]	58142 (4701) [N/A]	80445 (2373) [N/A]
wave	8563 (81841) [MQI]	18058 (39395) [iJ]	30583 (20514) [MLSATS]	44625 (10258) [MLSATS]	63725 (5129) [iJ]	88383 (2515) [iJ]
m14b	3802 (112532) [MQI]	14013 (53692) [Ch2.0]	27711 (27431) [iJ]	44174 (13785) [iJ]	68468 (6712) [N/A]	101385 (3523) [iJ]
auto	9450 (235532) [MQI]	29158 (112676) [iJ]	48221 (58885) [iJ]	82901 (28256) [iJ]	127433 (14722) [iJ]	179464 (7360) [iJ]