scientific article; zbMATH DE number 7651168

DOI10.4230/LIPIcs.ESA.2020.29MaRDI QIDQ5874497

Timothy M. Chan, Qizheng He

Publication date: 7 February 2023

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

dynamic programmingFrobenius problemknapsackcoin changingfine-grained complexity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

Characterization of canonical systems with six types of coins for the change-making problem, More on change-making and related problems

Uses Software

• Knapsack

Cites Work

• 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\)
• 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
• On Integer Programming and Convolution.
• Fast algorithms for knapsack via convolution and prediction
• On a linear diophantine problem of Frobenius
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item