Computing Science Problem Reformulation and Search Etcetera, etcetera, etcetera

  Home Page
  Source Code
  Et cetera

Interesting research directions that emerged as a result of the project are:

  • Theoretical time complexity transitions NP -> P -> NP in the continuum of mixed routing - scheduling problems as we move from shop scheduling to vehicle routing by removing types of constraints. Can there be other cyclic time complexity transitions? Is this phenomenon unique or can it be observed in other problem classes?
  • Transformations of associated graphs. We observed that there can be graph transformations that influence the behaviour of algorithms for finding solutions to the VRP and JSP. Can we come up with classes of such transformations, not just single examples? If these classes exist, can we optimize the desired output of the transformations?
  • Symmetry and Local Search. A deeper understanding needs to be developed of how symmetry influences the quality of local search techniques for scheduling problems.
  • Reformulation of algorithms. Are there analogies elsewhere to the demonstrated similarity of arc consistency and the Gale Shapley algorithm for Stable Marriage?

See Project History for more details.