Not logged in
Log in now
Create an account
Subscribe to LWN
LWN.net Weekly Edition for December 5, 2013
Deadline scheduling: coming soon?
LWN.net Weekly Edition for November 27, 2013
ACPI for ARM?
LWN.net Weekly Edition for November 21, 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 (subscriber, #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