דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
רן בן-בשט (הרצאה סמינריונית למגיסטר)
event date icon
יום שני, 22.09.2014, 15:30
event location icon
Taub 701
event speaker icon
מנחה: Prof. Hadas Shachnai
Parameterization is a useful tool for handling NP-hard problems in the real world. It aims to reduce the running times of algorithms for such problems, by confining the combinatorial explosion to some parameter k. As this parameter is often significantly smaller than the input size, it allows to develop practical algorithms for non-trivial classes of instances for these problems. In this talk we present a novel framework for developing parameterized algorithms, using constructions of automata for the corresponding languages. Our automata-based framework gives a different view of the parameterized versions of several classic problems, including Traveling Salesman and 3D-Matching. We show that many of the previously used techniques for solving these problems imply automata constructions for some implicitly related regular languages. We use automata tools also to infer lower bounds for these techniques. Finally, we note that our framework allows clean and simple design of algorithms for a family of problems, where the design of a single automaton for a specific problem yields deterministic, randomized and approximate witness counting algorithms for the problem.