Pokrytí problémů - Covering problems

v kombinatorika a počítačová věda, pokrývající problémy jsou výpočetní problémy, které se ptají, zda určitá kombinatorická struktura „pokrývá“ jinou, nebo jak velká musí být struktura, aby to dokázala. problémy s minimalizací a obvykle lineární programy, jehož dvojí problémy jsou nazývány problémy s balením.

Nejvýznamnějšími příklady řešení problémů jsou nastavit problém s krytem, což je ekvivalentní s bít set problém a jeho zvláštní případy problém s vrcholovým krytem a problém s okrajovým krytem.

Obecná formulace LP

V kontextu lineární programování, lze si představit jakýkoli lineární program jako krycí problém, pokud jsou koeficienty v matici omezení, objektivní funkci a pravé straně nezáporné.^[1] Přesněji, zvažte následující obecné celočíselný lineární program:

minimalizovat	${ displaystyle sum _ {i = 1} ^ {n} c_ {i} x_ {i}}$
podléhá	${ displaystyle sum _ {i = 1} ^ {n} a_ {ij} x_ {i} geq b_ {j} { text {pro}} j = 1, tečky, m}$
	${ displaystyle x_ {i} geq 0 { text {pro}} i = 1, tečky, n}$.

Takový celočíselný lineární program se nazývá krycí problém -li ${ displaystyle a_ {ij}, b_ {j}, c_ {i} geq 0}$ pro všechny ${ displaystyle i = 1, tečky, n}$ a ${ displaystyle j = 1, tečky, m}$.

Intuice: Předpokládejme, že ${ displaystyle n}$ typy objektů a každý objekt typu ${ displaystyle i}$ má související náklady ve výši ${ displaystyle c_ {i}}$. Číslo ${ displaystyle x_ {i}}$ označuje, kolik objektů typu ${ displaystyle i}$ kupujeme. Pokud omezení ${ displaystyle A mathbf {x} geq mathbf {b}}$ jsou spokojeni, říká se ${ displaystyle mathbf {x}}$ je krytina (struktury, na které se vztahuje, závisí na kombinatorickém kontextu). A konečně, optimálním řešením výše uvedeného celočíselného lineárního programu je pokrytí minimálních nákladů.

Jiná použití

Pro Petriho sítě například krycí problém je definován jako otázka, zda pro dané značení existuje běh sítě, takže lze dosáhnout nějakého většího (nebo stejného) značení. Větší zde znamená, že všechny komponenty jsou alespoň stejně velké jako komponenty daného značení a alespoň jedna je řádně větší.

Viz také

• The biclique problém s krytem hran požádá o pokrytí všech okrajů daného grafu (co nejméně) kompletní bipartitní podgrafy.
• Problém s krytím disku, problém pokrytí jednotkového kruhu menšími kruhy
• Polygonový potah, problém pokrytí složitého polygonu jednoduššími polygony, jako jsou čtverce nebo obdélníky.
• Problém bez obdélníku. Problém pokrytí obdélníkové oblasti bez dílčích obdélníků. ^[2]

Poznámky

Reference

• Vazirani, Vijay V. (2001). Aproximační algoritmy. Springer-Verlag. ISBN  3-540-65367-8.

externí odkazy

• Erich's Packing Center obsahuje několik ilustrací problémů s geometrickým pokrytím.