Change-making problems revisited: a parameterized point of view

DOI10.1007/S10878-017-0143-ZMaRDI QIDQ1679517zbMATH OpenOpenAlexFDO

Authors Frank Gurski, Jochen Rethmann, Eda Yilmaz, Steffen J. Goebbels

Publication date 9 November 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-017-0143-z

zbMATH Keywords

combinatorial optimizationfixed-parameter tractabilitykernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Dynamic programming (90C39)

Recommendations

• A polynomial-time algorithm for the change-making problem
• Optimal bounds for the change-making problem
• More on change-making and related problems
• Optimal bounds for the change-making problem
• Exact analysis of exact change: The k-payment problem

Cites work

• A faster pseudopolynomial time algorithm for subset sum
• A near-linear pseudopolynomial time algorithm for subset sum
• A polynomial-time algorithm for the change-making problem
• Algorithmic Solution of the Change-Making Problem
• An application of simultaneous diophantine approximation in combinatorial optimization
• Combinatorics of the change-making problem
• Computing Partitions with Applications to the Knapsack Problem
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 503190 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Kernelization: new upper and lower bound techniques
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Minkowski's Convex Body Theorem and Integer Programming
• Parameterized algorithms
• Parametrized complexity theory.
• Reducibility among combinatorial problems
• Technical Note—Optimality of a Heuristic Solution for a Class of Knapsack Problems
• The Change-Making Problem
• Totally greedy coin sets and greedy obstructions
• When the Greedy Solution Solves a Class of Knapsack Problems

Cited in

(11)

• Totally greedy coin sets and greedy obstructions
• A polynomial-time algorithm for the change-making problem
• More on change-making and related problems
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Knapsack problems: a parameterized point of view
• Characterization of canonical systems with six types of coins for the change-making problem
• Exact analysis of exact change: The k-payment problem
• When greedy gives optimal: a unified approach
• The change-making problem for six coin values and beyond
• Scheduling kernels via configuration LP
• Parameterized complexity of factorization problems

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Change-making problems revisited: a parameterized point of view

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