Michele Monaci

Exact Solution of the Robust Knapsack Problem

  • Michele Monaci
  • Ulrich Pferschy
  • Paolo Serafini
    • Categories Combinatorial Optimization, Dynamic Programming, Robust Optimization Tags , ,

    We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight di ffers from the expected one. For this problem, we provide a dynamic programming algorithm … Read more

    On the Robust Knapsack Problem

  • Michele Monaci
  • Ulrich Pferschy
    • Categories 0-1 Programming, Approximation Algorithms, Robust Optimization Tags , ,

    We consider an uncertain variant of the knapsack problem that arises when the exact weight of each item is not exactly known in advance but belongs to a given interval, and the number of items whose weight differs from the nominal value is bounded by a constant. We analyze the worsening of the optimal solution … Read more