Buchumschlag

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Yang, Yang
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity 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

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
von: Yang, Yang
Veröffentlicht: (2024)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Precoloring extension with demands on paths
von: Das, Arun Kumar, et al.
Veröffentlicht: (2025)

Simple approximation algorithms for Polyamorous Scheduling
von: Biktairov, Yuriy, et al.
Veröffentlicht: (2024)

An alignment problem
von: McDaniel, Emma L., et al.
Veröffentlicht: (2024)

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

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
von: Dell, Holger, et al.
Veröffentlicht: (2022)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2024)

Constructing self-referential instances for the clique problem
von: Li, Jiaqi, et al.
Veröffentlicht: (2026)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
von: Austrin, Per, et al.
Veröffentlicht: (2024)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
von: Ducoffe, Guillaume
Veröffentlicht: (2026)

A lossless a priori splitting rule for split-delivery routing problems
von: Jones, Bo, et al.
Veröffentlicht: (2025)

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

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

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

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

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
von: Liu, Wei, et al.
Veröffentlicht: (2024)

Streaming Complexity Separations for Dense and Sparse Graphs
von: Liu, Yang P., et al.
Veröffentlicht: (2026)

Fast decision tree learning solves hard coding-theoretic problems
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Halfspaces are hard to test with relative error
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Sublinear-query relative-error testing of halfspaces
von: Chen, Xi, et al.
Veröffentlicht: (2026)

On the complexity of global Roman domination problem in graphs
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2026)

On the uniqueness and computation of commuting extensions
von: Koiran, Pascal
Veröffentlicht: (2024)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2026)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
von: Heeger, Klaus, et al.
Veröffentlicht: (2024)

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

Clifford testing: algorithms and lower bounds
von: Hinsche, Marcel, et al.
Veröffentlicht: (2025)

Fast quantum algorithm for differential equations
von: Bagherimehrab, Mohsen, et al.
Veröffentlicht: (2023)

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

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
von: Abbas, Amira, et al.
Veröffentlicht: (2025)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
von: Apers, Simon, et al.
Veröffentlicht: (2021)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

The Trichotomy of Regular Property Testing
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Downward self-reducibility in the total function polynomial hierarchy
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
von: Fujie, Yuto, et al.
Veröffentlicht: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
von: Moroie, Gregory
Veröffentlicht: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
von: Gholizadeh, Hossein, et al.
Veröffentlicht: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
von: Herrmann, Anton, et al.
Veröffentlicht: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)