Imagen de Portada

Simple and Faster Algorithms for Knapsack

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	He, Qizheng, Xu, Zhean
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

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

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

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

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
por: Chen, Lin, 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)

Quantum Data Structure for Range Minimum Query
por: Wang, Qisheng, et al.
Publicado: (2026)

Faster Algorithms for Text-to-Pattern Hamming Distances
por: Chan, Timothy M., et al.
Publicado: (2023)

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

Faster Algorithms for Graph Monopolarity
por: Philip, Geevarghese, et al.
Publicado: (2024)

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

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)

Faster Combinatorial k-Clique Algorithms
por: Abboud, Amir, et al.
Publicado: (2024)

Faster Algorithms for Longest Common Substring
por: Charalampopoulos, Panagiotis, et al.
Publicado: (2021)

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

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

Faster Algorithms for Dual-Failure Replacement Paths
por: Chechik, Shiri, et al.
Publicado: (2024)

Faster Algorithms for Shortest Unique or Absent Substrings
por: Charalampopoulos, Panagiotis, et al.
Publicado: (2026)

A Faster Algorithm for Constrained Correlation Clustering
por: Fischer, Nick, et al.
Publicado: (2025)

Faster Algorithm for Structured John Ellipsoid Computation
por: Cao, Yang, et al.
Publicado: (2022)

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

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

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

0-1 Knapsack in Nearly Quadratic Time
por: Jin, Ce
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)

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

Faster Vizing and Near-Vizing Edge Coloring Algorithms
por: Assadi, Sepehr
Publicado: (2024)

Faster Algorithms for Schatten-p Low Rank Approximation
por: Kacham, Praneeth, et al.
Publicado: (2024)

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

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

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

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
por: Kadria, Avi, et al.
Publicado: (2025)

Faster Approximation Algorithms for k-Center via Data Reduction
por: Filtser, Arnold, et al.
Publicado: (2025)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
por: Łącki, Jakub, et al.
Publicado: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
por: Ashvinkumar, Vikrant, et al.
Publicado: (2024)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
por: Chuzhoy, Julia, et al.
Publicado: (2026)

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