Abstract | ||
---|---|---|
Combinatorial batch codes were defined by Paterson, Stinson, and Wei as purely combinatorial versions of the batch codes introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai. There are n items and m servers each of which stores a subset of the items. It is required that, for prescribed integers k and t, any k items can be retrieved by reading at most t items from each server. Only the case t = 1 is considered here. An optimal combinatorial batch code is one in which the total storage required is a minimum. We establish an important connection between combinatorial batch codes and transversal matroids, and exploit this connection to characterize optimal combinatorial batch codes if n = m + 1 and n = m + 2. |
Year | DOI | Venue |
---|---|---|
2010 | 10.3934/amc.2010.4.419 | ADVANCES IN MATHEMATICS OF COMMUNICATIONS |
Keywords | Field | DocType |
Combinatorial batch codes,transversal matroid,dual matroid,cocircuit,presentation of a transversal matroid | Integer,Matroid,Discrete mathematics,Combinatorics,Batch Code,Dual matroid,Server,Transversal (geometry),Mathematics | Journal |
Volume | Issue | ISSN |
4 | 3 | 1930-5346 |
Citations | PageRank | References |
16 | 1.40 | 2 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Richard Brualdi | 1 | 16 | 1.40 |
Kathleen Kiernan | 2 | 21 | 2.30 |
Seth Meyer | 3 | 16 | 1.40 |
Michael W. Schroeder | 4 | 22 | 4.37 |