Theoretical computer scientists can fail (as a researcher) if their proof is wrong. An applied algorithms person though, your proofs can be correct, theorems deep, and you can still fail. It is like being an engineer, your assumptions have to hold. Here are examples:
- I once gave a talk on scheduling problems that arise when you use broadcasts from the base station to wireless laptops. Broadcast means if you have to send the same bits to many laptops, you can do it with a single copy, so it is efficient. It also gives nice abstract problems, and I was on a roll, showing 2-opts or ptases. In the audience was a systems researcher who slayed me with a simple question: how do you know the bits were received correctly? Well, each of the laptops should ack. Then chances are a subset of them will fail. So, you have to rebroadcast, now to specific subset of laptops, and iterate. The model then becomes messier, results less clear.
- I once heard someone give a talk on network routing in presence of edge deletions. The motivation was if a truck ran over a cable and cut it, the link between the two routers will disappear. So, you want to compute reroutes. A systems researcher in the audience says, but physical links are bunched together into large cables, so (a) if there is a cut, bunch of links will go down simultaneously and (b) while you can determine the logical links between routers easily, say by looking at the routing table, it is difficult to get the operations people to tell you how they bunched wires together. That is, physical world of wires is different from the logical world of links, and indecipherable. Alas.
- Then there are times when you look for a theory and fail. I looked at problems where the longer you run the algorithms, better the approximations. The quality of solutions found by the algorithm is like a counter getting progressively close to the OPT. You can stop the computation any time you are happy with the accuracy. A bunch of us called his "progressive algorithms" and spent a long time searching for a theory of such algorithms. No luck.