| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Biclique Coverings, Rectifier Networks and the Cost of ε-Removal
Abstract : We relate two complexity notions of bipartite graphs: the minimal weight biclique covering number Cov(G) and the minimal rec-tifier network size Rect(G) of a bipartite graph G. We show that there exist graphs with Cov(G) ≥ Rect(G) 3/2−ǫ . As a corollary, we estab-lish that there exist nondeterministic finite automata (NFAs) with ε-transitions, having n transitions total such that the smallest equivalent ε-free NFA has Ω(n 3/2−ǫ) transitions. We also formulate a version of previous bounds for the weighted set cover problem and discuss its con-nections to giving upper bounds for the possible blow-up.
Cited literature [19 references]
https://hal.inria.fr/hal-01079368
Contributor : Balazs Szorenyi <>
Submitted on : Saturday, November 1, 2014 - 11:39:51 AM
Last modification on : Tuesday, November 24, 2020 - 2:18:20 PM
Long-term archiving on: : Monday, February 2, 2015 - 4:51:59 PM
Contributor : Balazs Szorenyi <>
Submitted on : Saturday, November 1, 2014 - 11:39:51 AM
Last modification on : Tuesday, November 24, 2020 - 2:18:20 PM
Long-term archiving on: : Monday, February 2, 2015 - 4:51:59 PM
File
1406.0017v1.pdf
Files produced by the author(s)