History of the Core Experiments

• RMF-LONG, RMF-WIDE, WASH-RLG-LONG, WASH-RLG-WIDE, WASH-LINE-MODERATE, and AC-DENSE problem families were suggested, along with several other problem families, for the First DIMACS Challenge. Challenge results have shows that these problem families are useful. See Network Flows and Matching: First DIMACS Implementation Challenge, D. S. Johnson and C. C. McGeoch (editors), AMS, 1993.
  • The RMF families are generated using the genrmf generator, developed prior to the Challenge by Goldfarb and Grigoriadis. See A Computational Comparison of the Dinic and Network Simplex Methods for Maximum Flow, D. Goldfarb and M. D. Grigoriadis, Annals of Oper. Res. (13) 83-123, 1988.
  • The WASH families are generated using the washington generator, developed by Anderson and students in his seminar for the DIMACS Challenge.
  • The AC-DEBSE family is generated by the AC generator of Waissi.
• The AK generator was developed by Goldberg and Cherkassky in a study conducted after the DIMACS Challenge. Problems produced by this generator are hard for push-relabel algorithms with gap and global relabeling heuristics. The above-mentioned DIMACS problem families are much simpler in terms of assymptotic grouth. See On Implementing Push-Relabel Method for the Maximum Flow Problem, B. V. Cherkassky and A.V. Goldberg, Algorithmica (19), 390-410, 1997.
• The RMF-LONGER problem family was suggested by Goldberg, Levine, and Martin during an unpublished study of adaptive scaling algorithms. The motivation for this problem family was the observation that, except for WASH-LINE-MODERATE problems, in all other above-mentioned problem families push-relabel algorithms never relabeled a vertex with a distance label higher than sqrt (n). The new problem family causes non-scaling push-relabel algorithms to relabel vertices with high distance label values.