I didn't believe the optimal algorithm is linear time, so I checked the source:

  a simple register allocation algorithm can achieve most ot the performance of the more complex algorithms: linear-scan register allocation, developed by Poletto and Sarkar

"Most of the performance" is not optimal. Were you referring to a different source?