The subset sum game revisited

DOI10.1007/s00224-021-10034-zzbMath1470.91058OpenAlexW3184916350MaRDI QIDQ5918370

Gerhard J. Woeginger, Astrid Pieterse

Publication date: 5 August 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-021-10034-z

zbMATH Keywords

computational complexitymulti-agent optimizationapproximability

Mathematics Subject Classification ID

2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46) Algorithmic game theory and complexity (91A68)

Cites Work

• Unnamed Item
• The Subset Sum game
• A dynamic programming algorithm for the bilevel Knapsack problem
• On the complexity of some two-person perfect-information games
• A Stackelberg knapsack game with weight control
• Improved approximation algorithms for a bilevel knapsack problem
• A polynomial algorithm for a continuous bilevel knapsack problem
• A faster algorithm for the continuous bilevel knapsack problem
• The Design of Approximation Algorithms
• Bilevel Knapsack with Interdiction Constraints
• A Study on the Computational Complexity of the Bilevel Knapsack Problem
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Bilevel programming with knapsack constraints