Amitabh Chaudhary's Research Projects

How much milk should Martin's Supermarkets order?

 National Science Foundation's logo
Like most supermarkets, our local Martin's Supermarkets in South Bend find it hard to accurately forecast the demand for milk, particularly for stores catering to students. But if they order too much milk, they likely face spoilage, and if they order too little, they likely face lost profits and unhappy customers. Their dilemma is but one instance of one of the hardest problems in operations research, the newsvendor problem.

The newsvendor problem is traditionally approached by modeling the demand stochastically, and then choosing the order amount that maximizes the expected profits. But for several products, such as supermarket perishables, consumer electronics, and even the influenza vaccine, stochastic models of demand are often grossly inaccurate, resulting in losses of billions of dollars across several industries.

In this project funded by Algorithmics Foundation Program, NSF, we are developing a radical alternate solution on the lines of online computing, which is inherently non-stochastic and worst-case. Our algorithms are the first ever that guarantee a minimum performance, even in the worst-case. Their guarantees hold even if the demand is censored—when they are told the just sales in the previous step, and not the actual demand.

Tests on Martin's sales data show our algorithms outperforming other known approaches(for some products our algorithms are the only ones turning in a profit). More importantly, their performance is steady across different products, and mostly unaffected by the skew in the demand distribution—exactly how good online algorithms behave.

Publications

Caching for global scientific collaborations

We are in a new age of global collaborations in science and medicine, thanks largely to scientific repositories that make data available to every corner of the Internet. Making the access to these data-intensive repositories efficient from every corner of the Internet is, however, a challenge for different technologies in distributed systems. This includes caching, the process of strategically storing copies of popular data to avoid repeated network requests for it. Effective caching is crucial to prevent these repositories from clogging the networks.

Existing algorithms for caching, designed either for memory hierarchies or for the web, are insufficient for repositories built on relational databases. New algorithms that understand how data is stored in relational databases, accessed by queries, updated, and processed in parallel by multiple computing units are indispensable for the next generation of caches.

We are designing the first online caching algorithms for dynamic data stored in relational databases. Even in the worst-case, the costs incurred by our algorithm as compared to those incurred by an (imaginary) offline optimal algorithm—which has complete knowledge of the requests in the future—will never be more, except for a factor logarithmic in the size of the cache.

Publications

Home page.