Copertina

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Yang, Yang
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
di: Yang, Yang
Pubblicazione: (2025)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
di: Singer, Noah G.
Pubblicazione: (2025)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
di: Kluk, Kacper, et al.
Pubblicazione: (2025)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
di: Bhattacharjee, Somnath, et al.
Pubblicazione: (2025)

On the complexity of global Roman domination problem in graphs
di: Reddy, Sangam Balchandar, et al.
Pubblicazione: (2026)

Clifford testing: algorithms and lower bounds
di: Hinsche, Marcel, et al.
Pubblicazione: (2025)

Simple approximation algorithms for Polyamorous Scheduling
di: Biktairov, Yuriy, et al.
Pubblicazione: (2024)

A tight quasi-polynomial bound for Global Label Min-Cut
di: Jaffke, Lars, et al.
Pubblicazione: (2022)

The communication complexity of distributed estimation
di: Gopalan, Parikshit, et al.
Pubblicazione: (2025)

Parameterized complexity of reconfiguration of atoms
di: Cooper, Alexandre, et al.
Pubblicazione: (2021)

An alignment problem
di: McDaniel, Emma L., et al.
Pubblicazione: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
di: S., Karthik C., et al.
Pubblicazione: (2023)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
di: Björklund, Andreas, et al.
Pubblicazione: (2025)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
di: Li, Tiange, et al.
Pubblicazione: (2026)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
di: Chakraborty, Dibyayan, et al.
Pubblicazione: (2024)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
di: Dell, Holger, et al.
Pubblicazione: (2022)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
di: Prunet, Thibault, et al.
Pubblicazione: (2023)

On the complexity and approximability of Bounded access Lempel Ziv coding
di: Cicalese, Ferdinando, et al.
Pubblicazione: (2024)

On girth and the parameterized complexity of token sliding and token jumping
di: Bartier, Valentin, et al.
Pubblicazione: (2020)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
di: Ducoffe, Guillaume
Pubblicazione: (2026)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
di: Enright, Jessica, et al.
Pubblicazione: (2020)

The complexity of testing all properties of planar graphs, and the role of isomorphism
di: Basu, Sabyasachi, et al.
Pubblicazione: (2021)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
di: Michel, Lukas, et al.
Pubblicazione: (2023)

A lossless a priori splitting rule for split-delivery routing problems
di: Jones, Bo, et al.
Pubblicazione: (2025)

Constructing self-referential instances for the clique problem
di: Li, Jiaqi, et al.
Pubblicazione: (2026)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
di: Austrin, Per, et al.
Pubblicazione: (2024)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
di: Dumas, Maël, et al.
Pubblicazione: (2022)

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
di: Bendotti, Pascale, et al.
Pubblicazione: (2024)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
di: Scheder, Dominik, et al.
Pubblicazione: (2025)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
di: Liu, Wei, et al.
Pubblicazione: (2024)

Time complexity of the Analyst's Traveling Salesman algorithm
di: Ramirez, Anthony, et al.
Pubblicazione: (2022)

Streaming Complexity Separations for Dense and Sparse Graphs
di: Liu, Yang P., et al.
Pubblicazione: (2026)

Fast decision tree learning solves hard coding-theoretic problems
di: Koch, Caleb, et al.
Pubblicazione: (2024)

Sublinear-query relative-error testing of halfspaces
di: Chen, Xi, et al.
Pubblicazione: (2026)

Halfspaces are hard to test with relative error
di: Chen, Xi, et al.
Pubblicazione: (2025)

Fast and simple multiplication of bounded twin-width matrices
di: Kozma, László, et al.
Pubblicazione: (2026)

Fast quantum algorithm for differential equations
di: Bagherimehrab, Mohsen, et al.
Pubblicazione: (2023)

A note on approximating the average degree of bounded arboricity graphs
di: Eden, Talya, et al.
Pubblicazione: (2026)