Cover Image

A Nearly Quadratic-Time FPTAS for Knapsack

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Lin, Lian, Jiayi, Mao, Yuchen, Zhang, Guochuan
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Note on Deterministic FPTAS for Partition
by: Chen, Lin, et al.
Published: (2025)

Weakly Approximating Knapsack in Subquadratic Time
by: Chen, Lin, et al.
Published: (2025)

Approximating Partition in Near-Linear Time
by: Chen, Lin, et al.
Published: (2024)

An Improved Pseudopolynomial Time Algorithm for Subset Sum
by: Chen, Lin, et al.
Published: (2024)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
by: Mao, Xiao
Published: (2023)

0-1 Knapsack in Nearly Quadratic Time
by: Jin, Ce
Published: (2023)

Knapsack with Small Items in Near-Quadratic Time
by: Bringmann, Karl
Published: (2023)

Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses
by: Chen, Lin, et al.
Published: (2025)

FPTAS for Holant Problems with Log-Concave Signatures
by: He, Kun, et al.
Published: (2024)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
by: Buchem, Moritz, et al.
Published: (2024)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
by: Dughmi, Shaddin, et al.
Published: (2025)

Performance of the Extended Ising Machine for the Quadratic Knapsack Problem
by: Akishima, Haruka, et al.
Published: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)

Online Unbounded Knapsack
by: Böckenhauer, Hans-Joachim, et al.
Published: (2024)

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

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Online Knapsack Problems with Estimates
by: Balabán, Jakub, et al.
Published: (2025)

Average sensitivity of the Knapsack Problem
by: Kumabe, Soh, et al.
Published: (2024)

Convolution and Knapsack in Higher Dimensions
by: Grage, Kilian, et al.
Published: (2024)

Fair Submodular Maximization over a Knapsack Constraint
by: Li, Lijun, et al.
Published: (2025)

Online General Knapsack with Reservation Costs
by: Burjons, Elisabet, et al.
Published: (2025)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)

Fine Grained Lower Bounds for Multidimensional Knapsack
by: Doron-Arad, Ilan, et al.
Published: (2024)

An FPTAS for 7/9-Approximation to Maximin Share Allocations
by: Huang, Xin, et al.
Published: (2025)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
by: Hao, Yimin, et al.
Published: (2025)

On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms
by: Schlöter, Jens
Published: (2025)

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
by: Barak, Zohar, et al.
Published: (2026)

Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal
by: Gehnen, Matthias, et al.
Published: (2025)

A Smoothed FPTAS for Equilibria in Congestion Games
by: Giannakopoulos, Yiannis
Published: (2023)

Zero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region
by: Shao, Shuai, et al.
Published: (2025)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
by: Doron-Arad, Ilan, et al.
Published: (2023)

Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
by: Bienkowski, Marcin, et al.
Published: (2026)

Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them
by: Canonne, Clément L., et al.
Published: (2025)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
by: Ma, Will, et al.
Published: (2019)

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
by: Amanatidis, Georgios, et al.
Published: (2021)

On Sketching Quadratic Forms
by: Andoni, Alexandr, et al.
Published: (2015)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
by: Bringmann, Karl, et al.
Published: (2024)

Approximate Counting for Spin Systems in Sub-Quadratic Time
by: Anand, Konrad, et al.
Published: (2023)