Tight Approximation Algorithms for Maximum General Assignment Problems

Link: https://math.mit.edu/~goemans/PAPERS/ga-soda06.pdf

---

Separable Assignment Problem (SAP):

• A set $U=\{1,\dots ,n\}$ of bins
• A set $H=\{1,\dots ,m\}$ of items
• Value function $f:U\times H\to \mathbb{R}$
• Each bin $i$ has a packing constraint ${\mathcal{I}}_i\subseteq 2^U$ consisting of subsets of items that fit in bin $i$
  • Introduces the single-bin sub-problem, an optimization problem over feasible sets
• Goal: assign items to bins with a maximum aggregate value

Single-bin Sub-problem:

• Fixed bin $i$
• Set of items $j\in H$ with values $v_j$
• Packing constraint for bin $i$, ${\mathcal{I}}_i\subseteq 2^H$ that is a lower-ideal of $H$, consisting of feasible subsets of items that can be packed in bin $i$.
  • Lower-ideal: for all $A\subseteq B$, $B\in \mathcal{I}\Rightarrow A\in \mathcal{I}$.
• Goal: Determine optimal subset of items $S\in \mathcal{I}$ to pack into bin $i$ under some objective $f(S)$.

We assume there is a $\beta$-approximation algorithm, $\beta \le 1$, for the single-bin subproblem. That is, an algorithm that outputs a subset of items $S\in {\mathcal{I}}_i$, such that for any other subset $S^{\prime }\in {\mathcal{I}}_i$,

${\sum }_{j\in S}{v}_j\ge \beta {\sum }_{j\in S^{\prime }}{v}_j.$ Assuming such an algorithm exists, they give a $((1-1/e)\beta )$-approximation algorithm based on LP-rounding. They also give a polynomial-time search $(\beta /(\beta +1)-ϵ)$-approximation algorithm.

Remark: The single-bin subproblem turns out to be a knapsack problem, whose greedy algorithm gives a 1/2-approximation. Knapsack also has a FPTAS giving a $(1-ϵ)$-approximation; hence there is a polynomial-time $(1-1/e)$-approximation algorithm for SAP.

LP-Based Approximation Algorithms

They give approximation algorithms under the assumption there is an $\beta$-approximation algorithm for the single-bin sub-problem.

• Let ${\mathcal{I}}_i$ for $i\in U$ be the set of feasible assignments of items to bin $i$ (given by single-bin sub-problem)
• For $S\in {\mathcal{I}}_i$, define $X_S^i\in \{0,1\}$ to indicate we chose $S$ as the subset of items for bin $i$
• Constraints:
  • One set per bin (note: $\varnothing \in {\mathcal{I}}_i$):

${\sum }_{S\in {\mathcal{I}}_i}{X}_S^i=1,\forall i\in U$

- Item can only be assigned to at most one bin: 

${\sum }_{i\in U,S\in {\mathcal{I}}_i:j\in S}{X}_S^i\le 1,\forall j\in H$

• Objective: Find assignment of items while maximizing profits:

$\max {\sum }_{i\in U,S\in {\mathcal{I}}_i}{f}_i^S{X}_S^i\text{ where }{f}_i^S={\sum }_{j\in S}{f}_{ij}$

They take the LP-relaxation, i.e., $X_S^i\in {\mathbb{R}}_{+}$.

Rounding:

• Solve the relaxed LP above
• For each bin $i$, assign set $S$ to $i$ with probability $X_S^i$
• If an item $j$ is in more than one bin, assign $j$ to the bin with maximum $f_{ij}$-value.

Theorem 2.1. The expected value of the rounded solution to the LP-relaxation is at least $(1-(1-\frac{1}{n}{)}^n)\text{LP}(\text{SAP})$.

Note: $(1-(1-1/n{)}^n)\to (1-1/e)\approx 0.63$ as $n\to \infty$

Solving the LP

The LP has exponentially many variables, by taking the dual we get polynomial number of variables but exponentially many constraints.

Dual LP:

$$\begin{array}{rlrlr}& \min & \sum _{i\in U}{q}_i+\sum _{j\in H}{\lambda }_j& & \\ & \text{s.t.}& q_i+\sum _{j\in S}{\lambda }_j\ge f_i^S& & \forall i\in U,S\in {\mathcal{I}}_i\\ & & {\lambda }_j\ge 0& & \forall j\in H.\end{array}$$

Define the polytope

$${\mathcal{P}}_i=\left\{(q_i,\lambda ):q_i\ge \sum _{j\in S}(f_{ij}-{\lambda }_j),\forall S\in {\mathcal{I}}_i\right\}.$$

