Recall that if the lengths of edges in the complete graph are drawn
independently from [0,1] then the expected value of the minimum spanning
tree is asymptotically equal to zeta(3). We consider analogous problems
where edges have not only a random length but also a random cost, and we
are interested in the length of the minimum-length structure whose total
cost is less than some cost budget.  For trees and arborescences we
determine asymptotically accurate estimates of the minimum cost. These
problems are NP-hard and we describe polynomial time algorithms.

This is joint with Tomasz Tkocz.

For several other classes of structures, we determine the correct
minimum length structure as a function of the cost-budget, up to
constant factors — shortest paths, minimum matchings, Traveling
Salesperson Problem.  Moreover, we achieve this even in the more general
setting where the distribution of weights and costs are arbitrary, so
long as the density f(x) as x–>0 behaves like cx^\gamma for some
$\gamma\geq 0$; previously, this case was not understood even in the
absence of cost constraints.  We also handle the case where each edge
has several independent costs associated to it, and we must
simultaneously satisfy budgets on each cost.  In this case, we show that
the minimum-length structure obtainable is essentially controlled by the
product of the cost thresholds.

This is joint with Wesley Pegden and Tomasz Tkocz.