Robust inventory problem with budgeted cumulative demand uncertainty

In this paper, a robust inventory problem with uncertain cumulative demands is considered. Interval-budgeted uncertainty sets are used to model possible cumulative demand scenarios. It is shown that under discrete budgeted uncertainty the robust min-max problem can be solved in polynomial time. On the other hand, for continuous budgeted uncertainty, the problem is weakly NP-hard. It can be solved in pseudopolynomial time and admits an FPTAS for nonoverlapping cumulative demand intervals.

Automated summary

This paper examines a robust inventory problem with uncertain cumulative demands, where interval-budgeted uncertainty sets are used to model possible demand scenarios. The study demonstrates that for discrete budgeted uncertainty, the robust min-max problem can be solved in polynomial time. Conversely, for continuous budgeted uncertainty, the problem is weakly NP-hard but can still be solved in pseudopolynomial time, particularly for nonoverlapping cumulative demand intervals, using an FPTAS.