  The Network Revenue Management (NRM) problem is a well-known challenge in
dynamic decision-making under uncertainty. In this problem, fixed resources
must be allocated to serve customers over a finite horizon, while customers
arrive according to a stochastic process. The typical NRM model assumes that
customer arrivals are independent over time. However, in this paper, we explore
a more general setting where customer arrivals over different periods can be
correlated. We propose a model that assumes the existence of a system state,
which determines customer arrivals for the current period. This system state
evolves over time according to a time-inhomogeneous Markov chain. We show our
model can be used to represent correlation in various settings.
  To solve the NRM problem under our correlated model, we derive a new linear
programming (LP) approximation of the optimal policy. Our approximation
provides an upper bound on the total expected value collected by the optimal
policy. We use our LP to develop a new bid price policy, which computes bid
prices for each system state and time period in a backward induction manner.
The decision is then made by comparing the reward of the customer against the
associated bid prices. Our policy guarantees to collect at least $1/(1+L)$
fraction of the total reward collected by the optimal policy, where $L$ denotes
the maximum number of resources required by a customer.
  In summary, our work presents a Markovian model for correlated customer
arrivals in the NRM problem and provides a new LP approximation for solving the
problem under this model. We derive a new bid price policy and provides a
theoretical guarantee of the performance of the policy.
