Dynamic Programming

A Class of Hybrid Methods for Revenue Management

  • William Cooper
  • Tito Homem-de-Mello
    • Categories Dynamic Programming, Stochastic Programming, Yield Management

    We consider a Markov decision process model of a network revenue management problem. Working within this formal framework, we study policies that combine aspects of mathematical programming approaches and pure Markov decision process methods. The policies employ heuristics early in the booking horizon, and switch to a more-detailed decision rule closer to the time of … Read more

    Solving Stability Problems on a Superclass of Interval Graphs

  • Carlo Mannino
  • Gianpaolo Oriolo
    • Categories Dynamic Programming, Graphs and Matroids, Telecommunications Tags , , ,

    We introduce a graph invariant, called thinness, and show that a maximum weighted stable set on a graph $G(V, E)$ with thinness $k$ may be found in $O(\frac{|V|}{k})^k$-time, if a certain representation is given. We show that a graph has thinness 1 if and only if it is an interval graph, while a graph with … Read more