@article{6a72779e7b424bfdac5322282e98f603,
title = "APPROXIMATING MINIMUM REPRESENTATIONS OF KEY HORN FUNCTIONS",
abstract = "Horn functions form an important subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem admitting a 2log1-o(1) n inapproximability bound. In this paper we consider the natural class of key Horn functions representing keys of relational databases. For this class, the minimization problems for most measures remain NP-hard. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all such measures.",
keywords = "Horn minimization, approximation algorithms, directed hypergraphs, implicational systems",
author = "Krist{\'o}f B{\'e}rczi and Endre Boros and Ond{\v r}ej {\v C}epek and Petr Ku{\v c}era and Kazuhisa Makino",
note = "Funding Information: ∗Received by the editors July 18, 2019; accepted for publication (in revised form) October 22, 2021; published electronically February 14, 2022. https://doi.org/10.1137/19M1275681 Funding: This work was supported by the J{\'a}nos Bolyai Research Fellowship and the Lend{\"u}let Programme of the Hungarian Academy of Sciences (grant LP2021-1/2021), by the National Research, Development and Innovation Fund of Hungary under the FK 18 funding scheme (project NKFI-128673), by the Thematic Excellence Programme (National Challenges Subprogramme) (project TKP-20-20-NKA-06), by Czech Science Foundation (Grant 19-19463S), and by SVV (project 260 453). Publisher Copyright: {\textcopyright} 2022 Society for Industrial and Applied Mathematics.",
year = "2022",
doi = "https://doi.org/10.1137/19M1275681",
language = "American English",
volume = "51",
pages = "116--138",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",
}