Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MAXIMUM PACKING INTEGER PROGRAMMING

• INSTANCE: Rational $m\times n$-matrix $A\in [0,1]^{m\cdot n}$, rational m-vector $b\in [1,\infty)^m$, rational n-vector $c\in [0,1]^n$.

• SOLUTION: A rational n-vector $x\in [0,1]^n$ such that $Ax\le b$.

• MEASURE: The scalar product of c and x, i.e., $$\sum\limits_{i=1}^{n} c_i x_i$$.

  
  

• Good News: Approximable within $O(\mbox{\sl opt}(c{m^{1/B}}/{\mbox{\sl opt}})^{B/(B-1)})$ for some c>0, where $B=\min_i b_i$ [446].

• Comment: Variation in which $A\in \{0,1\}^{m\cdot n}$ and $b\in Z^+$ is approximable within
  $O(\mbox{\sl opt}(m^{1/(B+1)}/\mbox{\sl opt})^{(B+1)/B})$ [446].