Best Computer Science School in Utah

Levi Pearson levi at
Wed Sep 26 11:13:44 MDT 2007

Barry Roberts <blr at> writes:

> I like to think of myself as a computer scientist, and the one thing I
> remember from my algorithms class all those years ago is that even if
> finding the optimal solution requires exponential time, the algorithm
> that is provably within 80% of optimal is polynomial.  Close enough is
> usually good enough (or provably optimal is usually not required).
> MacGyverism seems to match perfectly with what Dr. Campbell taught me IMHO.

In order to purposefully go with solutions you know are non-optimal,
you also need to be able to know how close to optimal you are.  I
don't think you can say, in general, that any polynomial time
algorithm to solve an exponential problem is going to give you 80% of
optimality.  So, you're back to needing theory to justify your
polynomial time algorithm as an acceptable compromise.

Well, I guess you don't NEED to, but your boss will probably be a lot
happier if you can describe the behavior of your core business
algorithm in detail rather than just saying, "Uh, it takes too long to
go through all the solutions to get the best one, so this other way
seems to get close most of the time and is fast enough on the cases I
tested it with."

It's no surprise that employers like ITA and Google, who work with
massive, complex data sets, are interested in people with CS theory.
And with hard drive and memory capacity going up, data sets are only
getting bigger.


More information about the PLUG mailing list