Editing Knapsack problem (section)

===Multi-dimensional weight===
Here, the weight of knapsack item <math>i</math> is given by a D-dimensional vector <math>\overline{w_i}=(w_{i1},\ldots,w_{iD})</math> and the knapsack has a D-dimensional capacity vector <math>(W_1,\ldots,W_D)</math>. The target is to maximize the sum of the values of the items in the knapsack so that the sum of weights in each dimension <math>d</math> does not exceed <math>W_d</math>.

Multi-dimensional knapsack is computationally harder than knapsack; even for <math>D=2</math>, the problem does not have [[EPTAS]] unless P<math>=</math>NP.<ref>{{cite journal | last1 = Kulik | first1 = A. | last2 = Shachnai | first2 = H. | author2-link = Hadas Shachnai | year = 2010 | title = There is no EPTAS for two dimensional knapsack | url = https://www.cs.technion.ac.il/~hadas/PUB/multi_knap.pdf| journal = Inf. Process. Lett. | volume = 110 | issue = 16| pages = 707–712 | doi=10.1016/j.ipl.2010.05.031| citeseerx = 10.1.1.161.5838 }}</ref> However, the algorithm in<ref name=CohenGrebla>Cohen, R. and Grebla, G. 2014. [http://wimnet.ee.columbia.edu/wp-content/uploads/2013/03/paper_short.pdf "Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes"]. in ''Proc. IEEE INFOCOM'14'', 2427–2435.</ref> is shown to solve sparse instances efficiently. An instance of multi-dimensional knapsack is sparse if there is a set <math>J=\{1,2,\ldots,m\}</math> for <math>m<D</math> such that for every knapsack item <math>i</math>, <math> \exists z>m</math> such that <math>\forall j\in J\cup \{z\},\ w_{ij}\geq 0</math> and <math>\forall y\notin J\cup\{z\}, w_{iy}=0</math>. Such instances occur, for example, when scheduling packets in a wireless network with relay nodes.<ref name=CohenGrebla/> The algorithm from<ref name=CohenGrebla/> also solves sparse instances of the multiple choice variant, multiple-choice multi-dimensional knapsack.

The IHS (Increasing Height Shelf) algorithm is optimal for 2D knapsack (packing squares into a two-dimensional unit size square): when there are at most five squares in an optimal packing.<ref>Yan Lan, György Dósa, Xin Han, Chenyang Zhou, Attila Benkő [https://scholar.google.com/citations?user=txyI5aAAAAAJ]: ''2D knapsack: Packing squares'', Theoretical Computer Science Vol. 508, pp. 35–40.</ref>