Not logged in
Log in now
Create an account
Subscribe to LWN
LWN.net Weekly Edition for June 20, 2013
Pencil, Pencil, and Pencil
Dividing the Linux desktop
LWN.net Weekly Edition for June 13, 2013
A report from pgCon 2013
Actually, I'm pretty sure that's NP-hard, at least for some definitions of optimal. So it might very well be counterproductive to spend the time obtaining an optimal scheduling.
Per-entity load tracking
Posted Jan 11, 2013 9:06 UTC (Fri) by ekj (guest, #1524)
I know you didn't claim that, it's just that I've seen one-to-many arguments that consist of "NP-hard, therefore not doable"
If a problem scales as 1.1**n and n is expected to be 100 at most, then it's easily doable (barring huge constant factors), a n**7 algorithm is actually more computationally intensive up to a n of about 350.
I don't know how large the problem-space tends to be for scheduling-problems though.
Posted Jan 24, 2013 1:33 UTC (Thu) by igorrs (guest, #88981)
If you were after PERFECT scheduling, finding the solution would require actual prediction of the future (with a crystal ball, for example ;-)). Time complexity was not at stake in that specific sentence.
Copyright © 2013, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds