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)

MINIMUM COVERING 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\ge b$.

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

  
  

• Good News: Approximable within $1+O(\max(\log(mB/\mbox{\sl opt}),\sqrt{\log(mB/\mbox{\sl opt})/B}))$, 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].