Imagen de Portada

0-1 Knapsack in Nearly Quadratic Time

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Jin, Ce
Formato:	Preprint
Publicado:	2023
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

A Nearly Quadratic-Time FPTAS for Knapsack
por: Chen, Lin, et al.
Publicado: (2023)

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

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

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

Near-Optimal Property Testers for Pattern Matching
por: Jin, Ce, et al.
Publicado: (2025)

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

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

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

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

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

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

Memory Reallocation with Polylogarithmic Overhead
por: Jin, Ce
Publicado: (2026)

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

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

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

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

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

A quantum algorithm for solving 0-1 Knapsack problems
por: Wilkening, Sören, et al.
Publicado: (2023)

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

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

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

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
por: Jin, Ce, et al.
Publicado: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
por: Jin, Ce, et al.
Publicado: (2024)

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

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

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

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

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

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

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

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

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

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

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
por: Fischer, Nick, et al.
Publicado: (2024)

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

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

Approximating Maximum Matching Requires Almost Quadratic Time
por: Behnezhad, Soheil, et al.
Publicado: (2024)

Removable Online Knapsack and Advice
por: Böckenhauer, Hans-Joachim, et al.
Publicado: (2020)

Sum-Of-Squares To Approximate Knapsack
por: Kothari, Pravesh K., et al.
Publicado: (2025)