scientific article; zbMATH DE number 7651168

DOI10.4230/LIPICS.ESA.2020.29MaRDI QIDQ5874497FDOQ5874497

Authors: 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
• Fast algorithms for \((\max, \min)\)-matrix multiplication and bottleneck shortest paths
• 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)