Imagen de Portada

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

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Yang, Yang
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

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

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

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

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

Parameterized complexity of reconfiguration of atoms
por: Cooper, Alexandre, et al.
Publicado: (2021)

An alignment problem
por: McDaniel, Emma L., et al.
Publicado: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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