More on change-making and related problems

DOI10.1016/j.jcss.2021.09.005zbMath1491.68126arXiv2110.02503OpenAlexW3207797135MaRDI QIDQ2051861

Qizheng He, Timothy M. Chan

Publication date: 25 November 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2110.02503

zbMATH Keywords

dynamic programmingFrobenius problemunbounded knapsackcoin changingfine-grained complexityword-break problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Dynamic programming (90C39) Algorithms on strings (68W32) The Frobenius problem (11D07)

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius
• New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
• Computing dominances in \(E^ n\)
• A note on the integrality gap of the configuration LP for restricted Santa Claus
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• The Change-Making Problem
• Faster All-Pairs Shortest Paths via Circuit Complexity
• A Faster Pseudopolynomial Time Algorithm for Subset Sum
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• On Problems Equivalent to (min,+)-Convolution
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Fast algorithms for knapsack via convolution and prediction
• On a linear diophantine problem of Frobenius