Problems column

The open research problems, coming from papers presented at the European Symposium on Algorithms (ESA), held in Mallorca, Spain in Oct 2005 were discussed. A solution to the brain teaser from Donald Knuth related to graph theory was also presented. The problem of multiple stream jitter regulation was also addressed and a model was suggested for permitting a certain amount of cell-dropping, and examining the correlations between buffer size, optimal jitter, and drop ratio. It was suggested that the minimum size, bounded capacity cut (MinSBCC) problem which arises in practical settings, such as in epidemiology, disaster control, as well as finding dense subgraphs and communities in graphs was also described. The solution to the problem of scheduling a set of independent jobs on identical parallel machines subject to migration delays so as to minimize workspan was also elaborated.