Imagen de Portada

Convolution and Knapsack in Higher Dimensions

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Grage, Kilian, Jansen, Klaus, Schumacher, Björn
Formato:	Preprint
Publicado:	2024
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

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

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

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

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

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

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

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)

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)

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)

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

$(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)

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

A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling
por: Jansen, Klaus, et al.
Publicado: (2026)

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

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

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

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)

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

Hardness and Tight Approximations of Demand Strip Packing
por: Jansen, Klaus, et al.
Publicado: (2024)

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
por: Brinkop, Hauke, et al.
Publicado: (2025)

Structural Results for High-Multiplicity Scheduling on Uniform Machines
por: Brinkop, Hauke, et al.
Publicado: (2022)

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)

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times
por: Deppert, Max A., et al.
Publicado: (2025)

Knapsack: Connectedness, Path, and Shortest-Path
por: Dey, Palash, et al.
Publicado: (2023)

Knapsack on Graphs with Relaxed Neighborhood Constraints
por: Dey, Palash, et al.
Publicado: (2025)

An Exact Solver for Submodular Knapsack Problems
por: Münch, Sabine, et al.
Publicado: (2025)

High-dimensional Linear Bandits with Knapsacks
por: Ma, Wanteng, et al.
Publicado: (2023)

New Algorithm for Combinatorial $n$-folds and Applications
por: Jansen, Klaus, et al.
Publicado: (2024)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
por: Jansen, Klaus, et al.
Publicado: (2024)

The Support of Bin Packing is Exponential
por: Jansen, Klaus, et al.
Publicado: (2025)