Cover Image

Beating Bellman's Algorithm for Subset Sum

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bringmann, Karl, Fischer, Nick, Nakos, Vasileios
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

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
by: Fischer, Nick, et al.
Published: (2025)

Sumsets, 3SUM, Subset Sum: Now for Real!
by: Fischer, Nick
Published: (2024)

Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
by: Bringmann, Karl, et al.
Published: (2026)

Derandomizing Pseudopolynomial Algorithms for Subset Sum
by: Chan, Timothy M.
Published: (2026)

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

An Improved Pseudopolynomial Time Algorithm for Subset Sum
by: Chen, Lin, et al.
Published: (2024)

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

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
by: Aggarwal, Divesh, et al.
Published: (2024)

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

Approximate Min-Sum Subset Convolution
by: Stoian, Mihail
Published: (2024)

Inverse Quadratic Decay in Random Subset Sum
by: Chen, Edwin, et al.
Published: (2026)

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
by: Bringmann, Karl, et al.
Published: (2024)

Listing Even Cycles Faster than the Submodular-Width Barrier
by: Nakos, Vasileios, et al.
Published: (2026)

Subset Balancing and Generalized Subset Sum via Lattices
by: Gao, Yiming, et al.
Published: (2026)

Targeted Least Cardinality Candidate Key for Relational Databases
by: Nakos, Vasileios, et al.
Published: (2024)

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
by: Bringmann, Karl, et al.
Published: (2022)

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

Improved Space Bounds for Subset Sum
by: Belova, Tatiana, et al.
Published: (2024)

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

Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach
by: Joux, Antoine, et al.
Published: (2024)

A Simple Algorithm for Trimmed Multipoint Evaluation
by: Fischer, Nick, et al.
Published: (2025)

Does Subset Sum Admit Short Proofs?
by: Włodarczyk, Michał
Published: (2024)

Dynamic and Streaming Algorithms for Union Volume Estimation
by: Bhore, Sujoy, et al.
Published: (2026)

Lawler-Moore Speedups via Additive Combinatorics
by: Bringmann, Karl, et al.
Published: (2026)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
by: Fischer, Nick
Published: (2026)

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

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Polyline Simplification has Cubic Complexity
by: Bringmann, Karl, et al.
Published: (2018)

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
by: Abboud, Amir, et al.
Published: (2023)

Parameterized Algorithms for Minimum Sum Vertex Cover
by: Aute, Shubhada, et al.
Published: (2024)

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

Breaking the Bellman-Ford Shortest-Path Bound
by: Elmasry, Amr
Published: (2024)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
by: Funke, Daniel, et al.
Published: (2024)

Beating Meet-in-the-Middle for Subset Balancing Problems
by: Randolph, Tim, et al.
Published: (2025)

Bellman-Ford in Almost-Linear Time for Dense Graphs
by: Li, George Z., et al.
Published: (2026)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
by: Abboud, Amir, et al.
Published: (2025)

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
by: Friggstad, Zachary, et al.
Published: (2024)