Then we can rewrite the dual LP as a fractional covering problem:

$$\begin{array}{rlrlr}& \min & \sum _{i\in U}{q}_i+\sum _{j\in H}{\lambda }_j& & \\ & \text{s.t.}& (q_i,\lambda )\in {\mathcal{P}}_i& & \forall i\in U\\ & & {\lambda }_j\ge 0& & \forall j\in H.\end{array}$$

Define a $\beta$-approximation separation algorithm for ${\mathcal{P}}_i$ to be an algorithm that takes in a point $(q_i,{\lambda }_j\mid j\in H)$ and returns either a violated constraint, or ensures that $(q_i/\beta ,{\lambda }_j\mid j\in H)$ is feasible for ${\mathcal{P}}_i$. One may approximate the above LP via Lagrangian LP algorithms.

Given a $\beta$-approximation algorithm for the single-bin subproblem, we can find a subset $S^{\ast }\in {\mathcal{I}}_i$ with value $q_i^{\ast }$ such that for any $S^{\prime }\in {\mathcal{I}}_i$,

$$q_i^{\ast }=\sum _{j\in S^{\ast }}(f_{ij}-{\lambda }_j)\ge \beta \sum _{j\in S^{\prime }}(f_{ij}-{\lambda }_j).$$

Two cases: $q_i^{\ast }>q_i$, in which a constraint is violated, or $q_i^{\ast }\le q_i$. In the latter case,

$$\sum _{j\in S^{\prime }}(f_{ij}-{\lambda }_j)\le \frac{q_i^{\ast }}{\beta }\le \frac{q_i}{\beta },\forall S^{\prime }\in {\mathcal{I}}_i.$$

Thus, $(q_i/\beta ,{\lambda }_j\mid j\in U)$ is feasible for ${\mathcal{P}}_i$.

Solving the Single-bin Sub-problem

The single-bin sub-problem can be written as a knapsack problem which has an efficient FPTAS.

• Single-bin sub-problem:

$$\begin{array}{rlr}& \max & f(S)\\ & \text{s.t.}& S\in {\mathcal{I}}_i\end{array}$$

• Knapsack:
  • Define $w:H\to \mathbb{R}$ by the following

$$w_j=\{\begin{array}{ll}0& \text{if }\exists S\in {\mathcal{I}}_i\text{ s.t. }j\in S\\ 1& \text{otherwise.}\end{array}$$

- Then the single-bin sub-problem can be seen as a knapsack problem: 

$$\begin{array}{rlrl}& \max & \sum _{j=1}^m{v}_j{x}_j& \\ & \text{s.t.}& \sum _{j=1}^m{w}_j{x}_j\le 0& \\ & & x_j\in \{0,1\},& \forall j\in H\end{array}$$

Local Search Algorithms

Define

• $\mathcal{S}=(S_1,\dots ,S_n)$ assignment of items to bins, where $S_i\in 2^H$.
• $v(\mathcal{S})$ value of assignment $\mathcal{S}$
• ${\alpha }_i(\mathcal{S})$ total value of items satisfied by bin $i$ in $\mathcal{S}$
• $v_j(S)$ the value of item $j$ in $\mathcal{S}$

$\text{Local}(i)$:

1. For each item $j$, set ${\text{value}}_j(\mathcal{S})=f_{i^{\prime }j}$ if $j$ is assigned to bin $i^{\prime }\ne i$ in $\mathcal{S}$. Otherwise, ${\text{value}}_j(\mathcal{S})=0$
2. For each item $j$, define marginal value $w_j=f_{ij}-{\text{value}}_j(\mathcal{S})$
3. Determine the subset of items to pack in bin $i$ which gives maximal marginal value using the $\beta$-approximation algorithm.

Local Search Algorithm:

1. Start with empty solution: $\mathcal{S}=(S_1,\dots ,S_n)$ where $S_i=\varnothing$
2. For a given $ϵ>0$, run the following $(1/\beta )n\ln (1/ϵ)$-times:
   1. For each bin $i$, run $\text{Local}(i)$. Set the marginal value of this solution for bin $i$ to be $W_i$ and $S_i^{\prime }$ the set of items with marginal value $W_i$.
   2. For each bin $i$, set ${\Delta }_i=W_i-{\alpha }_i(\mathcal{S})$
   3. Set bin $i^{\ast }$ to be the bin with maximal ${\Delta }_i$
   4. If ${\Delta }_{i^{\ast }}>0$, set the set $S_{i^{\ast }}$ of items for bin $i^{\ast }$ to $S_{i^{\ast }}^{\prime }$