Buchumschlag

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bringmann, Karl, Dürr, Anita, Polak, Adam
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
von: Dürr, Anita
Veröffentlicht: (2022)

Deterministic Monotone Min-Plus Product and Convolution
von: Jin, Ce, et al.
Veröffentlicht: (2026)

Knapsack with Small Items in Near-Quadratic Time
von: Bringmann, Karl
Veröffentlicht: (2023)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
von: Bringmann, Karl, et al.
Veröffentlicht: (2026)

Faster algorithms for k-Orthogonal Vectors in low dimension
von: Dürr, Anita, et al.
Veröffentlicht: (2025)

Simple and Faster Algorithms for Knapsack
von: He, Qizheng, et al.
Veröffentlicht: (2023)

3SUM in Preprocessed Universes: Faster and Simpler
von: Kasliwal, Shashwat, et al.
Veröffentlicht: (2024)

Convolution and Knapsack in Higher Dimensions
von: Grage, Kilian, et al.
Veröffentlicht: (2024)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
von: Nogler, Jakob, et al.
Veröffentlicht: (2024)

Approximate Min-Sum Subset Convolution
von: Stoian, Mihail
Veröffentlicht: (2024)

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
von: de Vos, Tijn, et al.
Veröffentlicht: (2024)

Better Indexing for Rectangular Pattern Matching
von: Gawrychowski, Paweł, et al.
Veröffentlicht: (2025)

Even Faster Algorithm for the Chamfer Distance
von: Feng, Ying, et al.
Veröffentlicht: (2025)

Lawler-Moore Speedups via Additive Combinatorics
von: Bringmann, Karl, et al.
Veröffentlicht: (2026)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
von: Dong, Sally, et al.
Veröffentlicht: (2023)

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
von: Bringmann, Karl, et al.
Veröffentlicht: (2022)

Listing Even Cycles Faster than the Submodular-Width Barrier
von: Nakos, Vasileios, et al.
Veröffentlicht: (2026)

Beating Bellman's Algorithm for Subset Sum
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Faster Algorithms for Fair Max-Min Diversification in $\mathbb{R}^d$
von: Kurkure, Yash, et al.
Veröffentlicht: (2024)

Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
von: Amanatidis, Georgios, et al.
Veröffentlicht: (2020)

Online Unbounded Knapsack
von: Böckenhauer, Hans-Joachim, et al.
Veröffentlicht: (2024)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Average sensitivity of the Knapsack Problem
von: Kumabe, Soh, et al.
Veröffentlicht: (2024)

Near-Optimal Directed Low-Diameter Decompositions
von: Bringmann, Karl, et al.
Veröffentlicht: (2025)

Online Knapsack Problems with Estimates
von: Balabán, Jakub, et al.
Veröffentlicht: (2025)

Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
von: Bringmann, Karl, et al.
Veröffentlicht: (2026)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2023)

Online General Knapsack with Reservation Costs
von: Burjons, Elisabet, et al.
Veröffentlicht: (2025)

Weakly Approximating Knapsack in Subquadratic Time
von: Chen, Lin, et al.
Veröffentlicht: (2025)

Polyline Simplification has Cubic Complexity
von: Bringmann, Karl, et al.
Veröffentlicht: (2018)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
von: Hu, Bingbing, et al.
Veröffentlicht: (2024)

Approximately Counting Knapsack Solutions in Subquadratic Time
von: Feng, Weiming, et al.
Veröffentlicht: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

Improved Approximation Algorithms for Three-Dimensional Knapsack
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

0-1 Knapsack in Nearly Quadratic Time
von: Jin, Ce
Veröffentlicht: (2023)

A Nearly Quadratic-Time FPTAS for Knapsack
von: Chen, Lin, et al.
Veröffentlicht: (2023)

Faster Convolutions: Yates and Strassen Revisited
von: Brand, Cornelius, et al.
Veröffentlicht: (2025)

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