Future Work

• Does “fast” translate into “fast enough”?

  • need to test algorithm on challenge problem
  • other resource types may give more complex search spaces and may need more complex interaction between schedulers

• Application-specific models of performance

  • explicit relationship between g and “quality of solution”

• Different classes of local, iterative-repair algorithm

  • e.g., activation based on local measures of degree of conflict
    • measures maintained by diffusion scheme
  • dynamic determination of chromatic number & #colors
    • we already have prototype algorithm

• Open problems (for dynamics/complexity groups?):

  • reliable performance predictors from simple graph metrics
    • e.g., chromatic number, degree of interconnection
    • metrics need to be locally & cheaply computable for use at run-time
  • convergence models for over-constrained coloring
  • improved analysis ® improved algorithms