0-1 Knapsack in Nearly Quadratic Time

0-1 Knapsack in Nearly Quadratic Time

We study pseudo-polynomial time algorithms for the fundamental 0- 1 Knapsack problem. Recent research interest has focused on its finegrained complexity with respect to the number of items 𝑛 and the maximum item weight 𝑤max. Under (min, +)-convolution hypothesis, 0-1 Knapsack does not have𝑂( (𝑛+𝑤m...

Full description

Bibliographic Details
Main Author:	Jin, Ce
Other Authors:	Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format:	Article
Language:	English
Published:	Association for Computing Machinery STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing 2024
Online Access:	https://hdl.handle.net/1721.1/155707

Similar Items

A Nearly Quadratic Improvement for Memory Reallocation
by: Farach-Colton, Martin, et al.
Published: (2024)

Knapsack-based reverse influence maximization for target marketing in social networks
by: Talukder, Ashis, et al.
Published: (2019)

Time-inconsistent stochastic linear-quadratic control in continuous time
by: Song, Wan Jing
Published: (2021)

Gravitation and quadratic forms
by: Ananth, Sudarshan, et al.
Published: (2018)

Multirate Linear Quadratic Gaussian controllers for linear time-invariant systems
by: Chua, Say Yong.
Published: (2009)

Primes in quadratic progressions on average
by: Baier, Stephan, et al.
Published: (2009)

Quadratic to linear magnetoresistance tuning in TmB 4
by: Mitra, Sreemanta, et al.
Published: (2019)

Solvability Regions of Affinely Parameterized Quadratic Equations
by: Dvijotham, Krishnamurthy, et al.
Published: (2024)

Constraint exploration method for quadratic programming problem
by: Mohd, Ismail, et al.
Published: (2000)

Implementation and control of a quadratic boost converter
by: Lim, Yuan Jun
Published: (2021)

Tuning reduction conditions to understand and control Ni exsolution from Sr0.8La0.1Ca0.1Ti0.94Ni0.06O3−δ
by: O'Leary, Willis, et al.
Published: (2024)

Electrical properties of textured (KNa)0.44Li0.06Nb0.84Sb0.06Ta0.1O3 thick films
by: Fu, Fang, et al.
Published: (2013)

Diameter-free estimates for the quadratic Vinogradov mean value theorem
by: Mudgal, A
Published: (2022)

VERY LARGE-SCALE NEIGHBORHOOD SEARCH FOR THE QUADRATIC ASSIGNMENT PROBLEM
by: Ahuja, Ravindra, et al.
Published: (2003)

Growth and characterization of InSb on (1 0 0) Si for mid-infrared application
by: Jia, Bo Wen, et al.
Published: (2019)

Accelerated synthesis of Li(Ni0.8Co0.1Mn0.1)O2 cathode materials using flame-assisted spray pyrolysis and additives
by: Zhang, Jianan, et al.
Published: (2024)

Design and implementation of re-lift boost converter & quadratic boost converter
by: Tee, Wen Bin
Published: (2016)

Modified voltage-mode controller for the quadratic boost converter with improved output performance
by: Jiang, Wentao, et al.
Published: (2019)

A class of two-sex population quadratic stochastic operators: b-bistochastic-volterra
by: Embong, Ahmad Fadillah, et al.
Published: (2024)

NEWTS1.0: Numerical model of coastal Erosion by Waves and Transgressive Scarps
by: Palermo, Rose V, et al.
Published: (2024)

Development of perovskite-based light emitting diodes with improved stability 1.0
by: Sim, Zong Huan
Published: (2019)

Analysis of the revolving vane (RV-0) expander, part 1 : experimental investigations
by: Subiantoro, Alison, et al.
Published: (2013)

Spray coating of dense proton-conducting BaCe0.7Zr0.1Y0.2O3 electrolyte for low temperature solid oxide fuel cells
by: Fan, Liangdong, et al.
Published: (2017)

Pressure dependence of resistivity and magnetic properties in a Mn1.9Cr0.1Sb alloy
by: Sharma, Vinay, et al.
Published: (2018)

Terahertz conductivity of topological surface states in Bi1.5Sb0.5Te1.8Se1.2
by: Tang, Chi Sin, et al.
Published: (2014)

Effective control of polarity in Bi0.9La0.1FeO3 thin films by dopant-related internal bias
by: Wang, Yang, et al.
Published: (2012)

The downside deviation quadratic programming for stock portfolio optimisation: an empirical study of shariah and conventional indices in Indonesia
by: Muhammad Mussafi, Noor Saif, et al.
Published: (2024)

Design and implementation of a single-switch high gain quadratic boost converter based on voltage-lift-technique
by: Gwan, Wei Lin
Published: (2016)

Microlensing Near Macro-Caustics
by: Weisenbach, Luke, et al.
Published: (2024)

Temperature-dependent ultrafast carrier and phonon dynamics of topological insulator Bi1.5Sb0.5Te1.8Se1.2
by: Cheng, Liang, et al.
Published: (2014)

Preparation of 1T′-phase ReS2xSe2(1‑x) (x = 0−1) nanodots for highly efficient electrocatalytic hydrogen evolution reaction
by: Lai, Zhuangchai, et al.
Published: (2020)

A case study of two autopilot design methodologies : linear quadratic and H-infinity for a tail controlled missile
by: Edeburn, Mark Anthony.
Published: (2024)

Electrocatalytic activity of LiCo1-xFexO2 (0 ≤ x ≤ 1) for oxygen evolution reaction in alkaline medium
by: Tan, Cherynn Xue Ying
Published: (2016)

Measurement of the branching fraction of B0 → J/ψπ0 decays
by: Aaij, R., et al.
Published: (2024)

Gold-catalyzed cycloisomerization of 1,7-diyne benzoates to indeno[1,2-c]azepines and azabicyclo[4.2.0]octa-1(8),5-dines
by: Rao, Weidong, et al.
Published: (2013)

Structural Characterization of La0.6Sr0.4CoO3−δ Thin Films Grown on (100)-, (110)-, and (111)-Oriented La0.95Sr0.05Ga0.95Mg0.05O3−δ
by: Ražnjević, Sergej, et al.
Published: (2024)

Near field wireless power transfer
by: Er, Gavin Kian Ming
Published: (2020)

Canonical Diffeomorphisms of Manifolds Near Spheres
by: Wang, Bing, et al.
Published: (2023)

Near-zero environmental impact aircraft
by: Prashanth, Prakash, et al.
Published: (2024)

Search for CP violation in D0 → K0 SK0 S decays in proton–proton collisions at √s = 13 TeV
by: CMS Collaboration
Published: (2024)