Skip to main content
eScholarship
Open Access Publications from the University of California

Statistical Heuristic Selection for Graph Coloring

  • Author(s): Freer, Andrew Adams
  • Advisor(s): Potkonjak, Miodrag
  • et al.
Abstract

Although a heuristic algorithm's usefulness is grounded in its empirical performance on a set of problem instances, much of recent graph coloring heuristic development neglects statistical methodology in several important ways. First, heuristic parameters are often set in an ad-hoc, irreproducible fashion. Second, heuristic parameters are often tuned and evaluated on the same set of instances, causing over-tuning. Last, the common winner-take-all approach limits a heuristic's application to a very specific set of graph instances.

To address the above issues, we employ machine learning techniques to perform instance-based algorithm selection from a set of diverse heuristic algorithms, including multiple parameterizations of the same algorithm. The implemented strategy improves on a winner-take-all strategy by over a color on average on a set of IID random graphs when allowed a maximum runtime of approximately 15 minutes, and in general achieves near-optimal heuristic selection on unseen graphs.

Main Content
Current View