Семинар за рачунарство и примењену математику, 5. јул 2019.
- 01. Јул, 2019
- Коментари (0)
Наредни састанак Семинара биће одржан у петак, 5. јул 2019. у сали 301ф Математичког института САНУ са почетком у 14:15.
Предавач: Љиљана Бранковић, School of Еlectrical Engineering anд Computing, Faculty of Engineering and Built Environment, The University of Newcastle, Australia
Наслов предавања: PARAMETERISED APPROXIMATION ALGORITHM FOR HITTING SET
Апстракт: 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.
Коментари(0)