Problema del recobriment

Els problemes de recobriment són normalment problemes de minimització i programació lineal, els problemes duals dels quals s'anomenen problemes d'embalatge. Els exemples més prominents de problemes de recobriment són el problema del recobriment d'un conjunt.

Formulació LP general

En el context de programació lineal, es pot pensar en qualsevol programa lineal com a problema de recobriment si els coeficients a la matriu de restriccions, la funció objectiu, i el cantó de la dreta són no negatius. Més precisament, consideri's el programa lineal general en variables enteres:

minimitzar	$\sum _{i=1}^{n}c_{i}x_{i}$
subjecte a	$\sum _{i=1}^{n}a_{ij}x_{i}\geq b_{j}{\text{ for }}j=1,\dots ,m$
	$x_{i}\geq 0{\text{ for }}i=1,\dots ,n$.

Tal programa lineal en variables enteres s'anomena problema de recobriment si $a_{ij},b_{j},c_{i}\geq 0$ per a tot $i=1,\dots ,n$ i $j=1,\dots ,m$.

Intuïció: Suposar que es tenen $n$ tipus d'objecte i cada objecte del tipus $i$ té un cost associat de $c_{i}$. El nombre $x_{i}$ diu quants objectes del tipus $i$ es compren. Si les restriccions $A\mathbf {x} \geq \mathbf {b}$ es satisfan, es diu que $\mathbf {x}$ és un recobriment (les estructures que es recobreixen depenen del context combinatori). Finalment, una solució òptima al citat programa lineal és un recoberiment de cost mínim.

Altres usos

Per a xarxes de Petri, per exemple, el problema del recobriment es defineix com la pregunta de si per a un marcatge donat, existeix un camí de la xarxa, tal que es pot arribar amb una marca més gran (o igual). Més gran vol dir aquí que tots els components són com a mínim tan grans com el del marcatge donat i com a mínim un és pròpiament més gran.

Bibliografia

• Vazirani, Vijay V. Approximation Algorithms. Springer-Verlag, 2001. ISBN 3-540-65367-8.