Revenue management practices often include overbooking capacity to account for customers who make reservations but do not show up. In this paper, we consider the network revenue management problem with no-shows and overbooking, where the show up probabilities are specific to each product. We propose a randomized linear program to jointly make the capacity control and overbooking decisions. We establish that our solution method gives an upper bound on the optimal expected total profit and that this upper bound is tighter than that obtained by the standard deterministic
linear program that appears in the existing literature. We describe how the randomized linear program can be used to obtain a bid price control policy. Numerical experiments indicate that our approach can provide significant improvements over standard benchmark methods.