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


UCLA Electronic Theses and Dissertations bannerUCLA

Statistical Heuristic Selection for Graph Coloring


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
For improved accessibility of PDF content, download the file to your device.
Current View