Buchumschlag

An O(nlogn) approximate knapsack algorithm

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Dawes, Nick
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms F.2.1
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Selective algorithm processing of subset sum distributions
von: Dawes, Nick
Veröffentlicht: (2024)

Engineering Compressed Matrix Multiplication with the Fast Walsh-Hadamard Transform
von: Andersson, Joel, et al.
Veröffentlicht: (2026)

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

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

Classic Round-Up Variant of Fast Unsigned Division by Constants: Algorithm and Full Proof
von: Li, Yifei
Veröffentlicht: (2024)

Splittable Spanning Trees and Balanced Forests in Dense Random Graphs
von: Gillman, David, et al.
Veröffentlicht: (2025)

The Constrained Layer Tree Problem and Applications to Solar Farm Cabling
von: Bläsius, Thomas, et al.
Veröffentlicht: (2024)

Type-II/III DCT/DST algorithms with reduced number of arithmetic operations
von: Shao, Xuancheng, et al.
Veröffentlicht: (2007)

Min-CSPs on Complete Instances
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

DynamicLogLog: Faster, Smaller, and More Accurate Cardinality Estimation
von: Bushnell, Brian
Veröffentlicht: (2026)

A Heuristic for Direct Product Graph Decomposition
von: Calderoni, Luca, et al.
Veröffentlicht: (2021)

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$
von: Spielman, Daniel A., et al.
Veröffentlicht: (2003)

Stable Iterative Solvers for Ill-conditioned Linear Systems
von: Kalantzis, Vasileios, et al.
Veröffentlicht: (2025)

Deterministic complexity analysis of Hermitian eigenproblems
von: Sobczyk, Aleksandros
Veröffentlicht: (2024)

Invariant subspaces and PCA in nearly matrix multiplication time
von: Sobczyk, Aleksandros, et al.
Veröffentlicht: (2023)

When Votes Change and Committees Should (Not)
von: Bredereck, Robert, et al.
Veröffentlicht: (2020)

Unsplittable Multicommodity Flows in Outerplanar Graphs
von: Alemán-Espinosa, David, et al.
Veröffentlicht: (2025)

The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication
von: Murthy, Sandeep
Veröffentlicht: (2007)

Smoothed Analysis of Interior-Point Algorithms: Condition Number
von: Dunagan, John, et al.
Veröffentlicht: (2003)

Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
von: Spielman, Daniel A., et al.
Veröffentlicht: (2006)

Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic
von: Paszyński, Maciej
Veröffentlicht: (2024)

Does block size matter in randomized block Krylov low-rank approximation?
von: Chen, Tyler, et al.
Veröffentlicht: (2025)

Generating Signed Permutations by Twisting Two-Sided Ribbons
von: Yuan, et al.
Veröffentlicht: (2023)

Efficient Uniform Sampling of Surjections via their Profiles
von: Carayol, Arnaud, et al.
Veröffentlicht: (2026)

A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm
von: Li, Shisheng
Veröffentlicht: (2026)

Reserve Matching with Thresholds
von: Evren, Suat
Veröffentlicht: (2023)

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
von: Farfan, Angelo, et al.
Veröffentlicht: (2025)

Eliminating Illusion in Directed Networks
von: Jana, Sougata, et al.
Veröffentlicht: (2026)

Restless reachability problems in temporal graphs
von: Thejaswi, Suhas, et al.
Veröffentlicht: (2020)

Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"
von: Krawczyk, Tomasz
Veröffentlicht: (2024)

An 8- and 12-bit block AES cipher
von: Breuer, Peter T.
Veröffentlicht: (2025)

Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm
von: Hochbaum, Dorit S.
Veröffentlicht: (2016)

A simple $(2+ε)$-approximation for knapsack interdiction
von: Weninger, Noah
Veröffentlicht: (2026)

Approximation algorithms for scheduling with rejection in green manufacturing
von: Gong, Mingyang, et al.
Veröffentlicht: (2025)

Approximation algorithms for Job Scheduling with reconfigurable resources
von: Bergé, Pierre, et al.
Veröffentlicht: (2023)

An $n^{O(\log\log n)}$ time approximation scheme for capacitated VRP in the Euclidean plane
von: Sitters, René
Veröffentlicht: (2025)

The cost of cyclic permutations and remainder sums in the Euclidean algorithm
von: Blomer, Valentin, et al.
Veröffentlicht: (2026)

A faster algorithm for the construction of optimal factoring automata
von: Erlebach, Thomas, et al.
Veröffentlicht: (2024)

An improved local search based algorithm for $k^-$-star partition
von: Gong, Mingyang, et al.
Veröffentlicht: (2025)

Tensor Decomposition for Non-Clifford Gate Minimization
von: Khoruzhii, Kirill, et al.
Veröffentlicht: (2026)