论文标题
包装约束的截止性问题的近似算法
Approximation Algorithms for Interdiction Problem with Packing Constraints
论文作者
论文摘要
我们研究了一个二线优化问题，这是一个零和Stackelberg游戏。在这个问题中，有两个球员，一个领导者和一个追随者，他们从公共组中挑选项目。领导者和追随者都有自己的（多维）预算。每个项目都与利润相关联，这与领导者和追随者相同，如果领导者（追随者）选择了领导者的预算（追随者）的预算。领导者和追随者将以连续的方式选择项目：首先，领导者选择领导者预算中的项目。然后，追随者从追随者的预算中选择剩余项目中的项目。领导者的目标是最大程度地减少追随者获得的最大利润。令$ s_a $和$ s_b $分别为领导者和追随者预算的维度。我们问题的一个特殊情况是Caprara等人研究的二极管背包问题。 [Siam Journal on Optimization，2014]，其中$ s_a = s_b = 1 $。我们考虑一般问题，并获得$（s_b+ε）$ - 近似算法时，当$ s_a $和$ s_b $都是恒定的。特别是，如果$ s_b = 1 $，我们的算法意味着双重背包问题的PTA，这是第一个O（1）-Approximation算法。我们还通过证明不存在任何$（4/3-ε）$ - 近似算法，即使$ s_a = 1 $和$ s_b = 2 $，我们也可以补充我们的结果。当$ s_a $和$ s_b $都是输入的一部分时，我们还考虑了我们问题的变体。我们获得了具有O（1） - 资源增强的O（1） - APPRXIMATION算法，也就是说，我们给出了一种算法，该算法返回了一个解决方案，该解决方案超过O（1）次超过给定领导者的预算，而解决方案所实现的客观值是O（1）倍的最佳目标值，是领导者预算的最佳目标值。
We study a bilevel optimization problem which is a zero-sum Stackelberg game. In this problem, there are two players, a leader and a follower, who pick items from a common set. Both the leader and the follower have their own (multi-dimensional) budgets, respectively. Each item is associated with a profit, which is the same to the leader and the follower, and will consume the leader's (follower's) budget if it is selected by the leader (follower). The leader and the follower will select items in a sequential way: First, the leader selects items within the leader's budget. Then the follower selects items from the remaining items within the follower's budget. The goal of the leader is to minimize the maximum profit that the follower can obtain. Let $s_A$ and $s_B$ be the dimension of the leader's and follower's budget, respectively. A special case of our problem is the bilevel knapsack problem studied by Caprara et al. [SIAM Journal on Optimization, 2014], where $s_A=s_B=1$. We consider the general problem and obtain an $(s_B+ε)$-approximation algorithm when $s_A$ and $s_B$ are both constant. In particular, if $s_B=1$, our algorithm implies a PTAS for the bilevel knapsack problem, which is the first O(1)-approximation algorithm. We also complement our result by showing that there does not exist any $(4/3-ε)$-approximation algorithm even if $s_A=1$ and $s_B=2$. We also consider a variant of our problem with resource augmentation when $s_A$ and $s_B$ are both part of the input. We obtain an O(1)-approximation algorithm with O(1)-resource augmentation, that is, we give an algorithm that returns a solution which exceeds the given leader's budget by O(1) times, and the objective value achieved by the solution is O(1) times the optimal objective value that respects the leader's budget.
