Seminar za računarstvo i primenjenu matematiku, 5. jul 2019.

Naredni sastanak Seminara biće održan u petak, 5. jul 2019. u sali 301f Matematičkog instituta SANU sa početkom u 14:15.

Predavač: Ljiljana Branković, School of Electrical Engineering and Computing, Faculty of Engineering and Built Environment, The University of Newcastle, Australia

Naslov predavanja: PARAMETERISED APPROXIMATION ALGORITHM FOR HITTING SET

Apstrakt: The Hitting Set  problem can be stated as follows: Given a hypergraph $G=(V,E)$ with edge size bounded by $d$ and a non-negative integer $K$, is there a subset of vertices  $C$ of cardinality  of at most $K$, such that each edge in $E$ has at least one of its vertices in $C$? We design  and  analyze simple search tree algorithms for approximating 3-Hitting Set, focusing on the case of factor-2 approximations for $d=3$. The main ingredient of our algorithms are exact and approximation- preserving reduction rules. We also derive several results for hypergraph instances of bounded degree, including a new polynomial-time approximation algorithm.



Nažalost nije moguće ostaviti komentar.