Overruns in newtheorem in latex

I don't know about the vldb class, but the clues you give suggest it's two column. With the amsthm package you get what you want and are also able to set the font in the body of the definition to upright, which is customary:

\documentclass[twocolumn]{article} \usepackage{amsthm} \theoremstyle{definition} \newtheorem{definition}{Definition} \begin{document} \begin{definition}[anonymity non-reconstructible fragmentation] aaa \end{definition} \end{document} 

By the way, subfigure has been obsolete for ten years; prefer subfig (possibly with the caption=false package, that might be required with the class you're using).

If the default \newtheorem is used, then the optional argument (your definition title) is set in a box as part of a list, hence being unbreakable. With minimal manual intervention, you can fix this:

\documentclass{article} \usepackage{lipsum}% http://ctan.org/pkg/lipsum \newtheorem{definition}{Definition} \begin{document} \begin{definition}[anonymity non-reconstructible fragmentation and then some] \lipsum[1] \end{definition} \begin{definition}\textbf{\upshape(anonymity non-reconstructible fragmentation and then some)} \lipsum[1] \end{definition} \end{document} 

The class vldb uses the kernel's \newtheorem, but with a redefinition of \@opargbegintheorem; as with the original definition, the annotation is placed as part of the optional argument of \item, so no line breaks are allowed. To correct this you can redefine \@opargbegintheorem so the annotation will be outside the optional argument for \item; with the appropriate settings you will respect the style used by the class.

Unfortunately, in this specific case, the word at the end of the line "fragmentation" will break at "frag" producing an overfull box (by 1.48pt), so perhaps a manual line break could be used. The example below shows two possible alternatives:

\documentclass{vldb} \usepackage{graphicx} \usepackage{subfigure} \usepackage{algorithmic} \usepackage{algorithm} \usepackage{url} \usepackage{times} \usepackage{lipsum} \makeatletter \def\@opargbegintheorem#1#2#3{\trivlist \item[\hskip\dimexpr\labelsep+10pt\relax{\scshape #1\ #2}](\textsc{#3}).\ \itshape} \makeatother \newtheorem{definition}{Definition} \begin{document} \begin{definition}[anonymity non-reconstructible fragmentation] \lipsum[4] \end{definition} \lipsum[4] \begin{definition}[anonymity non-reconstructible \\ fragmentation] \lipsum[4] \end{definition} \lipsum[4] \end{document}