A lower bound for the hitting set size for combinatorial rectangles and an application

被引：0

作者：

Chandran, LS ^{[1
]}

机构：

[1] Indian Inst Sci, Dept Comp Sci & Automat, Bangalore 560012, Karnataka, India

来源：

INFORMATION PROCESSING LETTERS | 2003年 / 86卷 / 02期

关键词：

hitting set; combinatorial rectangle; combinatorial problems;

D O I：

10.1016/S0020-0190(02)00475-1

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We prove a lower bound of Omega(1/epsilon (m + log(d - a)) where a = [log(m) (1/4epsilon)] for the hitting set size for combinatorial rectangles of volume at least epsilon in [m](d) space, for epsilon is an element of [m(-(d-2)), 2/9] and d > 2. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：75 / 78

页数：4

共 8 条

[1] 3-HITTING SET on Bounded Degree Hypergraphs: Upper and Lower Bounds on the Kernel Size
Kanj, Iyad A.
Zhang, Fenghui
THEORY AND PRACTICE OF ALGORITHMS IN COMPUTER SYSTEMS, 2011, 6595 : 163 - +
[2] 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size
Kanj, Iyad
Zhang, Fenghui
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2015, 7 (02)
[3] Sharp Concentration of Hitting Size for Random Set Systems
Jessie D. Jamieson
Anant Godbole
William Jamieson
Lucia Petito
Graphs and Combinatorics, 2015, 31 : 639 - 648
[4] Sharp Concentration of Hitting Size for Random Set Systems
Jamieson, Jessie D.
Godbole, Anant
Jamieson, William
Petito, Lucia
GRAPHS AND COMBINATORICS, 2015, 31 (03) : 639 - 648
[5] Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
Gutin, G.
Jones, M.
Yeo, A.
THEORETICAL COMPUTER SCIENCE, 2011, 412 (41) : 5744 - 5751
[6] Optimal-size problem kernels for d-Hitting Set in linear time and space
van Bevern, Rene
Smirnov, Pavel V.
INFORMATION PROCESSING LETTERS, 2020, 163
[7] A lower bound on the size of ε-free NFA corresponding to a regular expression
Lifshits, Y
INFORMATION PROCESSING LETTERS, 2003, 85 (06) : 293 - 299
[8] A NEW LOWER-BOUND ON THE EXPECTED SIZE OF IRREDUNDANT FORMS FOR BOOLEAN FUNCTIONS
OCONNOR, L
INFORMATION PROCESSING LETTERS, 1995, 53 (06) : 347 - 353

← 1 →