Problems column

Samir Khuller*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)130-134
Number of pages5
JournalACM Transactions on Algorithms
Issue number1
StatePublished - 2006


  • Algorithms
  • Problems

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'Problems column'. Together they form a unique fingerprint.

Cite this