Previous Up Next

10  Geometric graphs

We were able to beat the Leighton-Rao cuts of geometric graphs from our SODA-93 paper.
 graph      Leighton-Rao           Metis+MQI
 U10A   .0424 = 204 / 4811    0.0411 = 198 / 4821
 U10B   .0301 = 117 / 3883    0.0288 = 143 / 4968
 U10C   .0343 = 155 / 4522    0.0338 = 164 / 4858
 U10D   .0575 = 284 / 4937    0.0551 = 272 / 4936
 U10E   .0291 = 143 / 4908    0.0291 = 143 / 4908
 U30A   .0249 = 335 / 13467   0.0244 = 364 / 14940
U100K   .0156 = 692 / 44370   0.0146 = 717 / 49171

Previous Up Next