Our results demonstrate that the incorporation of soft compactness constraints substantially improves the timeliness and accuracy of outbreak detection. Our new approach based on additive linear-time subset scanning enables efficient maximization of penalized scan statistics over subsets of the data, thus improving detection of irregular clusters.