Algorithmic Complexity Attacks
Do you know of other resource consumption vulnerabilities that were caused by flawed algorithms?


this can be a subtle issue because basically any algorithm that processes requests with responses is subject to a Denial of Service attack vulnerability due to being overwhelmed with requests, such that even efficient algorithms can be overwhelmed. in a sense the algorithms are not considered "flawed" until an attacker exploits them, during an ongoing, adaptive race between hackers and researchers employing countermeasures. 

one famous example from history is the so-called Ping of Death which led to large attacks in 2000 against Yahoo, CNN, eBay, Dell, &amp; Amazon by the hacker "mafiaboy". ref [1] lists the 10 most famous attacks of the past 25 years several of which are DoS attacks. however, some other algorithms are not discovered to be inefficient until hackers find methods/attack vectors for "bogging them down" and the Apache vulnerability you mention apparently fits into that category. 

there are large amounts of research into DoS prevention techniques eg refs below.

[1] Hackers’ Most Destructive Attacks, DailyBeast

[2] Preventing Internet Denial-of-Service with Capabilities Anderson, Roscoe, Wetherall

[3] Denial of service attacks and how to defend against them Razmov

[4] Internet denial of service attacks and defense mechanisms Abliz