On the PTAS Complexity of Multidimensional Knapsack
Skip to main content
Explore our many areas of focus
Explore all research areas
Applied AI & sciences
Earth AI
Health AI
Science AI
Sustainability & crisis resilience
Foundational ML & algorithms
Algorithms & theory
Information retrieval
Machine intelligence
Machine perception
Natural language processing
People, systems & quantum AI
Human-computer interaction and visualization
Networking
Quantum AI
Responsible AI
Anti abuse
Software engineering
Software systems
Learn More
Publications
Projects
Building a collaborative ecosystem
Datasets
Access high-quality datasets to accelerate your research.
Tools & services
Explore our latest AI models and products.
Open source
Discover open-source code and collaborate with the community.
Shaping the future together
See all programs
Faculty programs
Participating in the academic research community through meaningful engagement with university faculty.
Student programs
Supporting the next generation of researchers through a wide range of programming.
Locations
Find your place in our global offices and research labs.
Translating discovery into real-world impact
People
Our researchers drive advancements in computer science through both fundamental and applied research.
Teams
Collaborative groups tackling the world's most challenging AI problems.
Research
Explore our many areas of focus
Explore all research areas
Applied AI & sciences
Earth AI
Health AI
Science AI
Sustainability & crisis resilience
Foundational ML & algorithms
Algorithms & theory
Information retrieval
Machine intelligence
Machine perception
Natural language processing
People, systems & quantum AI
Human-computer interaction and visualization
Networking
Quantum AI
Responsible AI
Anti abuse
Software engineering
Software systems
Learn More
Publications
Projects
Resources
Building a collaborative ecosystem
Datasets
Access high-quality datasets to accelerate your research.
Tools & services
Explore our latest AI models and products.
Open source
Discover open-source code and collaborate with the community.
Conferences & events
Careers
Shaping the future together
See all programs
Faculty programs
Participating in the academic research community through meaningful engagement with university faculty.
Student programs
Supporting the next generation of researchers through a wide range of programming.
Locations
Find your place in our global offices and research labs.
Blog
About
Translating discovery into real-world impact
People
Our researchers drive advancements in computer science through both fundamental and applied research.
Teams
Collaborative groups tackling the world's most challenging AI problems.
Google
Research
Google AI
Learn about all our AI
Google DeepMind
Explore the frontier of AI
Google Labs
Try our AI experiments
Research
Resources
Conferences & events
Careers
Blog
About
Search
Home
Publications
On the PTAS Complexity of Multidimensional Knapsack
Ilan Doron-Arad
Ariel Kulik
Pasin Manurangsi
ITCS (2026)
Download
Google Scholar
Copy Bibtex
Abstract
We study the d-dimensional knapsack problem. We are given a set of items, each with a d-dimensional cost vector and a profit, along with a d-dimensional budget vector. The goal is to select a set of items that do not exceed the budget in all dimensions and maximize the total profit. A polynomial-time approximation scheme (PTAS) with running time n^{Θ(d/{ε})} has long been known for this problem, where {ε} is the error parameter and n is the encoding size. Despite decades of active research, the best running time of a PTAS has remained O(n^{⌈ d/{ε} ⌉ - d}). Unfortunately, existing lower bounds only cover the special case with two dimensions d = 2, and do not answer whether there is a n^{o(d/({ε)})}-time PTAS for larger values of d.
In this work, we show that the running times of the best-known PTAS cannot be improved up to a polylogarithmic factor assuming the Exponential Time Hypothesis (ETH). Our techniques are based on a robust reduction from 2-CSP, which embeds 2-CSP constraints into a desired number of dimensions. Then, using a recent result of [Bafna Karthik and Minzer, STOC'25], we succeed in exhibiting tight trade-off between d and {ε} for all regimes of the parameters assuming d is sufficiently large. Informally, our result also shows that under ETH, for any function f there is no f(d/({ε)}) ⋅ n^{õ(d/({ε)})}-time (1-{ε})-approximation for d-dimensional knapsack, where n is the number of items and õ hides polylogarithmic factors in d/({ε)}.
Meet the teams driving innovation
Our teams advance the state of the art through research, systems engineering, and collaboration across Google.
See our teams
Follow us
Explore our other initiatives
Google AI
Discover how Google AI is committed to enriching knowledge and solving complex challenges
Products
Build
Research
Responsibility
Societal Impact
About
Google Cloud
High-performance infrastructure for cloud computing, data analytics & machine learning
Overview
Solutions
Products
Pricing
Resources
Google DeepMind
Our mission is to build AI responsibly to benefit humanity
Models
Research
Science
About
Google Labs
Explore the future of AI responsibly with Google Labs
About
Experiments
Stay connected
About Google
Google Products
Privacy
Terms
Cookies management controls
×