A lower bound for the hitting set size for combinatorial rectangles and an application
| Data(s) |
30/04/2003
|
|---|---|
| Resumo |
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. |
| Formato |
application/pdf |
| Identificador |
http://eprints.iisc.ernet.in/39709/1/A_lower_bound.pdf Chandran, Sunil L (2003) A lower bound for the hitting set size for combinatorial rectangles and an application. In: Information Processing Letters, 86 (2). pp. 75-78. |
| Publicador |
Elsevier Science |
| Relação |
http://dx.doi.org/10.1016/S0020-0190(02)00475-1 http://eprints.iisc.ernet.in/39709/ |
| Palavras-Chave | #Computer Science & Automation (Formerly, School of Automation) |
| Tipo |
Journal Article PeerReviewed |
