Buchumschlag

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Aggarwal, Divesh, Joux, Antoine, Santha, Miklos, Węgrzycki, Karol
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

Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach
von: Joux, Antoine, et al.
Veröffentlicht: (2024)

Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
von: Randolph, Tim, et al.
Veröffentlicht: (2024)

Space-Efficient Algorithm for Integer Programming with Few Constraints
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
von: Eisenbrand, Friedrich, et al.
Veröffentlicht: (2024)

Beating Meet-in-the-Middle for Subset Balancing Problems
von: Randolph, Tim, et al.
Veröffentlicht: (2025)

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

An Improved Pseudopolynomial Time Algorithm for Subset Sum
von: Chen, Lin, et al.
Veröffentlicht: (2024)

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

Derandomizing Pseudopolynomial Algorithms for Subset Sum
von: Chan, Timothy M.
Veröffentlicht: (2026)

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

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
von: Sajith, Thejas Radhika
Veröffentlicht: (2025)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
von: Jourdan, Ben, et al.
Veröffentlicht: (2024)

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

Inverse Quadratic Decay in Random Subset Sum
von: Chen, Edwin, et al.
Veröffentlicht: (2026)

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2020)

Sumsets, 3SUM, Subset Sum: Now for Real!
von: Fischer, Nick
Veröffentlicht: (2024)

Recursive lattice reduction -- A framework for finding short lattice vectors
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2023)

Subset Balancing and Generalized Subset Sum via Lattices
von: Gao, Yiming, et al.
Veröffentlicht: (2026)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
von: Nezhad, Sina Bagheri, et al.
Veröffentlicht: (2025)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2025)

On the quantum time complexity of divide and conquer
von: Allcock, Jonathan, et al.
Veröffentlicht: (2023)

Hitting Meets Packing: How Hard Can it Be?
von: Focke, Jacob, et al.
Veröffentlicht: (2024)

Improved Space Bounds for Subset Sum
von: Belova, Tatiana, et al.
Veröffentlicht: (2024)

Edge-Minimum Walk of Modular Length in Polynomial Time
von: Amarilli, Antoine, et al.
Veröffentlicht: (2024)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2020)

Dynamic data structures for twin-ordered matrices
von: Bosek, Bartłomiej, et al.
Veröffentlicht: (2026)

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
von: Caroppo, Susanna, et al.
Veröffentlicht: (2025)

Engineering an Efficient Approximate DNF-Counter
von: Soos, Mate, et al.
Veröffentlicht: (2024)

Does Subset Sum Admit Short Proofs?
von: Włodarczyk, Michał
Veröffentlicht: (2024)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
von: Allcock, Jonathan, et al.
Veröffentlicht: (2024)

On Integer Programs That Look Like Paths
von: Briański, Marcin, et al.
Veröffentlicht: (2025)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
von: Bampis, Evripidis, et al.
Veröffentlicht: (2025)

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
von: Hunkenschröder, Christoph, et al.
Veröffentlicht: (2025)

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

Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs
von: Im, Sungjin, et al.
Veröffentlicht: (2023)

Parameterized Algorithms for Minimum Sum Vertex Cover
von: Aute, Shubhada, et al.
Veröffentlicht: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Interactive Coding with Unbounded Noise
von: Fargion, Eden, et al.
Veröffentlicht: (2024)