National Institute of the Republic of Serbia
ὅδε οἶκος, ὦ ἑταῖρε, μνημεῖον ἐστιν ζωῶν τῶν σοφῶν ἀνδρῶν, καὶ τῶν ἔργων αὐτῶν
PROGRAM
| ODELJENJE ZA MATEMATIKU MATEMATIČKOG INSTITUTA SANU |
PROGRAM ZA JUL 2019.
PETAK, 05.07.2019 u 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.
Zajednički sastanak Seminara za računarstvo i primenjenu matematiku.