Theory Seminar

Approximation algorithms for inventory problems with submodular or routing costs

Viswanath Nagarajan

University of Michigan
Friday, September 08, 2017
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

We consider inventory optimization problems over a horizon of T periods that involve two kinds of costs (1) an ordering cost to replenish items and (2) a holding cost to store items. When the ordering cost satisfies a certain natural property and the holding cost is a polynomial function, we obtain an O(log T / loglog T) approximation algorithm. This implies the first sub-logarithmic approximation ratio for the inventory-routing and submodular-joint-replenishment problems, under linear holding costs.

Additional Information

Contact: Grant Schoenebeck

Sponsor(s): CSE

Open to: Public