Varying Constraints

This is an open problem in competitive mathematical programming. Levina et al. (2007) developed an algorithm (based on the Strong Aggregating Algorithm) in competitive on-line linear programming with strong performance guarantees. However, they only consider sequences of problems with the same constraints; only the cost vector (i.e., the objective function) changes in time. Is it possible to extend their results to time-varying constraints?


  • Tatsiana Levina, Yuri Levin, Jeff McGill, and Mikhail Nediak (2007). Linear programming with online learning. Operations Research Letters, 35, 612-618.