Carla P. Gomes

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.^[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 isIf 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.