Seminar za računarstvo i primenjenu matematiku, 5. jul 2019.
- 01. Jul, 2019
- Komentari (0)
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.
Komentari(0)