= Carla P. Gomes
{c}
\b[Carla P. Gomes] studies <algorithms> for difficult search problems. With <Bart Selman>, she investigated <algorithm portfolios>: policies that combine candidate <algorithms> or randomized runs to exploit complementary <runtime> behavior. Their 2001 paper compared concurrent execution, interleaving and restart policies under specified problem distributions.<Algorithm portfolios by Carla P. Gomes and Bart Selman>[Page43, byline and Abstract; sections4–5, portfolio comparisons]{ref}
A portfolio's benefit depends on how its runs behave together. For an original model, let one <randomized algorithm> finish in one second with <probability> $1/2$ and in ten seconds otherwise. Its <expected value> of completion time is $5.5$ seconds. Run two copies on separate full-speed <CPUs> and stop both at the first acceptable answer. With <independent random variables> for their completion times, both are slow with <probability> $1/4$, so mean wall time is
$$
\frac34(1)+\frac14(10)=3.25\ \mathrm{seconds}.
$$
If their completion times are identical on every trial, that mean remains $5.5$ seconds. Different run labels do not establish independence.
The faster wall time also has a resource cost. In the stipulated independent model, both <CPUs> run until the first completion, consuming mean total work $2(3.25)=6.5$ CPU-seconds. This exceeds the single-run mean even though the answer arrives sooner. Gomes and Selman's portfolio approach makes such choices explicit: a useful policy is assessed against its workload, stopping rule and resource budget, rather than presumed universally faster.
\Image[https://people.as.cornell.edu/sites/default/files/styles/person_image/public/2025-09/20221148006.jpg]
{title=Carla P. Gomes, named portrait in Cornell University's faculty profile}
{height=300}
Back to article page
