Семинар за рачунарство и примењену математику, 5. јул 2019.

Наредни састанак Семинара биће одржан у петак, 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.


Нажалост није могуће оставити коментар.

Вести и дешавања


Активности на семинарима

све вести