Cover Image

Improved Approximation Algorithms for Three-Dimensional Knapsack

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jansen, Klaus, Kar, Debajyoti, Khan, Arindam, Sreenivas, K. V. N., Tutas, Malte
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Improved Approximation Algorithms for Three-Dimensional Bin Packing
by: Kar, Debajyoti, et al.
Published: (2025)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
by: Kar, Debajyoti, et al.
Published: (2026)

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

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

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

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

Near-optimal Algorithms for Stochastic Online Bin Packing
by: Ayyadevara, Nikhil, et al.
Published: (2022)

Bin Packing under Random-Order: Breaking the Barrier of 3/2
by: Hebbar, Anish, et al.
Published: (2024)

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

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

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

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

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

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

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

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

Random-Order Online Independent Set of Intervals and Hyperrectangles
by: Garg, Mohit, et al.
Published: (2024)

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

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

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

Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
by: Pham, Canh V.
Published: (2024)

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

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

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

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

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

Improved Approximation Algorithm for Maximum Balanced Biclique
by: Manurangsi, Pasin
Published: (2026)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

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)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
by: Armbruster, Alexander, et al.
Published: (2026)

Why is My Route Different Today? An Algorithm for Explaining Route Selection
by: Schild, Aaron, et al.
Published: (2025)

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

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
by: Fan, Chenglin, et al.
Published: (2025)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
by: Zhao, Jingyang, et al.
Published: (2022)

Improved Approximation Algorithms for Relational Clustering
by: Esmailpour, Aryan, et al.
Published: (2024)

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

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