MISANU

Seminar on Computer Science and Applied Mathematics

PROGRAM

Matematički Institut SANU, Beograd
Knez Mihajlova 36
Fakultet organizacionih nauka, Univerzitet u Beogradu,
Jove Ilica 154
IEEE Chapter Computer Science (CO-16) Belgrade, Republic of Serbia

SEMINAR ZA RAČUNARSTVO I PRIMENJENU MATEMATIKU

MI SANU, Knez Mihailova 36, sala 301f

Upravni odbor Matematickog instituta SANU je na nedavnoj sednici doneo odluku da se dosadasnji Seminar za primenjenu matematiku, sada nazove Seminar za racunarstvo i primenjenu matematiku, a u cilju potenciranja znacaja racunarstva kao jedne od oblasti delatnosti Instituta. Istovremeno, Upravni odbor doneo je odluku o osnivanju Odeljenja za racunarstvo i primenjenu matematiku i vezao rad novog odeljenja za rad Seminara za racunarstvo i primenjenu matematiku.

PLAN RADA SEMINARA ZA JUL 2019. GODINE

Utorak, 02.07.2019. 14:15, Sala 301f, MI SANU, Kneza Mihaila 36
Ljiljana Branković, School of Electrical Engineering and 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, focussing 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.

RUKOVODIOCI SEMINARA
MI SANU
Vera Kovačević-Vujčić
Milan Dražić

FON
Zorica Bogdanovic
Marijana Despotovic-Zrakic

IEEE
Bozidar Radenkovic