Change-making problems revisited: a parameterized point of view

DOI10.1007/s10878-017-0143-zzbMath1373.90168OpenAlexW2619212074MaRDI QIDQ1679517

Frank Gurski, Eda Yilmaz, Jochen Rethmann, 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)

Related Items (4)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Knapsack problems: a parameterized point of view ⋮ When greedy gives optimal: a unified approach ⋮ Characterization of canonical systems with six types of coins for the change-making problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial kernels for weighted problems
• Fundamentals of parameterized complexity
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Totally greedy coin sets and greedy obstructions
• Combinatorics of the change-making problem
• An application of simultaneous diophantine approximation in combinatorial optimization
• A polynomial-time algorithm for the change-making problem
• Parametrized complexity theory.
• Kernelization: New Upper and Lower Bound Techniques
• Minkowski's Convex Body Theorem and Integer Programming
• When the Greedy Solution Solves a Class of Knapsack Problems
• The Change-Making Problem
• Computing Partitions with Applications to the Knapsack Problem
• Technical Note—Optimality of a Heuristic Solution for a Class of Knapsack Problems
• A Faster Pseudopolynomial Time Algorithm for Subset Sum
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Reducibility among Combinatorial Problems
• Parameterized Algorithms
• Algorithmic Solution of the Change-Making Problem

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