A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

By Chandra Chekuri, Sanjeev Khanna. SIAM journal on computing (Print), 2005

348 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

MCDNN: An Approximation-Based Execution Framework for Deep Stream Processing Under Resource Constraints (2016, background): “Third, it must consider processing a request either on-device, on-cloud or split across the two, introducing a multiple-knapsack element [9].”
Online Submodular Maximization with Preemption (2015, background): “Submodular maximization captures well known combinatorial optimization problems such as: MaxCut [32, 36, 39, 40, 53], Max-DiCut [20, 32, 34], Generalized Assignment [11, 12, 24, 29], and Max-FacilityLocation [2, 14, 15].”
Online Matching and Ad Allocation (2013, methodology): “For GAP, a (1)2 approximation follows from Shmoys and Tardos [88] (see [27]).”
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (2011, methodology): “[19] gave a (1− 1/e)-approximation for this problem, improving upon a previous 1/2-approximation [6].”
Submodular Maximization with Cardinality Constraints (2014, background): “Submodular maximization problems capture well known combinatorial optimization problems such as: Max- Cut [26] [29] [31] [33] [50], Max-DiCut [16] [26] [27], Generalized Assignment [10, 11, 19, 23], and Max-Facility-Location [1, 12, 13].”