In this paper, we present new approximation methods for the network revenue management problem with customer choice behavior. Our methods are sampling-based and so can handle very general customer choice models. The starting point for our methods is a dynamic program that allows randomization. An attractive feature of this dynamic program is that the size of its action space is linear in the number of itineraries, as opposed to exponential. It turns out that this dynamic program has a structure that is similar to the dynamic program for the network revenue management problem under the so called independent demand setting. Our approximation methods exploit this similarity and build on ideas developed for the independent demand setting. We present two approximation methods. The first one is based on relaxing the flight leg capacity constraints using Lagrange multipliers, whereas the second method involves solving a perfect hindsight relaxation problem. We show that both methods yield upper bounds on the optimal expected total revenue. Computational experiments demonstrate the tractability of our methods and indicate that they can generate tighter upper bounds and higher expected revenues when compared with the standard deterministic linear program that appears in the literature.