A PTAS for the multiple knapsack problem

By Chandra Chekuri, Sanjeev Khanna. ACM-SIAM Symposium on Discrete Algorithms, 2000

303 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/018a3acede8f77daa40744e04298b6f2dcfef3ad

How researchers see this paper

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

1. Jan Vondr'ak
2. Gruia Calinescu
3. Chandra Chekuri
4. Martin Pál
5. Daniel Marx
6. Moran Feldman
7. Ashwinkumar Badanidiyuru
8. Aranyak Mehta

Citations in the corpus

• 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].”
• Parameterized Complexity and Approximation Algorithms (2008, background): “Euclidean TSP Arora [6] O(|x|15,000) Multiple Knapsack Chekuri and Khanna [26] O(|x|9,375,000) Maximum Subforest Shamir and Tsur [109] O(|x|958,267,391) Maximum Independent Set Erlebach et al.”