ARTP - 05 - APX algoritmy založené na celočíselnom lineárnom programovaní

Zhrnutie prednášky

Prednáška ukazuje, ako pomocou celočíselného lineárneho programovania (ILP) navrhovať aproximačné algoritmy. ILP je NP-ťažké, no mnohé NP-ťažké problémy sa dajú naň preformulovať a riešiť hotovými solvermi. Na príklade váhovaného vrcholového pokrytia sa zavádza premenná x_v pre každý vrchol, minimalizuje sa súčet váh vybraných vrcholov a pre každú hranu platí x_u + x_v ≥ 1. Podmienka celočíselnosti sa potom relaxuje na interval od 0 do 1, čím vznikne lineárny program riešiteľný v polynomiálnom čase, ktorého optimum je dolným odhadom optima ILP. Zlomkové riešenie sa zaokrúhli tak, že vrchol patrí do pokrytia, ak x_v ≥ 1/2; na konci sa rozoberá otázka, či je výsledok vôbec vrcholovým pokrytím.

• - ILP hľadá hodnoty premených 0/1 optimalizujúce lineárnu funkciu za lineárnych obmedzení a je NP-ťažké.
• - Váhované vrcholové pokrytie: minimalizácia súčtu w_v·x_v s podmienkou x_u + x_v ≥ 1 pre každú hranu.
• - Relaxácia nahradí x ∈ {0,1} podmienkou 0 ≤ x ≤ 1 a vznikne lineárny program riešiteľný v polynomiálnom čase.
• - Každé riešenie ILP je aj riešením relaxovaného LP, takže optimum LP je dolným odhadom optima ILP (pri minimalizácii).
• - Zlomkové hodnoty treba zaokrúhliť: vrchol sa zaradí do pokrytia, ak x_v ≥ 1/2.
• - Otvorená otázka na konci: či je takto zaokrúhlené riešenie platným vrcholovým pokrytím.

Zhrnutie pripravené s pomocou AI z prepisu videa.