Optimization Online


Approximation Algorithms for the Incremental Knapsack Problem via Disjunctive Programming

Daniel Bienstock(dano***at***columbia.edu)
Jay Sethuraman(js1353***at***columbia.edu)
Chun Ye(cy2214***at***columbia.edu)

Abstract: In the \emph{incremental knapsack problem} ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items to be placed in the knapsack. Item $i$ has a value of $v_i$ and a weight of $w_i$ that is independent of the time period. At any time period $t$, the sum of the weights of the items in the knapsack cannot exceed the knapsack capacity $B_t$. Moreover, once an item is placed in the knapsack, it cannot be removed from the knapsack at a later time period. We seek to maximize the sum of (discounted) knapsack values over time subject to the capacity constraints. We first give a constant factor approximation algorithm for $\IK$, under mild restrictions on the growth rate of $B_t$ (the constant factor depends on the growth rate). We then give a PTAS for $\IIK$, the special case of $\IK$ with no discounting, when $T = O(\sqrt{\log N})$.

Keywords: Approximation Algorithms, Integer Programming, Disjunctive Programming

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Integer Programming (0-1 Programming )

Citation: Columbia University, Nov 2013.

Download: [PDF]

Entry Submitted: 11/18/2013
Entry Accepted: 11/18/2013
Entry Last Modified: 11/18/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society