Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects

09/07/2020
by   Alan Frieze, et al.
0

We consider cost constrained versions of the minimum spanning tree problem and the assignment problem. We assume edge weights are independent copies of a continuous random variable Z that satisfies F(x)=(Z≤ x)≈ x^α as x→0, where α≥ 1. Also, there are r=O(1) budget constraints with edge costs chosen from the same distribution. We use Lagrangean duality to construct polynomial time algorithms that produce asymptotically optimal solutions. For the spanning tree problem, we allow r>1, but for the assignment problem we can only analyse the case r=1.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset