We study combinatorial optimization problems on graphs in the mean-field model, which assigns independent and identically distributed random weights to the edges of the graph. Specifically, we focus on two generalizations ...