Improved approximation algorithms for a bilevel knapsack problem

DOI10.1016/j.tcs.2015.06.027zbMath1328.68306OpenAlexW2339632011MaRDI QIDQ2354770

Xian Qiu, Walter Kern

Publication date: 24 July 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.06.027

zbMATH Keywords

approximation algorithmknapsackStackelbergbilevel

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (9)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ A polynomial algorithm for a continuous bilevel knapsack problem ⋮ Solution techniques for bi-level knapsack problems ⋮ An exact approach for the bilevel knapsack problem with interdiction constraints and extensions ⋮ On the Stackelberg knapsack game ⋮ The subset sum game revisited ⋮ Computational complexity characterization of protecting elections from bribery ⋮ A Stackelberg knapsack game with weight control ⋮ Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography

Cites Work

• Unnamed Item
• Unnamed Item
• Two-person knapsack game
• Bilevel programming: a survey
• A dynamic programming algorithm for the bilevel Knapsack problem
• Multilevel optimization: algorithms and applications
• Foundations of bilevel programming
• Weak via strong Stackelberg problem: New results
• An exact algorithm for bilevel 0-1 knapsack problems
• Two-group knapsack game
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• A Complexity and Approximability Study of the Bilevel Knapsack Problem
• Approximation Algorithms for a Bi-level Knapsack Problem
• Bilevel programming with knapsack constraints

This page was built for publication: Improved approximation algorithms for a bilevel knapsack problem