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

We consider the fractional and generalized hypertree width measures, which capture the ability to decompose a hypergraph into tree-like structures. We present improved polynomial-time and parameterized approximation algorithms to these measures: polynomial-time and parameterized approximations to the fractional measure; and a polynomial-time approximation to the generalized measure. All our results improve upon the corresponding previous best known results of [Korchemna-Lokshtanov-Saurabh-Surianarayanan-Xue FOCS‘2024]. Our approach boils down to a novel use of semi-definite programming for approximating a coverage type vertex separator problem in hypergraphs, that lies at the core of the divide-and-conquer approach to approximating the fractional hypertree width measure.