scientific article; zbMATH DE number 7651168

DOI10.4230/LIPICS.ESA.2020.29MaRDI QIDQ5874497FDOQ5874497

Timothy M. Chan, Qizheng He

Publication date: 7 February 2023

Title of this publication is not available (Why is that?)

zbMATH Keywords

dynamic programmingknapsackFrobenius problemcoin changingfine-grained complexity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• Computing dominances in \(E^ n\)
• New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Title not available (Why is that?)
• On a linear diophantine problem of Frobenius
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius
• The Change-Making Problem
• A Faster Pseudopolynomial Time Algorithm for Subset Sum
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• On Integer Programming and Convolution.
• Title not available (Why is that?)
• Faster All-Pairs Shortest Paths via Circuit Complexity
• On Problems Equivalent to (min,+)-Convolution
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast algorithms for knapsack via convolution and prediction
• Title not available (Why is that?)

Cited In (3)

• \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
• More on change-making and related problems
• Characterization of canonical systems with six types of coins for the change-making problem

Uses Software

• Knapsack

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874497)