Cover Image

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Buchem, Moritz, Deuker, Paul, Wiese, Andreas
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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)

Scheduling on a Stochastic Number of Machines
by: Buchem, Moritz, et al.
Published: (2024)

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

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

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

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)

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

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

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

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

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

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
by: Henzinger, Monika, et al.
Published: (2025)

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

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

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

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

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
by: Driemel, Anne, et al.
Published: (2026)

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

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
by: Harada, Kaito, et al.
Published: (2024)

A simpler QPTAS for scheduling jobs with precedence constraints
by: Das, Syamantak, et al.
Published: (2025)

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

Time Fairness in Online Knapsack Problems
by: Lechowicz, Adam, et al.
Published: (2023)

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

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Multipass Linear Sketches for Geometric LP-Type Problems
by: Çekirge, N. Efe, et al.
Published: (2025)

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

Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities
by: Bai, Miao, et al.
Published: (2023)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
by: Agarwal, Arpit, et al.
Published: (2024)

On the Approximability of Unsplittable Flow on a Path with Time Windows
by: Armbruster, Alexander, et al.
Published: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Improved Tree Sparsifiers in Near-Linear Time
by: Agassy, Daniel, et al.
Published: (2025)

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

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

Approximating Directed Connectivity in Almost-Linear Time
by: Quanrud, Kent
Published: (2025)

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

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)