Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints

Title: Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints 

Abstract: The joint replenishment problem (JRP) is a classical inventory management problem. We consider a natural generalization with outliers, where we are allowed to reject (that is, not service) a subset of demand points. In this talk, we are motivated by issues of fairness - if we do not serve all of the demands, we wish to “spread out the pain” in a balanced way among customers, communities, or any specified market segmentation. One approach is to constrain the rejections allowed, and to have separate bounds for each given customer. In our most general setting, we consider a set of C features, where each demand point has an associated rejection cost for each feature, and we have a given bound on the allowed rejection cost incurred in total for each feature. 
We give the first constant approximation algorithms for the fairness-constrained JRP with a constant number of features; specifically, we give a 2.86-approximation algorithm in this case. Even for the special case in which we bound the total (weighted) number of outliers, this performance guarantee improves upon bounds previously known for this case. 

Bio: Varun is a final-year PhD student in Operations Research advised by David Shmoys. Most of Varuns' research has focussed on optimization problems from the perspective of emerging considerations like fairness, recourse and predictions.