Computer Science – Computer Science and Game Theory
Scientific paper
2009-11-16
Computer Science
Computer Science and Game Theory
Scientific paper
We consider the online linear programming problem where the constraint matrix is revealed column by column along with the objective function. We provide a 1-o(1) competitive algorithm for this surprisingly general class of online problems under the assumption of random order of arrival and some mild conditions on the right-hand-side input. Our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, the price learned from the previous steps is used to determine the decision for the current step. Our result provides a common near-optimal solution to a wide range of online problems including online routing and packing, online combinatorial auction, online adwords matching, many secretary problems, and various resource allocation and revenue management problems. Apart from online problems, the algorithm can also be applied for fast solution of large linear programs by sampling the columns of constraint matrix.
Agrawal Shipra
Wang Zizhuo
Ye Yinyu
No associations
LandOfFree
A Dynamic Near-Optimal Algorithm for Online Linear Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Dynamic Near-Optimal Algorithm for Online Linear Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Dynamic Near-Optimal Algorithm for Online Linear Programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-498981