Coping with the Unknown in the Battlefield and on the Auction Block
In this talk, we discuss algorithms that cope with unknown, rapidly-changing environments in two settings. The algorithms are analyzed using both experimental and analytical methods.
We first describe logistics algorithms for maximizing operational availability of combat vehicles by producing flexible, optimized inventory and delivery plans that decrease replenishment times and prioritize parts allocations and repairs. Our algorithms are designed to leverage real-time information available from modern communications and inventory-tracking technology by employing mathematical optimization models. The algorithms were implemented and tested using a logistics simulator that generates detailed battlefield scenario.
Next, we study a problem related to pricing of products and services over time. We consider a collection of bidders, each of whom is interested in buying a copy of an item for which there is an unlimited supply. Every bidder is associated with a time interval over which the bidder will consider buying, and a maximum value the bidder is willing to pay. For every unit of time, the seller sets a price for the item. The seller's goal is to set the prices in order to maximize revenue over the time period. In the offline setting, we assume that the seller knows the bids of all the bidders in advance. In the online setting, we assume that at each unit of time the seller only knows the values of the bids that have arrived before or at that time unit. We provide a polynomial-time offline algorithm and prove upper and lower bounds on the competitiveness of deterministic and randomized online algorithms for two variants of the problem.
Baruch Schieber, IBM T.J. Watson Research Center
